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