第 7 讲：Burnside 引理与对称计数

有限群 $G$ 作用于有限集 $X$ 时，Burnside 引理说轨道数等于不动点数的平均：

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

证明是对集合 $\{(g,x):g\cdot x=x\}$ 做两次计数：先按 $g$ 数得到右侧总和；先按 $x$ 数得到各稳定子大小之和，再在每条轨道内使用轨道—稳定子公式，恰好每条轨道贡献 $|G|$。

如果 $X$ 是对 $n$ 个位置进行 $q$ 色染色，置换 $g$ 把位置分成 $c(g)$ 个循环。一个染色被 $g$ 固定，当且仅当同一位置循环里的颜色都相同，因此

$$|\operatorname{Fix}(g)|=q^{c(g)}.$$

这条“先数位置循环，再取 $q$ 的幂”是染色题真正需要计算的部分。不要把置换的阶误当成循环数。

六珠手镯怎么数

若有 $q$ 种颜色，位置构成正六边形。手镯允许翻面，所以作用群是 $D_6$，共有 12 个元素。

• 恒等变换有 $q^6$ 个不动染色；
• 转 $60^\circ$ 或 $300^\circ$，六点成一个循环，各有 $q$ 个；
• 转 $120^\circ$ 或 $240^\circ$，有两个循环，各有 $q^2$ 个；
• 转 $180^\circ$，有三个循环，有 $q^3$ 个；
• 三条穿过对顶点的反射轴产生四个位置循环，各有 $q^4$ 个；
• 三条穿过对边中点的反射轴产生三个位置循环，各有 $q^3$ 个。

因此

$$N(q)=\frac{q^6+2q+2q^2+4q^3+3q^4}{12}.$$

$q=2$ 时是 13 种，$q=3$ 时是 92 种。若题目说项链且不允许翻面，就只使用六个旋转，答案会不同。

代入 $q=2$ 检查一次：

$$N(2)=\frac{64+4+8+32+48}{12}=13.$$

若只允许旋转，群变成 $C_6$，轨道数为

$$\frac{2^6+2\cdot2+2\cdot2^2+2^3}{6}=14.$$

手镯比项链多允许反射，因此等价关系更强，本质不同的方案数从 $14$ 降到 $13$，数量方向也符合直觉。

旋转的不动点可用最大公因数统一写

$n$ 个位置旋转 $k$ 格时，位置置换有 $\gcd(n,k)$ 个循环，所以固定染色数为

$$q^{\gcd(n,k)}.$$

于是只考虑旋转的 $n$ 珠项链数为

$$\frac1n\sum_{k=0}^{n-1}q^{\gcd(n,k)}.$$

反射则要分 $n$ 的奇偶：$n$ 为奇数时每条反射轴穿过一个顶点；$n$ 为偶数时又分“穿过两个对顶点”和“穿过两条对边中点”两类。课件的六珠例子正是偶数情形。

标准做题流程

1. 明确允许哪些对称，写出作用群；
2. 按循环型给群元素分类，而不是逐个重复计算；
3. 对每类代表元数位置循环，求不动对象数；
4. 乘上该类元素个数并求和；
5. 最后除以 $|G|$，并用“结果应为整数、对称越多轨道越少”做 sanity check。

如果颜色个数受到“恰好使用多少颗红珠”之类限制，固定数就不再是简单的 $q^{c(g)}$；仍然先看位置循环，但只能整段选择循环，再按长度凑所需数量。