正文
组合数学--Polya 原理及典型应用
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
Redfield-Polya （Pólya enumeration theorem，简称PET）定理是组合数学理论中最重要的定理之一．自从 1927 年 Redfield 首次运用 group reduction function 概念，现在称之为群的循环指标（circle index of a group），至今 60 多年来，他在许多实际计数问题上得到了广泛的应用，它以置换群为理论基础，与生成函数有机地结合在一起，揭示了一类具有组合意义的计数的规律性．
抽象地说在一集合内，定义了一个等价关系，人们往往关心由这个等价关系所决定的等价类的数目，Refield-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种）
非常神奇的东西，不知道为什么，也不清楚具体的定义是什么（看也看不懂），反正这个典型就是这么牛的被解掉了！
参考：
http://blog.sina.com.cn/s/blog_4aba84bd010005rc.html
http://www.cnblogs.com/hankers/archive/2012/02/16/2354397.html
