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)}
$$