burnside引理简单证明

前言：由于博主时不时会忘记这个定理以及它是咋证明的，所以为了方便就干脆自己写一个放 $blog$ 上面

现在给出集合 $\text{X}$ ，设 $\text G$ 是其置换群， $\text C$ 是其着色集，且 $\text G$ 作用在 $\text C$ 下

那么定义 $G(c)=\{f:f\in \text G,f\times c=c\},C(f)=\{c:c\in \text C,f\times c=c\}$

然后有一个显然的推论: 设 $c$ 是 $\text C$ 中的一种着色，那么 $|\{f\times c:f\in \text G\}|=\frac{|\text G|}{|G(c)|}$ ,证明显然

然后就能证明 $Burnside$ 引理了：

$$\begin{aligned} \sum\limits_{f\in \text G}|C(f)|=&\sum\limits_{c\in \text C}|G(c)|\\ \sum\limits_{f\in \text G}|C(f)|=&\sum\limits_{c\in\text C}\frac{|\text G|}{与c等价的着色数}\\ \sum\limits_{f\in\text G}|C(f)|=&|\text G|\sum\limits_{c\in\text C}\frac{1}{与c等价的着色数}\\ 由于在一个等价类中&每种着色的贡献都是\frac{1}{与c等价的着色数}\\ 所以\sum\limits_{f\in \text G}|C(f)|=&|G|\times N(\text G,\text C)\\ N(\text G,\text C)=&\frac{\sum\limits_{f\in \text G}|C(f)|}{|\text G|} \end{aligned}$$

得证