Burnside引理和Pólya定理证明

记为这个元素上的置换群。

记为元素在作用下的等价类。那么对任意中的元素，都存在中的，使得。个人觉得这个E可以看作Equal。

记是的不动置换类。即对任意中的，都有。个人觉得这个Z可以看作Zero。

¶ 中每个元素的不动置换类的大小相等

证明：

假设是里的一个元素，那么存在，使得。

因为对中的每个置换，都有，所以也有。因为对每个p，都不同，所以每个的不动置换都对应一个的不动置换。由于这里和是对称的，所以也有每个的不动置换都对应一个的不动置换。所以和的不动置换是一一对应的。由于和具有普适性，所以中每个元素的不动置换类的大小都相等。

特别地，如果是交换群，即对其中的任意两个置换和都有，那么，即中每个元素的不动置换类都相等。很多常见的转动群都是交换群，比如先转90度再转180度和先转180度后转90度是一样的，这种情况下就有这个小结论（虽然我不知道有什么用2333

¶

思路：

将中的每个置换应用在上面，可以得到个结果。这些结果显然都是属于的。假如的话，那显然就有一些结果是重复的。那么中的每个元素在这个结果中出现的次数是不是一样的呢？直觉上是的，因为这个等价类里每个元素都是平等的。要证明它，我们只要证明将变成的置换与中的置换一一对应即可。

记为能将变成的置换的集合。那么任意中的置换，都有，所以对任意中的置换，都有。显然，固定时，对于每个，都是一个不同的置换，而根据定义，，所以每一个中的置换都对应一个中的置换。

因为，所以，所以。由于对每个，都不一样，所以每个中的置换都对应一个中的置换。

因此将变成的置换与中的置换一一对应，所以。

这个证明是我自己想出来的，如有雷同，纯属巧合。

¶ Burnside引理：等价类个数

其中就是在的作用下不动的元素的个数。把写成循环表示的话，就是其中的长度为1的循环的个数。

由于，所以的等价类里的元素的个数是。由于等价类里的每个元素的不动置换类的大小都相等，所以。也就是每个等价类里的不动置换数之和为定值。所以所有元素的不动置换数之和 ，。

这个相当于数每个元素的不动置换有几个，然后求和。可以换一个形式，求每个置换有多少个不动点，然后求和，结果是一样的，即。所以。

¶ Pólya 定理

其实这个就是Burnside引理的特殊情况。

Pólya 定理解决的问题：用种颜色对这个对象进行染色，一种染色方案不同当且仅当中只有一个置换（单位元）使得这个方案置换之后仍为这个方案，求染色方案数。

我们将每个对象染上不同颜色的方案视为一个元素，那么所有元素的集合记为，元素个数为个。我们就是要求这些元素中的等价类有多少个。注意Burnside引理中的置换群的目标集是染色方案的集合，而这里的的目标集是。

对于一个中的置换，将其用循环表示，那么一种染色方案在下不动当且仅当每个循环里的对象都是同色的，假设循环个数为，那么在染色方案的集合上对应的置换的不动点个数为。所以等价类个数。

由于和里的置换是一一对应的，所以，所以