Burnside解释

发布时间 2023-12-12 20:10:07作者: zhuzc_114514

burnside引理

|X/G|= 1/|G| * ∑ |X^g|

(不会打mkd)

有一个A集合,一个B集合,X集合为所有A到B的映射(就是对于A的每个元素选择一个B集合的元素,比如给“正方体的面选颜色”,面是A集合,颜色是B集合,所有方案为集合X)

G为A的置换群,包含若干对A的元素的置换操作

左边:

|X/G|表示在置换群G(的影响)下(即可以对A中的元素 按置换群中的操作 置换),产生的本质不同的集合(X/G)的大小。

右边:

选取G中的每一个置换操作g,计算其贡献,最后求平均值(即除以 置换总个数,也就是|G|)

对于每一个置换操作,其贡献为“不动点数量”——也就是A经过 一次此置换操作 后(一次多次其实一样),B集合不变 的方案 总数

比如给染好色的正方体旋转(即给A集合进行一次置换操作),如果旋转前后的颜色(从固定视角看)(B集合)相同,则算1贡献;如果不同,则不算贡献