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适用范围较小，遇到颜色有限制条件时，

     就应该用结合的方法， 用（方案总数） / 置换数 的思想，

                   用每种置换下找循环个数并 染色的方法求方案的技巧，

                   从而求出最后答案啊。