本文最后更新于:2020年4月20日 中午

Burnside引理

AABB为有限集合,XX表示所有从AABB的映射集合(着色方案集合)。X/GX/G表示XX所有元素的轨道的集合(去掉重复),即GG作用在XX上产生的所有等价类的集合,XgX^{g}表示XX中在gg作用下的不动元素,则有

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

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

Polya计数公式

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

Xg=mc(g)|X^{g}|=m^{c(g)}

替换一下,就得到了:

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


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

树形dp好题 上一篇
数论初级魔法大赏 下一篇