搜搜考试网【组合数学问题】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
问题描述的够清除了,求问为什么
请注意如何把两种项链视为相同的.
以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