Burnside引理与Polya计数公式

Burnside引理

设$A$和$B$为有限集合，$X$表示所有从$A$到$B$的映射集合（着色方案集合）。$X/G$表示$X$所有元素的轨道的集合（去掉重复），即$G$作用在$X$上产生的所有等价类的集合，$X^{g}$表示$X$中在$g$作用下的不动元素，则有

$|X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|$

$X$中非等价的着色数等于在$G$中的置换作用下保持不变的着色的平均数！

Polya计数公式

考虑置换$g$可以分解成若干不相交的循环置换的乘积，那么每个循环内的颜色必须相同，才能在$g$的作用下染色不变，设颜色一共$m$种，置换$g$的循环分解中的循环个数为$c(g)$，那么在$g$作用下着色不变的着色数为：

$|X^{g}|=m^{c(g)}$

替换一下，就得到了：

$|X/G|={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}$