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)，即定义置换的操作符号为(+)
而要表示一个群，则所有置换必须满足的条件是
封闭性：任何置换的叠加所产生的置换也在原先的置换集合里
结合律：即对于三个置换(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 定理
( ext{Polya})定理，事实上就是对于每个置换，归纳了一下快速求出表观不变的元素个数的方法
也就是对于一个类似环序列的置换，置换之后表观不变，那么集合元素之间就存在一些相等关系，这些关系把集合元素之间的分成若干个循环，循环内的集合元素相同，通过求循环个数来快速求表观不变的元素个数
如对于环序列的问题，集合(S),置换(+x)的循环个数就是(gcd(i,|S|))
实际上，具体的问题直接在( ext{Burnside})引理的基础上自己归纳总结快速求的方法是最好的