以前只是直接用了这两个式子。。今天才仔细看了证明。。【网上的真是难懂啊
我看的几个博客地址(各有优缺): 其实如果能懂的话 只看博客B就可以了
首先是一些置换群方面的定义和性质 博客A:http://blog.csdn.net/xym_CSDN/article/details/53456447
然后是burnside的证明 博客B:http://blog.csdn.net/gengmingrui/article/details/50564027
还有两个定理的式子和举例 博客C:http://blog.csdn.net/liangzhaoyang1/article/details/72639208
但是对于博客B,我看的时候遇到了几个问题
1、 设G={a1,a2,…ag}是目标集[1,n]上的置换群。
这里涉及到两个集合 一个是置换群,一个是目标集
目标集是一个状态集合, 在OI中举个例子 {
m个格子黑白染色, 状态数有2^m种, 每一种都是目标集中的一个元素,所以[1,n]实际上是[1,2^m];
而置换就可以理解为 两个状态之间的有向边。 比如1001这种染色状态,经过(1 2 3)(4)的置换后,变成0101
}
2、 c1(ak)是在置换ak的作用下不动点的个数,也就是长度为1的循环的个数(其实就是被置换ak置换过后位置不变的元素个数)
因为这句话,我之前一直误以为是不动点是: 比如置换a=(1 2 3)(4)中的那个4 。
然而实际上。比如1001这种染色状态,经过置换a(1 4)(2 3)的置换后,变成1001 ,所以‘1001’这个元素是置换a的一个不动点。
3、 轨道大小*稳定化子数=变换个数
这个的证明在博客A的最后有
。
。
。
贴一下来自博客C的式子:
Burnside引理:
对于一个置换f,若一个染色方案s经过置换后不变,称s为f的不动点。将f的不动点数目记为C(f),则可以证明等价类数目为所有C(f)的平均值。
百度百科的定义:
设G=a1,a2,…ag是目标集[1,n]上的置换群。每个置换都写成不相交循环的乘积。c1(ak)是在置换ak的作用下不动点的个数。通过上述置换的变换操作后可以相等的元素属于同一个等价类。若G将[1,n]划分成l个等价类,则:
Polya定理 :
polya定理实际上是burnside引理的具体化,提供了计算不动点的具体方法。
假设一个置换有k个循环,易知每个循环对应的所有位置颜色需一致,而任意两个循环之间选什么颜色互不影响。因此,如果有m种可选颜色,则该置换对应的不动点个数为m。
用其替换burnside引理中的C(f),即C(f)=m。得到等价类数目为:
其中|F|表示置换的数目,ki表示第i个置换包含的循环个数。