Burnside · 平均不动点数

Burnside 引理与本质不同的染色

本系列前面的计数都默认对象带标号：位置 $1$ 与位置 $2$ 是两个不同的位置，交换它们得到的两种安排分别记数。 $n$ 颗珠子的项链用 $k$ 种颜色染，按这个口径共 $k^n$ 种；但项链可以转动，转一圈能重合的两种染色在实物上是同一条。本页处理的是对称之后本质不同的染色有多少种。

1 · 旋转下的等价类

把珠子的位置按 $0$ 到 $n-1$ 编号，旋转一格即把位置 $i$ 的珠子送到位置 $i+1 \bmod n$ 。 $n$ 个旋转（含保持不动的那个）在复合下构成循环群 $C_n$ ，它以置换位置的方式作用在全部 $k^n$ 个染色上，这种作用称作群作用（group action）。两个染色等价当且仅当某个旋转把其一变成另一，等价类即轨道（orbit），要数的就是轨道个数。

轨道大小不一律等于 $n$ 。 $n = 6$ 两色时，染色 $101010$ 转两格就回到自身，它的轨道只含 $3$ 个染色。把 $x$ 保持不动的群元素全体记作 $\mathrm{Stab}(x)$ ，它是 $G$ 的子群，且满足

|\mathrm{Orb}(x)| \cdot |\mathrm{Stab}(x)| = |G|

即轨道大小整除群的大小，缺口由稳定化子补上。这条等式（orbit–stabilizer theorem）是 §2 论证的支点。

2 · 不动点数的平均

按轨道逐个数是行不通的，因为轨道的大小参差不齐。Burnside 引理换一个角度：不看轨道，只看每个群元素各自固定住多少个对象。记 $g$ 的不动点（fixed point）集合为 $\mathrm{Fix}(g)$ ，即被 $g$ 原样保持的那些染色。

定理 2.1（Burnside 引理）有限群 $G$ 作用在有限集 $X$ 上时，轨道个数等于各群元素不动点数的平均： $\#\text{轨道} = \frac{1}{|G|} \sum_{g \in G} |\mathrm{Fix}(g)|$

证明数满足 $g \cdot x = x$ 的配对 $(g, x)$ 共有多少个，记作 $N$ 。按 $g$ 分组，第 $g$ 组有 $|\mathrm{Fix}(g)|$ 个配对，故 $N = \sum_{g \in G} |\mathrm{Fix}(g)|$ 。按 $x$ 分组，第 $x$ 组有 $|\mathrm{Stab}(x)|$ 个配对，故 $N = \sum_{x \in X} |\mathrm{Stab}(x)|$ 。对固定的一条轨道，其中每个 $x$ 都有 $|\mathrm{Stab}(x)| = |G| / |\mathrm{Orb}(x)|$ ，而轨道内的 $|\mathrm{Orb}(x)|$ 是同一个数，于是整条轨道对第二种数法的贡献是 $|\mathrm{Orb}| \cdot |G| / |\mathrm{Orb}| = |G|$ 。每条轨道贡献 $|G|$ ，所以 $N = |G| \cdot \#\text{轨道}$ 。两个表达式相等，除以 $|G|$ 即得。∎

同一批配对按两种方式分组求和，是组合恒等式与双计数里那套双计数手法用在群作用上的结果。

3 · 项链的计数公式

Burnside · (1/n)Σⱼ k^gcd(j,n)

旋转 $j$ 格的置换把 $n$ 个位置分成 $\gcd(j, n)$ 个循环，每个循环长 $n / \gcd(j, n)$ 。一个染色被它固定，当且仅当每个循环内部同色，各循环之间互不牵连，故这个置换的不动点数是 $k^{\gcd(j,\, n)}$ 。代入引理并按 $\gcd$ 的取值 $d$ 合并同类项——满足 $\gcd(j, n) = d$ 的 $j$ 恰有 $\varphi(n/d)$ 个——得到项链公式：

\frac{1}{n} \sum_{j=0}^{n-1} k^{\gcd(j,\, n)} = \frac{1}{n} \sum_{d \mid n} \varphi(n/d)\, k^{d}

$n$ 为素数时右式化简为 $(k^n - k)/n + k$ ，其中除法整除的事实等价于费马小定理。若翻转也算等价，群换成 $2n$ 阶的二面体群 $D_n$ ，反射的不动点数按 $n$ 的奇偶分两种情形；正方体六面染色则把群换成 $24$ 个旋转，做法不变。

图 3-1 · 项链染色的轨道与旋转不动点表。可调珠子数

n

与颜色数

k

，单击任一代表元查看它整条轨道的成员，侧栏高亮的是固定住该代表元的旋转，末两行给出不动点总数与平均。

警示 · 归一化去重要用最小旋转表示，排序不是轨道的口径。把染色数组排序后当键去重，等于把任意位置置换都算作等价，数出来的是多重集个数： $n = 6$ 、 $k = 3$ 时排序法给 $28$ ，最小旋转法与公式都给 $130$ ，而 $28 = C(8, 6)$ 正是三色六珠的多重集数。

暴力枚举只在小规模上可用。本页的 orbitsBrute 逐个生成 $k^n$ 个染色再按最小旋转表示去重，node v26.6.0 实测： $n = 10$ 、 $k = 3$ 的 $59049$ 个染色约 $0.1$ 秒， $n = 11$ 、 $k = 4$ 的 $4194304$ 个染色约 $4$ 秒， $n = 12$ 、 $k = 4$ 的 $16777216$ 个染色约 $32$ 秒。图 3-1 的枚举上限取在 $65536$ ，越过这一档只显示公式值。

4 · 参考文献

Burnside's lemma. Wikipedia. 轨道计数公式的陈述、证明与项链算例。https://en.wikipedia.org/wiki/Burnside%27s_lemma
Group action. Wikipedia. 群作用、轨道与稳定化子的定义及其计数关系。https://en.wikipedia.org/wiki/Group_action
Necklace (combinatorics). Wikipedia. 循环群与二面体群下的项链与手镯计数。https://en.wikipedia.org/wiki/Necklace_(combinatorics)