Burnside 引理 | Codeboy's Blog

形式陈述

有限群 $G$ 作用于有限集合 $X$ 时，轨道数满足

|X/G|=\frac1{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|.

证明可双重计数集合 $\{(g,x):gx=x\}$ ，或结合轨道—稳定子定理。公式需要对群元素而不是共轭类直接平均；若按共轭类分组求和，必须让代表项乘以对应类大小。

直觉

最清楚的证明是数同一个集合两次：考虑所有满足 $g\cdot x=x$ 的配对 $(g,x)$ 。按群元素分组得到不动点数之和；按对象分组得到稳定子大小之和，而轨道—稳定子关系保证每条轨道总共贡献恰好 $|G|$ 。平均不动点数因此不是经验公式，而是对轨道大小不均匀的精确校正。

例子与边界

计数项链时，旋转固定的着色数取决于旋转循环结构。仅除以 $|G|$ 通常错误，因为具有对称性的对象轨道更小。Burnside 给普通轨道数；带颜色权重的系统生成函数需 Pólya 理论。

用旋转识别四颗珠子的二色项链。恒等旋转固定 $2^4=16$ 种着色，转 $90^\circ$ 与 $270^\circ$ 各固定 $2$ 种，转 $180^\circ$ 固定 $2^2=4$ 种，因此轨道数为

\frac{16+2+4+2}{4}=6.

若直接用 $16/4$ 会得到 $4$ ，错误正来自全同色等具有非平凡稳定子的着色。把反射也纳入作用后，计数对象变成手链而不是项链，群必须随等价关系一起改变。

推论与应用

群作用把“视为相同”的对称变换形式化，轨道—稳定子定理解释每条轨道的权重，Burnside 引理则完成项链、图着色和化学异构体等有限对象的去重计数。进一步记录颜色库存或结构权重时，Pólya 枚举定理把每个置换的循环类型编码进生成函数。

参考资料

Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011，Chs. 1–4。
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009，Parts A–B。