Burnside & Polya
Burnside & Polya
前置知识
首先，要引入一些群论的概念，但是也不需要太懂
一个集合$S$，我们定义两种相同，即表观相同和本质相同
称对于集合的一种操作为置换
每一个对于集合的置换都是一种广义的对称，关于操作$x$对称的两个集合本质相同
即对于置换$S$得到$S’$，则$S$,$S’$关于这个置换对称，同时$S,S’$本质相同
群就是一些集合和一些操作(称作置换)的组合
对于一个$n$元序列$p_i$，我们认为它是我们的集合，我们定义序列的对称是可以通过首尾相接乘环之后相同
如有$S=\{2,1,1\},S’=\{1,2,1\}$
我们可以说$S,S’$向右移动1个位置这个置换对称
我们暂且定义这个操作为$+1$，即定义置换的操作符号为$+$
而要表示一个群，则所有置换必须满足的条件是
封闭性：置换$x$可以通过其他置换叠加得到，同时任何置换的叠加所产生的置换也在原先的置换集合里
结合律：即对于三个置换$a,b,c,(a+b)+c=a+(b+c)$
单位元：存在一个置换$e$对于其他所有的置换满足$e+a=a+e=a$
逆元：即对于每个置换$a$，存在置换$b$使得置换$a+b=e$
对于上面提到的环序列问题
置换集合是$\{+0,+1,\cdots,+n-1\}$，两个置换叠加的结果是要对于$n$取模的，所以显然满足上面的性质
Burnside
对于一个群$G$
其中所有本质不同的集合个数可以表示为
显然也等于
如对于$\{1,1,2\}$，三种置换之后得到$\{1,1,2\},\{1,2,1\},\{2,1,1\}$
感性证明如下：
考虑每一种本质不同的集合$S$
对于$S$执行每一种置换$x$，会产生若干个表观相同的置换集合
这些集合的总大小就是总的置换个数
对于每一个操作集合$Set$对应的表观元素$T$,$Set$本身是封闭的
存在$|Set|$种置换可以从$S$得到$T$
同时也存在$|Set|$种置换满足$T$置换之后表观不变
因为可以先对$T$执行一个$Set$中置换的逆置换，然后再分别叠加以置换集合中所有的置换
根据群的封闭性，叠加之后的置换集合等价于原先的置换集合，而原先的置换集合里有$|Set|$个会得到$T$
所以一个本质不同的集合被分散到这些集合里，最后一共还是被算了置换个数次
Tips:
这里一定要注意的是，即便没有元素对于置换$x$对称，也必须要算进总的置换个数里
举个例子：
如果有$2$个$0$和$2$个$1$组成的环序列，手玩一下知道方案数是$2$
实际的置换是$+0,+1,+2,+3$
对称的个数是$6,0,2,0$
实际上把这个问题扩展到$n$个，就会发现奇数的置换都是不存在对称的
(甚至只保留偶数的置换同样满足群的性质),但是也必须计算$2n$个置换,因为环序列的置换就是$2n$个，不会因为具体情况不存在而改变
Polya 定理
$\text{Polya}$定理，事实上就是对于每个置换，归纳了一下快速求出表观不变的元素个数的方法
也就是对于一个类似环序列的置换，置换之后表观不变，那么集合元素之间就存在一些相等关系，这些关系把集合元素之间的分成若干个循环，循环内的集合元素相同，通过求循环个数来快速求表观不变的元素个数
如对于环序列的问题，集合$S$,置换$+x$的循环个数就是$\gcd(i,|S|)$
实际上，具体的问题直接在$\text{Burnside}$引理的基础上自己归纳总结快速求的方法是最好的