参考资料
- TGSteven 的博客（那篇博客现在已经被TGSteven删掉了）
- wikipedia: Burside’s lemma
轨道 orbit
我们记$X$中的元素$x$在置换群$G$作用下的轨道为：
那么，$x$的轨道中的所有元素一定和$x$属于同一个等价类，并且不在$x$的轨道中的元素一定不与$x$属于同一个等价类。比如说，$2$种颜色的珠子串长度为$4$的项链，允许旋转，那么0101和1010都是0101的轨道中的元素。又比如给$2\times 2$的方格涂色，允许进行旋转，那么$\begin{matrix} 1& 0 \ 0 & 1\end{matrix}$的轨道中的元素有$\begin{matrix} 1& 0 \ 0 & 1\end{matrix}$和$\begin{matrix} 0& 1 \ 1 & 0\end{matrix}$。一个元素的轨道，就是它在$G$的作用下能够得到的元素组成的集合。
定义一个集合$X$的轨道是所有元素的轨道的集合，记为$X/G$。实际上，一个轨道就是我们之前提到的一个等价类。
不动点与稳定子集
定义一个置换$g$的不动点为：
定义$X$中的一个元素$x$的稳定子集为：
证明orbit-stabilizer theorem（口胡）
orbit-stabilizer theorem：一个元素的轨道中的元素数量与这个元素的稳定子集的大小的乘积等于置换群中置换的数量，即$\forall x\in X,| G\cdot x|\cdot |G_x| = |G|$
限于本人的水平，以下内容是在阅读了若干资料之后用口水话胡的。
对于一个元素$x$，我们可以将$G$中的置换分为两类，一类是$G_x$中的，一类是不属于$G_x$的。那么对于$x$的轨道中的所有元素，这个“分类”的结果是一样的。即对于一个置换$g$，如果$g\cdot x=x$，那么$\forall x’\in G\cdot x,g\cdot x’=x’$；如果$g\cdot x\not= x$，那么$\forall x’\in G\cdot x,g\cdot x’\not =x’$。
一个置换作用在$x$上，得到的结果一定在$x$的轨道中。那么任意一个置换，它可以表达为：$x$的轨道中的一个元素在$G_x$中的一个置换下得到的结果。并且，“$x$的轨道中的一个元素在$G_x$中的一个置换下得到的结果”和“$G$中的一个置换”，这两者是一一对应的关系。因此，$|G\cdot x|\cdot |G_x|=|G|$。
这也就是为什么我们要求置换构成群：这个定理成立的前提是置换结合满足封闭性。如果从$x$到达“$x$的轨道中的一个元素在$G_x$中的一个置换下得到的结果”这个置换不在$G$中，那么在计数的时候就会出错。
证明Burnside Lemma
Burnside Lemma：一个集合$X$在置换群$G$作用下的等价类（轨道）的数量，等于$G$中每一个置换的不动点的数量的平均值。即$|X/G|={1\over |G|}\sum_{g\in G}|X^g|$
首先，显然有
考虑某一个轨道$G\cdot x$，轨道中的每一个元素的轨道都是$G\cdot x$，每一个元素对$(1)$的贡献是$|G_x|$，所以每一个轨道对$(1)$的贡献就是$|G\cdot x|\cdot |G_x| = |G|$（轨道稳定定理）。也就是说每个轨道对$(1)$的贡献是一样的。
由于轨道的数量为 $|X/G|$，故而 $\sum_{g\in G}|X^g| = |G||X/G|$，即$\frac{1}{|G|} \sum_{g\in G} |X^g| = |X/G|$。