Burnside 引理

强壮的 Burnside 引理，羸弱的 Polya 定理。

轨道—稳定子定理

给定群 $G$ 对集合 $X$ 的群作用。

定义群作用下 $g\in G$ 的不动点集合为 $Fix(g)=\{x|gx=x\}\subseteq X$ 。

定义群作用下 $x\in X$ 的不动群元素集合为 $Stab(x)=\{g|gx=x\}\subseteq G$ 。

易得 $Stab(x)$ 是封闭的，也就是说， $Stab(x)$ 为 $G$ 的一个子群。因此 $Stab(x)$ 也被称为稳定子群。

定义元素 $x\in X$ 的轨道为 $Orb(x)=\{gx|g\in G\}$ 。

那么就有轨道—稳定子定理：

$$|G|=|Stab(x)|\times|Orb(x)|$$

这是拉格朗日定理 $|G|=|H|\times|\{gH|g\in G\}|$ 的直接推论。

因为其中的 $H$ 显然对应于 $Stab(x)$ ，也就是说，我们只需证明 $|Orb(x)|=|\{gH|g\in G\}|$ 就行了。

不妨取 $g_1x,g_2x \in Orb(x),g_1x\ne g_2x$ ，由左陪集的性质（若两个元素 $a,b$ 满足 $a^{-1}b\in H$ ，即 $a\sim b$），任意两个等价的元素的左陪集相同。又因为 $g_1x\ne g_2x$ ，那么 $g_1^{-1}g_2x\ne x$ ，于是 $g_1^{-1}g_2\notin Stab(x)$ ， $g_1Stab(x) \ne g_2Stab(x)$ ，于是 $|Orb(x)|=|\{gH|g\in G\}|$ 。

这就是轨道—稳定子定理。

Burnside 引理

Burnside 引理远远强于 Polya 定理，不知道 Polya 有什么用处。

Burnside 引理：

$$|\{Orb(x)\}|\times|G|=\sum_{g\in G}|Fix(x)|$$

在一般的计数问题中， $G$ 对应着本质相同的方案之间的置换， $X$ 对应着所有的方案。

接下来考虑证明。

如果我要对满足 $gx=x$ 的 $(g,x)$ 计数，那么如果固定 $g$ 看 $x$ ，就有方案数：

$$\sum_{g\in G}|Fix(g)|$$

同时，如果我固定 $x$ 看 $g$ 就有：

$$\sum_{x\in X}|Stab(x)|=\sum_{x\in X}\frac{|G|}{|Orb(x)|}=|G|\sum_{x\in X}\frac{1}{|Orb(x)|}$$

由于 $Orb(x)$ 是一个对 $G$ 的划分（由左陪集的性质容易看出），那么必然有 $|Orb(x)|$ 个 $x$ 贡献 $\frac{1}{|Orb(x)|}$ 。总和就是 $|\{Orb(x)\}|$ 。

其实考群论和考 Burnside 没有什么区别，因为群论的题目没有什么可以考。 Polya 哪里凉快哪里呆着去。