一些群论前置知识

拉格朗日定理

在一个有限群上,设是它的子群,必有的约数。

可以考虑用陪集证明:

对一个元素就是关于的左陪集。因为逆元存在,所以

考虑两个元素,如果,则不妨设

那么,则

因为,所以,所以

那么所以的不同左陪集无交,设其个数为,则,得到的约数。

同时也得到一个子群的不同陪集数

轨道-稳定化子定理

对一个置换群和一个元素,设中使保持不变的置换构成的集合,通过中的变换能变换到的位置集合。

首先证明是一个子群:

,所以,即

的一个子群。

再考虑所有置换,因为,所以

因为所有不同的组成的集合即为,所以所有不同的左陪集数量也为

由拉格朗日定理即得到

Burnside 引理

对一个关于染色方案的置换群,对于任意两个元素,如果存在一个使得,则称属于同一个等价类。每个等价类称作一个轨道。

Burnside 引理提供了一种方法求的轨道数:所有置换的不动点个数的算术平均。

证明:

对于每一个元素,假设它对答案贡献,那么每一个轨道累加得到贡献

由轨道-稳定化子定理

Pólya 定理

Pólya 定理是Burnside 引理的具体化。

假设现在有种颜色。

如果一个关于位置的置换个轮换,因为不动点经过置换后仍是自身,所以每个轮换的元素的颜色相同。对于这个置换来说,有中染色方法使得存在这样一个不动点。

那么用这个来枚举得到

值得注意的是,里的置换是关于所有染色方案的置换,里的置换是关于染色位置的置换,

里的置换是阶置换,里的置换是阶置换,中的染色在的幂中体现。