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\)。
其中所有本质不同的集合个数可以表示为：
\[ \frac{\sum_{置换x}所有集合中操作之后表观不变的个数}{置换个数} \]
显然也等于：
\[ \frac{\sum_{集合S}所有置换中操作之后表观不变的个数}{置换个数} \]
如对于 \(\{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}\) 引理的基础上自己归纳总结快速求的方法是最好的。