跳轉到

08.2 有限群與 Burnside 引理：對稱性的計數工具#

0. 導言：當「相同」變成數學問題#

多少種方式可以把一條項鍊串上 6 顆珠子、只用黑白兩色？暴力答案是 \(2^6 = 64\) 。但「順時針轉 2 格」的項鍊與原來是同一條——「相同」不是相等，而是在某個變換群之下等價。把這個模糊的直覺變成可計算的公式，就是本章的任務。

歷史脈絡：Burnside 引理（burnside's lemma，正確名稱或許該叫「Cauchy–Frobenius 引理」：Cauchy 1845 年、Frobenius 1887 年均已證明，Burnside 1897 年在教科書中引用並因此得名——命名錯誤本身就是一則「前因後果」的教訓）。它是 Pólya 計數定理（1937）的核心零件，後者徹底改變了化學（異構物計數）、組合學與圖論（圖的同構類計數）。

驅動關係：Lagrange/Cauchy 的排列群（08.1 前因）→ 群作用的概念化 → orbit–stabilizer 定理 → Burnside 引理 → Pólya 定理 → 現代組合枚舉與化學資料庫。同時，07.2 證明 Fermat 小定理時「乘 \(a\) 是排列」的手法，正是群作用的第一次亮相。

1. 群作用：讓群「動起來」#

定義 1.1（群作用）#

群 \(G\) 作用在集合 \(X\) 上，是指映射 \(G \times X \to X\) ， \((g, x) \mapsto g \cdot x\) ，滿足：

  1. \(e \cdot x = x\) （單位不動）；
  2. \(g \cdot (h \cdot x) = (gh) \cdot x\) （相容性）。

每個 \(g\) 因此給出 \(X\) 上的一個雙射（逆映射為 \(g^{-1}\) ），故有同態 \(G \to \mathrm{Sym}(X)\) （Cayley 定理的推廣視角：每個群作用都是一個排列表示）。

定義 1.2（軌道與固定子）#

對 \(x \in X\) ：

  • 軌道（orbit）： \(Gx = \{g \cdot x \mid g \in G\}\) ；
  • 固定子（stabilizer）： \(G_x = \{g \in G \mid g \cdot x = x\}\) 。

定理 1.3（軌道–固定子定理，orbit–stabilizer）#

\(G\) 有限， \(x \in X\) ，則

\[|Gx| = \frac{|G|}{|G_x|}, \qquad \text{即} \quad |G| = |G_x| \cdot |Gx|.\]

