首页 > 代码库 > Polya定理应用实例
Polya定理应用实例
关于Polya原理的应用经典实例:
问题:用两种颜色去染排成一个圈的6个棋子,如果通过旋转得到只算作一种。问有多少种染色状态。
解:先将棋子表上号:
1
6 2
5 3
4
那么把所有通过旋转m(m大于等于0小于等于5)步的写出来:
1 6 5
6 2 5 1 4 6
5 3 4 2 3 1
4 3 2
(m=0) (m=1) (m=2)
4 3 2
3 5 2 4 1 3
2 6 1 5 6 4
1 6 5
(m=3) (m=4) (m=5)
然后写出每种的置换群:
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 2 3 4 5 6 6 1 2 3 4 5 5 6 1 2 3 4
m= 0 m=1 m=2
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
4 5 6 1 2 3 3 4 5 6 1 2 2 3 4 5 6 1
m=3 m=4 m=5
(第一行是原来每位的数字,后一行为现在每位数字)
化简:
(1)(2)(3)(4)(5)(6) (1,6,5,4,3,2) (1,5,3)(2,6,4)
(1,4)(2,5)(3,6) (1,3,5)(2,4,6) (1,2,3,4,5,6)
(每个数对应下一个数,接着再找下一个数的对应数,遇到循环加括号)
最后,根据Polya原理:
Answer=(2^6+2^1+2^2+2^3+2^2+2^1)/6=14
(2表示两种颜色,幂表示每种的括号数,除以6表示有6种)
Polya定理应用实例