polya定理-创新互联
polya定理的内容好多啊，虽然公式很简单，但是前面关于群论与置换群的内容就要理解一会儿了。。
详细的话就看下组合数学，也可看下这个课件http://wenku.baidu.com/view/3dc7027602768e9951e738ca.html
下面就说一下自己的见解：
1）关于群与置换群：
群：就是经过二元运算后还满足 封闭性、结合律、单位元存在、逆元存在性质的集合就是群。。
这里的二元运算很广泛，当然也包括+-*/什么的。。。
举个例子：a，b属于R集，那么，那么a*b当然也属于R了。。那么R对这个运算当然是一个群了
置换群：实际上就是排列的变化，如
这个就是一个排列到另外一个排列的变化就是一个置换。。a1->ai1
a2-->ai2.........
2)Burnside引理:
实际上就是把所有的方案列出来，对于每一个置换，把置换下不变的方案数统计出来，累加起来
最后除以置换总数。。
3）polya定理：
就是burnside的优化而已，因为所有的进行一次，时间复杂度o（nsp）太高了，所以得优化
方法：
把每种置换写成若干个不想交循环的乘积，比如（1 2 3 4） ->(2 1 4 3) 这个置换就可以写成 (1 2)*(3 4),那么求本质不同的时候，只要每个循环
里涂一种颜色（想想为什么，因循环内部必须一样，这样在该置换下才是一种方案啊，不然就变成多种了），这样的话就变成2（循环的个数）个位置的染色，所以该置换 下为M^2中方案本质不同的（M为颜色数）
所以就变成了求每种置换下的循环个数，然后每种对应M^T个方案，T为循环个数，其他跟burnside一样。。
4）polya与burnside联系：
两者本质相同，结合起来用是解题是最需要的，因为单纯的burnside复杂度太高，polya适用范围较小，遇到颜色有限制条件时，
就应该用结合的方法， 用（方案总数） / 置换数 的思想，
用每种置换下找循环个数并 染色的方法求方案的技巧，
从而求出最后答案啊。
当前标题：polya定理-创新互联
当前路径：http://6mz.cn/article/dghjis.html