證明：對每個 \(y \in Gx\) ，選一個把 \(x\) 送 to \(y\) 的 \(g_y\) 。考慮陪集 \(g_y G_x\) ：若 \(h \in g_y G_x\) ，則 \(h \cdot x = g_y(k \cdot x) = g_y \cdot x = y\) ，故 \(g_y G_x\) 的所有元素都送 \(x\) to \(y\) ；反過來若 \(g \cdot x = y\) ，則 \(g_y^{-1}g \in G_x\) ，即 \(g \in g_y G_x\) 。所以「把 \(x\) 送 to \(y\) 的元素全體 = 陪集 \(g_y G_x\) 」，大小 \(|G_x|\) （Lagrange）。不同 \(y\) 的陪集互不相交（否則 \(g_{y'}^{-1}g_y \in G_x\) 導致 \(y = y'\) ）。因此 \(|G| = \sum_{y \in Gx} |G_x| = |Gx| \cdot |G_x|\) 。 \(\blacksquare\)

結構對照：這個證明與 Lagrange 定理（08.1 定理 2.5）同構——都是「陪集等大、互斥、覆蓋」三步曲。事實上 Lagrange 是取 \(X = G/H\) （陪集集合）的特例。同一個證明骨架，支撐兩大定理。

定理 1.4（軌道是等價類）#

關係 \(x \sim y \iff \exists g: y = g \cdot x\) 是等價關係，其等價類恰為軌道。因此 \(X\) 被軌道劃分： \(|X| = \sum_{\text{軌道 } O} |O|\) 。

# 正方形的旋轉群作用在 4 個頂點上
import itertools

def compose(p, q):
    """排列合成：先做 q 再做 p"""
    return tuple(p[i] for i in q)

C4 = [((0,1,2,3), "e"), ((1,2,3,0), "r90"), ((2,3,0,1), "r180"), ((3,0,1,2), "r270")]
X = list(itertools.permutations(range(4)))   # 頂點的排列

orbit_of = {}
for x in X:
    orb = frozenset(p for p, _ in C4 for p in [compose(p, x)])
    orbit_of.setdefault(orb, []).append(x)

print(f"頂點 {X[0]} 的軌道大小: {len(orbit_of[frozenset(compose(p, X[0]) for p, _ in C4)])}")
print(f"軌道總數: {len(orbit_of)}")   # 等價類 = 軌道

2. Burnside 引理#

定理 2.1（Burnside 引理 / Cauchy–Frobenius 引理）#

有限群 \(G\) 作用在有限集 \(X\) 上，則軌道個數（即本質不同的組態數）為

\[N = \frac{1}{|G|} \sum_{g \in G} |\mathrm{Fix}(g)|,\]

其中 \(\mathrm{Fix}(g) = \{x \in X \mid g \cdot x = x\}\) 。平均來說，「被多少變換固定住」就等於「有多少種本質不同的東西」。

證明（雙重計數）。計算集合

\[S = \{(g, x) \mid g \in G,\ x \in X,\ g \cdot x = x\}\]

的大小，兩個方向各算一次：

  1. 按 \(g\) 分組： \(|S| = \sum_{g \in G} |\mathrm{Fix}(g)|\) 。
  2. 按 \(x\) 分組： \(x\) 貢獻的對數為 \(|G_x|\) ，而由 orbit–stabilizer 定理 \(|G_x| = |G|/|Gx|\) 。所以 $\(|S| = \sum_{x \in X} \frac{|G|}{|Gx|} = |G| \sum_{x \in X} \frac{1}{|Gx|}.\)$ 同一軌道內每個 \(x\) 的 \(|Gx|\) 相同（都等於該軌道大小），故 \(\sum_{x \in O} \frac{1}{|O|} = 1\) ，每個軌道總共貢獻 1： $\(|S| = |G| \cdot (\text{軌道個數}).\)$

兩式相等，除以 \(|G|\) 即得。 \(\blacksquare\)

證明思想：又是「雙重計數」——07.2 證 Fermat 小定理用「乘 \(a\) 重排 \(\{1,\dots,p-1\}\) 」，08.1 證 Lagrange 用「陪集劃分」，本章用「 \((g,x)\) 配對矩陣按行按列各數一次」。交換求和順序是組合數學最強的萬用鑰匙。

範例 2.2（項鍊問題）#

6 顆珠子、2 色、旋轉群 \(C_6\) 作用在 \(X = \{黑白\}^6\) （ \(|X| = 64\) ）：

旋轉 \(\mathrm{Fix}(g)\) 說明
\(e\) \(2^6 = 64\) 全部不動
轉 1、5 格 \(2\) 六位循環 → 必須全同色
轉 2、4 格 \(2^2 = 4\) 3 週期：每 3 格同色
轉 3 格 \(2^3 = 8\) 2 週期
\[N = \frac{64 + 2 + 4 + 4 + 8 + 2}{6} = \frac{84}{6} = 14.\]

不經 Burnside，這個 14 很難不重不漏地數出來。

def count_bracelet(colors, n, rotations):
    """旋轉等價下的手環數（Burnside 引理）"""
    total = 0
    for k in range(rotations):                 # 旋轉 k 格
        fixed = 0
        for cfg in itertools.product(colors, repeat=n):
            # 旋轉 k 格後仍相同 ⟺ cfg 是週期 gcd(n, k) 的重複
            d = math.gcd(n, k)
            if all(cfg[i] == cfg[(i + k) % n] for i in range(n)):
                fixed += 1
        total += fixed
    return total // rotations

import math
print(count_bracelet("BW", 6, 6))   # 14 ✓
print(count_bracelet("BW", 4, 4))   # 6  （四珠手環）

3. 進階：循環指數與 Pólya 定理（概述）#

Burnside 引理逐個 \(g\) 計數 \(\mathrm{Fix}(g)\) 。Pólya（1937）把它系統化：若 \(g\) 作用在 \(n\) 個位置上分解成 \(c_1\) 個 1-循環、 \(c_2\) 個 2-循環…，則固定 \(g\) 的著色數為 \(m^{c(g)}\) （ \(m\) 色時），因為每個循環內必須同色：

\[\mathrm{Fix}(g) = m^{c(g)}, \qquad c(g) = \text{$g$ 的循環個數}.\]

項鍊例： \(c(e)=6, c(r^{\pm1})=1, c(r^{\pm2})=2, c(r^3)=3\) ，代入：

\[N = \frac{1}{6}\left(2^6 + 2 \cdot 2^1 + 2 \cdot 2^2 + 2^3\right) = 14. ✓\]

若再加上翻轉（二面體群 \(D_6\) ，12 個元素）則考慮「可翻面的手環」，答案變 13。作用群越大，等價類越少——對稱性越多，本質不同的組態越少。

範例 3.1（正方形頂點二著色， \(D_4\) 作用）#

# D4 作用在 4 個頂點的 2-著色上：16 種塗法 → 本質不同有 6 種
def cycle_count(perm):
    seen, cycles = set(), 0
    for i in range(len(perm)):
        if i not in seen:
            cycles += 1
            j = i
            while j not in seen:
                seen.add(j); j = perm[j]
    return cycles

D4 = [(0,1,2,3), (1,2,3,0), (2,3,0,1), (3,0,1,2),      # 旋轉
      (3,2,1,0), (1,0,3,2), (0,3,2,1), (2,1,0,3)]      # 翻轉
m, n = 2, 4
N = sum(m ** cycle_count(p) for p in D4) // len(D4)
print(N)   # 6

4. 應用版圖#

領域 問題 作用群 結果
化學 苯環取代物的異構物數 \(D_6\) Pólya 1937 的原始動機
圖論 \(n\) 點標號圖的同構類數 \(S_n\) 作用在邊集合 A000088 數列
遊戲 魔方陣、積木、拼圖本質型態 對稱群 謎題設計
編碼 等價碼字分類 換座標群 碼的重量枚舉子

圖計數例子：3 個頂點的簡單圖有 \(2^{\binom{3}{2}} = 8\) 個標號版本，但在 \(S_3\) 作用下只有 4 個同構類（空圖、1 邊、2 邊、三角形）—— \(S_3\) 的循環指數給出 \(\frac{1}{6}(2^3 + 3 \cdot 2^2 + 2 \cdot 2^1) = 4\) 。

5. 章末小結#

定理 敘述 證明核心
orbit–stabilizer \(\lvert G\rvert = \lvert G_x\rvert \cdot \lvert Gx\rvert\) 陪集分解（同 Lagrange）
軌道劃分 \(X = \bigsqcup\) 軌道 等價關係
Burnside $N = \frac{1}{ G
Pólya $N = \frac{1}{ G

核心因果鏈：排列群（Cauchy）→ 群作用 → 軌道/固定子 → orbit–stabilizer（Lagrange 的推廣）→ Burnside（雙重計數）→ Pólya（循環指數）→ 組合枚舉的工業化。

一個容易被忽略的深意：Burnside 引理把「等價類個數」這個離散整數，表達成「平均固定點數」這個可以逐元素計算的量。這種「全域量 = 局部量平均」的哲學，在指標定理、Möbius 反演、 甚至傅立葉分析中反覆出現。

6. 下一步#

到目前為止，我們的群都是有限的，計算模型是「排列、枚舉、數數」。但如果把視野拉向「一切可計算的對象」——字串、程式、語言——計數會被不可計算性取代：有些問題連「有沒有演算法」都沒有答案。這就是 08.3 的主題：從 Turing 1936 的圖靈機（可計算性的極限）、Chomsky 1956 的語言層級（語法的四種機器）、到 DFA 與 Kleene 星號、以及 Regular 語言的 Pumping lemma——我們將從「數對稱」轉向「算能力」，為全書的計算理論篇揭開序幕。