【组合数学问题】Mobius反演定理和polya定理
来源:学生作业帮 编辑:搜搜考试网作业帮 分类:数学作业 时间:2024/08/18 23:10:09
【组合数学问题】Mobius反演定理和polya定理
相同的问题,用m种颜色的珠子串n颗项链不同种树的问题,用Mobius反演定理和Polya定理两种定理都可以解答,但是我试了好多情况,用两种方法算出来的结果都不一样,为什么,
m=3,n=3 M定理:(1*3^3+2*3)/3=11 Polya定理:(3^3+2*3+3*3^2)/6=10
同理m=3,n=4 M定理:24 P定理:21
m=3,n=12 M定理:44386 P定理:22913
问题描述的够清除了,求问为什么
相同的问题,用m种颜色的珠子串n颗项链不同种树的问题,用Mobius反演定理和Polya定理两种定理都可以解答,但是我试了好多情况,用两种方法算出来的结果都不一样,为什么,
m=3,n=3 M定理:(1*3^3+2*3)/3=11 Polya定理:(3^3+2*3+3*3^2)/6=10
同理m=3,n=4 M定理:24 P定理:21
m=3,n=12 M定理:44386 P定理:22913
问题描述的够清除了,求问为什么
![【组合数学问题】Mobius反演定理和polya定理](/uploads/image/z/19332504-0-4.jpg?t=%E3%80%90%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6%E9%97%AE%E9%A2%98%E3%80%91Mobius%E5%8F%8D%E6%BC%94%E5%AE%9A%E7%90%86%E5%92%8Cpolya%E5%AE%9A%E7%90%86)
请注意如何把两种项链视为相同的.
以3个珠子为例
你使用Polya定理时,使用的对称群是S3,那么穿法123和132被视为一种(这是轴对称),123和231被视为一种(旋转).这样计算就是10种
你使用Mobius反演定理时,算得应该是圆排列,那么穿法123和132不被视为同一种(这是轴对称),而123和231被视为一种(旋转).
这种情况下,使用Polya定理使用的对称群应该是C3,也就是{(1)(2)(3),(1 2 3) (1 3 2)},计算结果:(1*3^3+2*3^1)/3=11
以3个珠子为例
你使用Polya定理时,使用的对称群是S3,那么穿法123和132被视为一种(这是轴对称),123和231被视为一种(旋转).这样计算就是10种
你使用Mobius反演定理时,算得应该是圆排列,那么穿法123和132不被视为同一种(这是轴对称),而123和231被视为一种(旋转).
这种情况下,使用Polya定理使用的对称群应该是C3,也就是{(1)(2)(3),(1 2 3) (1 3 2)},计算结果:(1*3^3+2*3^1)/3=11