Burnside引理和Polya定理 Burnside引理和Polya定理
因为今天看到了BZOJ1004用到了Burnside引理，此前也听过大牛说过，现在就学习一下。
有一个置换群的概念：就是一些置换的集合（置换群就是一个将置换作为元素的群）
关于置换可以看1004上的实例
Burnside引理
定义：设(G={a1,a2,…ag})是目标集[1,n]上的置换群。每个置换都写成不相交循环的乘积。
(c_1(a_k))是在置换(a_k)的作用下不动点的个数。
即是长度为1的循环的个数(其实就是被置换置过后位置不变的元素个数)。
通过上述置换的变换操作后可以相等的元素属于同一个等价类。
若G将[1,n]划分成L个等价类，则：(等价类个数为：等价类个数为：L=frac{1}{|G|}sum_{i=1}^gc_1(a_i))
证明见（http://blog.csdn.net/gengmingrui/article/details/50564027）
Pólya定理
题目还没涉及到，先不总结