【转】Polya定理

时间:2023-03-08 16:24:50

转自:http://endlesscount.blog.163.com/blog/static/82119787201221324524202/

Polya定理

首先记Sn为有前n个正整数组成的集合,G为Sn的置换群,C为Sn的着色集。那么我们等于是要求C中有多少种着色方案是不等价的。定义两种着色等价的概念:如果对于在C中的两种着色c1、c2,存在置换f使得f*c1=c2,那么c1和c2就是等价的。要想求不等价着色的个数,我们要先证明一个定理,即:
      Burnside定理:设G(c)={f|f属于G,f*c=c},C(f)={c|c属于C,f*c=c}。那么对于每一种着色c,那么与c等价的着色数=|G|/|G(c)|。
      证明:首先可以证明G(c)为Sn的一个置换群。那么对于任意的f*c=g*c,可知f的逆*g属于G(c),所以g={f&h|h属于G(c)}。那么在|g|=|G(c)|。所以与c等价的着色数=|G|/|G(c)|。这样我们就得到了Burnside定理。
我们现在就用Burnside定理来得到最终的答案。先设N(G,C)为C中不等价的着色数。我们考虑这样一个计数过程:求所有的(f,c)满足f*c=c的总对数。那么我们有:
                                  sum{|G(c)|}(对于每一个c属于C)=sum{|C(f)|}(对于每一个f属于G)。
      由Burnside定理可对等式左边进行替换,得到:
                                  sum{|G|/与c等价的着色数}(对于每一个c属于C)=sum{|C(f)|}(对于每一个f属于G)。
      如果我们把右边的式子展开的话,等价类相互合并和就把分母给消去了,最后得到的就是不等价类的个数:
                                  N(G,C)*|G|=sum{|C(f)|}(对于每一个f属于G)。
这个公式就是Polya定理。即:N(G,C)=1/|G|*sum{|C(f)|}(对于每一个f属于G)。那么对于任意的带变换的着色计数问题,我们都可以把变换用置换群表示出来,然后对于每一个置换群考虑其|C(f)|的个数,这可以通过递推、DP、或者是矩阵快速幂来解决。