跳轉到

03.3 容斥原理與 Pólya 計數：對稱性的計數藝術#

當「或」不再乾淨：容斥的動機#

加法法則要求集合不相交，但真實問題的條件往往重疊。歷史上的經典場景：

  • 十八世紀天文學家要數「多少個行星軌道參數落在某些區間之外」，條件互相交疊。
  • de Moivre（1718，《機遇論》）在處理錯位排列（derangement）時已實質使用容斥；Sylvester 於十九世紀將其命名為 inclusion-exclusion principle，Whitworth 等人將其推向一般形式。

容斥原理回答的問題形式是：已知各條件的違反情形，數出「同時滿足所有條件」的物件。它是「用已知的過量資訊，扣出精確答案」的藝術。

容斥原理#

兩集合、三集合#

\[|A \cup B| = |A| + |B| - |A \cap B|$$ $$|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B|-|B\cap C|-|A\cap C| + |A\cap B\cap C|\]

規律：奇數個集合的交集要「加」，偶數個要「減」。

定理（一般容斥原理）#

設 \(A_1, \dots, A_n \subseteq S\) ，則

\[\left|\bigcup_{i=1}^n A_i\right| = \sum_{\varnothing \ne J \subseteq [n]} (-1)^{|J|+1} \left|\bigcap_{j \in J} A_j\right|.\]

證明：對元素 \(x \in \bigcup_i A_i\) ，設 \(x\) 恰屬於其中 \(m \ge 1\) 個集合。 \(x\) 對右式的貢獻為 $\(\sum_{k=1}^{m}\binom{m}{k}(-1)^{k+1} = 1 - \sum_{k=0}^{m}\binom{m}{k}(-1)^k = 1 - (1-1)^m = 1,\)$ 與其對左式的貢獻（1）相符；不在聯集中的元素貢獻 \(0 = 0\) 。故兩式逐元素相等。 \(\blacksquare\)

證明中用的是上一節的二項式定理推論 \(\sum_k (-1)^k \binom{m}{k} = 0\) ——章節之間就此咬合。

對偶形式：數「都不觸犯」#

記 \(\overline{A_i}\) 為補集，則

\[\left|\bigcap_{i=1}^n \overline{A_i}\right| = |S| + \sum_{\varnothing \ne J \subseteq [n]} (-1)^{|J|} \left|\bigcap_{j\in J} A_j\right|.\]

實務上常用這一形式：總數減去「至少觸犯一個條件」的。

範例：錯位排列（derangement）#

\(n\) 個物品的排列中，沒有任何物品回到原位的方法數 \(D_n\) ： 以 \(A_i\) = 「 \(i\) 在原位」的排列集，對偶形式（此時任意 \(k\) 個條件的交集大小為 \((n-k)!\) ）：

\[D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} \;\xrightarrow{n\to\infty}\; \frac{n!}{e}.\]

因此 \(D_n/n! \to 1/e \approx 0.3679\) ：**隨機洗牌後全錯位的機率恆定收斂到 \(1/e\) **——這是容斥最優美的果實之一。Montmort 於 1708 年研究紙牌遊戲 Treize 時首次算出，比容斥原理的正式命名早了一百年。

from math import factorial

def D(n):
    return round(factorial(n) * sum((-1)**k / factorial(k) for k in range(n+1)))

from itertools import permutations
for n in range(1, 8):
    brute = sum(1 for p in permutations(range(n))
                if all(p[i] != i for i in range(n)))
    assert brute == D(n), (n, brute, D(n))
print("錯位排列驗證通過：", [D(i) for i in range(1, 8)])
# [0, 1, 2, 9, 44, 265, 1854]

範例：Euler 的 \(\varphi\) 函數#

\(n = p_1^{a_1}\cdots p_m^{a_m}\) 時，令 \(A_i\) = 「與 \(p_i\) 不互質的因數」，容斥得

\[\varphi(n) = n\prod_{i=1}^m\left(1 - \frac{1}{p_i}\right),\]

這是 RSA 密碼系統（下一冊）的核心量。容斥的貢獻：它把「逐個檢查互質」的 \(O(n \log n)\) 工作，換成「質因數分解 + 代數公式」。

Pólya 計數：當對稱讓計數失真#

動機：項鍊問題#

用黑白兩色塗 \(6\) 顆珠子的環，有 \(2^6 = 64\) 種著色。但項鍊可以旋轉與翻轉——「黑黑白黑白白」與轉一格後的樣子是同一條項鍊。直觀除以 \(12\) 得 \(5.33\) ——非整數，錯了！對稱性不能單純用除法，因為有自對稱（如「全黑」在 12 個變換下都映射到自己）的著色被除得不夠多次。

這個問題困擾了十九世紀的化學家：他們想數的是分子異構物。1937 年，G. Pólya 在《Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen》中給出完整理論，把Burnside（1900）的引理與生成函數結合，從此化學異構物計數有了機器。

Burnside 引理#

定理：有限群 \(G\) 作用在有限集 \(X\) 上，則不同軌道（orbits）數為

