跳轉到

8.2 鴿籠原理與生成函數應用#

概念說明#

鴿籠原理（Pigeonhole Principle）：n+1 隻鴿子飛進 n 個籠子，必有一籠至少兩隻。它看似平凡，卻是計算機科學中「存在性證明」的最強短路徑：證明雜湊表必有碰撞、證明任意 367 人中必有同生日、證明任何壓縮演算法必有某些輸入會變大（n+1 種輸入塞進 n 種輸出，必有兩個撞在一起——這直接推出「無損壓縮不可能壓縮所有檔案」）。鴿籠的進階版「廣義鴿籠原理」更精確：N 個物件放進 k 個籠子，必有某籠至少 ⌈N/k⌉ 個。它把「必存在」升級成「存在多少」，在負載均衡與雜湊分析中天天用到。

生成函數（generating function）則是組合數學的顯微鏡。給數列 a₀, a₁, a₂, …，定義其生成函數 A(x) = Σ aₖxᵏ。魔法在於：數列的捲積對應多項式的乘法。於是：

  • 「從 3 種物品中選，第一種最多 2 個、第二種不限、第三種偶數個，共幾種重量組合？」→ 乘開 (1+x+x²)(1+x+x²+…)(1+x²+x⁴+…)，xⁿ 的係數就是答案。
  • 遞迴關係可以轉成代數方程：費氏數列的生成函數是 x/(1−x−x²)，部分分式分解後直接讀出封閉公式（Binet 公式）。

鴿籠回答「存不存在」，生成函數回答「有多少、怎麼算」——兩者一靜一動，構成組合推理的基本工具箱。

演算法步驟#

用生成函數解「組合計數」問題的流程：

  1. 把每種「選擇」翻譯成一個多項式因子（每個可取數量對應一項）。
  2. 全部因子相乘（多項式乘法，係數用 Python 大整數精確累加）。
  3. 讀出目標次數的係數；或先符號化簡得到封閉式。
  4. 驗證：對小規模用暴力枚舉（8.1 節）比對。

鴿籠式論證的演算法應用（生日悖論式的碰撞偵測）：

  1. 值域有 N 個可能值、樣本超過 √N 個 → 必有碰撞（機率過半）。
  2. 據此設計尋找碰撞的最少查詢次數 O(√N)（Pollard ρ 分解法在 3.3 節正是此原理）。

Python 程式碼範例#

import itertools, math, random
from fractions import Fraction

# --- 例 1：生成函數做組合計數 ---
def poly_mul(p, q):
    """多項式乘法：係數列表表示"""
    r = [0] * (len(p) + len(q) - 1)
    for i, a in enumerate(p):
        for j, b in enumerate(q):
            r[i + j] += a * b
    return r

# 問題：1 元、5 元、10 元各若干，湊 30 元有幾種法？
coin1 = [1] * 31            # 1 元：0~30 個
coin5 = [1 if v % 5 == 0 else 0 for v in range(31)]
coin10 = [1 if v % 10 == 0 else 0 for v in range(31)]
gf = poly_mul(poly_mul(coin1, coin5), coin10)
ways_gf = gf[30]
print("生成函數：湊 30 元的方法數 =", ways_gf)

ways_bf = sum(1 for a in range(31) for b in range(7) for c in range(4)
              if a + 5*b + 10*c == 30)
print("暴力枚舉驗證             =", ways_bf)
assert ways_gf == ways_bf

# --- 例 2：費氏數列的封閉公式由生成函數導出 ---
def fib_genfn(n):
    """F(0)=0, F(1)=1，生成函數 x/(1-x-x^2) 的係數"""
    f = [0, 1]
    for k in range(2, n):
        f.append(f[-1] + f[-2])
    return f

phi = (1 + 5**0.5) / 2
print("Binet 公式 F(30) =", round(phi**30 / 5**0.5),
      "vs 遞迴", fib_genfn(31)[30])

# --- 例 3：生日悖論（鴿籠的機率版） ---
def birthday_collision_prob(n, days=365):
    p_no = Fraction(1, 1)
    for i in range(n):
        p_no *= Fraction(days - i, days)
    return 1 - p_no

for n in [10, 23, 40, 60]:
    print(f"{n:>2} 人中有人同生日的機率 ≈ {float(birthday_collision_prob(n)):.4f}")

# 雜湊碰撞的實測：值域 10^6，抽約 sqrt(N) 個看碰撞率
M = 10**6
def collision_rate(m, domain, trials=1000):
    hit = 0
    for _ in range(trials):
        seen = set()
        for _ in range(m):
            v = random.randrange(domain)
            if v in seen:
                hit += 1
                break
            seen.add(v)
    return hit / trials

print(f"值域 {M} 抽 {int(M**0.5)} 個，碰撞率 ≈ "
      f"{collision_rate(int(M**0.5), M):.2f}（理論約 0.39）")

複雜度分析#

生成函數的多項式乘法：兩個 d 階多項式相乘 O(d²)，串乘 m 個因子 O(m·d²)；用 numpy.convolve 可降到 C 層速度，超多項次可用 FFT（NTT）做到 O(d log d)——這與 4.3 節多項式求根共享同一套底層。讀單一係數還有更快的路：組合數問題常有封閉式（如「非負整數解 x₁+…+xₖ=n 的計數 = C(n+k−1, k−1)」），避免任何乘法。鴿籠原理本身 O(1)——它的價值在推理而非計算。生日悖論的工程含義值得背下來：值域 N 中出現碰撞約需 √N 個樣本，所以 64 位元雜湊在約 2³² ≈ 43 億筆時碰撞率過半，這是 GUID、雜湊表 sizing、密碼學安全位數（見第 2 章）的共同設計公式。

練習#

  1. 用生成函數計算「丟兩顆骰子，點數和為 n 的方法數」數列（n = 2..12），並與 (x+x²+…+x⁶)² 的係數比對。
  2. 證明並驗證：任取 11 個不超過 20 的相異正整數，必存在兩數其中一個整除另一個（提示：把每數寫成 2^a·奇數，對奇數用鴿籠）。用程式枚舉所有 C(20,11) 種取法確認命題為真。
  3. 實作 Catalan 生成函數 C 滿足 C = 1 + xC² 的係數遞推（cₙ = Σcᵢc_{n−1−i}），算出前 10 項並與 8.3 節的公式 Cₙ = C(2n,n)/(n+1) 對照。