首页 > 代码库 > 【转】Polya定理
【转】Polya定理
转自：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、或者是矩阵快速幂来解决。
【转】Polya定理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。