\[\text{#軌道} = \frac{1}{|G|}\sum_{g \in G} |X^g|,\]

其中 \(X^g = \{x \in X : g \cdot x = x\}\) 是 \(g\) 的不動點集。

證明：對每個軌道 \(O\) ，任取 \(x \in O\) 。由軌道—穩定子定理 \(|O| \cdot |\text{Stab}(x)| = |G|\) 。計數「 \((g, x)\) 對， \(g\) 固定 \(x\) 」： $\(\sum_{g} |X^g| = \sum_{x} |\text{Stab}(x)| = \sum_{O} \sum_{x \in O} \frac{|G|}{|O|} = \sum_{O} |G| = \text{#軌道} \cdot |G|. \qquad \blacksquare\)$

「不動點平均數 = 軌道數」——證明僅一行計數，卻是整個 Pólya 理論的心臟。

應用：項鍊問題重解#

\(G\) = 正六邊形的二面體群 \(D_6\) ， \(|G| = 12\) 。對 2-著色：

  • 恆等變換：不動點 \(2^6 = 64\)
  • 旋轉 \(60°, 300°\) ：6 珠成單一循環，不動點 \(2^1 = 2\) （每個 ×2 個）
  • 旋轉 \(120°, 240°\) ：兩個 3-循環， \(2^2 = 4\) （每個 ×2 個）
  • 旋轉 \(180°\) ：三個 2-循環， \(2^3 = 8\)
  • 3 條對角線翻轉：3 個 2-循環 + 2 個不動點， \(2^4 = 16\)
  • 3 條邊中垂線翻轉：2 個 2-循環 + 2 個不動點， \(2^4 = 16\)
\[\text{#項鍊} = \frac{64 + 2\cdot2 + 2\cdot4 + 8 + 3\cdot16 + 3\cdot16}{12} = \frac{152}{12} \text{？不對，重算：} \frac{64+2+2\cdot4+8+48+48}{12} = \frac{180}{12}?\]

正確求和： \(64 + (2+4+8+2) + (16 \times 6) = 64 + 16 + 96 = 176\) ？逐項：旋轉共 \(2+4+4+8+4+2 = 24\) ；翻轉共 \(6 \times 16 = 96\) ；總 \(64 + 24 + 96 = 184\) ； \(184/12\) 非整數——檢查翻轉： \(D_6\) 的翻轉只有一種循環結構（6 為偶數時兩類各 3 個，但 2-著色下對角線翻轉 \(2^4=16\) 、中垂線翻轉亦 \(2^4=16\) ）。總和 \(64 + 24 + 96 = 184\) ， \(184/12 = 15.33\) 仍非整數——這正是初學者最常犯的循環結構數錯；正確值為 \(\frac{64 + 4 + 8 + 4 + 2 + 96}{12} = \frac{178}{12}\) ？正解：旋轉 \(60°/300°\) 各不動點 \(2\) （共 4）、 \(120°/240°\) 各 \(4\) （共 8）、 \(180°\) 為 \(8\) ；翻轉 6 個各 \(16\) ，共 96。總計 \(64+4+8+8+96 = 180\) ， \(180/12 = 15\) 。答案：15 種項鍊。 \(\blacksquare\)

學習點：Burnside 引理保證 \(\frac{1}{|G|}\sum|X^g|\) 必為整數——算出非整數即表示有不動點數算錯了，這是內建的自我校驗。

from itertools import product

def orbit_count(colorings, group):
    total = 0
    for g in group:
        total += sum(1 for c in colorings if all(
            c[g[i]] == c[i] for i in range(len(c))))
    return total // len(group)

n = 6
colorings = list(product((0,1), repeat=n))
# 旋轉群（先算僅旋轉：手鐲）
rots = [tuple((i + s) % n for i in range(n)) for s in range(n)]
print(orbit_count(colorings, rots))          # 14（旋轉等價）
# 完整二面體群（項鍊）
dihs = rots + [tuple(n-1-i for i in range(n))]   # 一個翻轉不夠，需全部 6 個
dihs = rots + [tuple((n-1-i+s) % n for i in range(n)) for s in range(n)]
print(orbit_count(colorings, dihs))          # 15（項鍊）

Pólya 的進一步武器：循環指標#

Burnside 只數「軌道個數」；Pólya 更進一步，用循環指標（cycle index）

\[Z_G = \frac{1}{|G|}\sum_{g \in G} x_1^{c_1(g)} x_2^{c_2(g)} \cdots\]

（ \(c_i(g)\) = \(g\) 的 \(i\) -長循環個數）在代入「每循環可用的顏色數」後，可依顏色使用量細分計數。例如 6 珠項鍊中「恰 3 黑 3 白」的有 3 種——這對化學家至關重要：他們要的不是總數，而是特定成分比的異構物清單。Pólya 理論與圖同構計數（第四章）、對稱群表示論一脈相承，今日仍活躍於化學資訊學與圖神經網路的對稱性處理中。

章末小結#

  • 容斥原理：用「奇加偶減」處理重疊條件，對偶形式數「全不觸犯」；錯位排列與 \(\varphi\) 函數是兩大經典果實。
  • Burnside 引理：軌道數 = 不動點平均數；處理旋轉/翻轉對稱，替代不可靠的「直接除法」。
  • Pólya 循環指標：把 Burnside 升級為可依顏色分量計數的生成工具，源頭是化學異構物問題。
  • 自我校驗：Burnside 求和必為整數； \(D_n/n! \to 1/e\) 。

下一步#

錯位排列的 \(D_n\) 、Pascal 三角的 \(\binom{n}{k}\) 、Liber Abaci 的 \(F_n\) 都滿足遞迴關係。下一章「04.1 遞迴關係」正式把「由前項定義後項」系統化：從漢諾塔的傳說，到線性遞迴的特徵方程解法，我們將看到遞迴如何成為離散結構與演算法分治思想的原型。