Burnside引理与Polya计数公式

Burnside引理

设和为有限集合,表示所有从到的映射集合(着色方案集合)。表示所有元素的轨道的集合(去掉重复),即作用在上产生的所有等价类的集合,表示中在作用下的不动元素,则有

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

Polya计数公式

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

替换一下,就得到了: