03.2 排列組合與二項式定理：從 Liber Abaci 到組合學#

從分賭金到兔子問題#

1600 年代之前，計數問題散落在賭桌、天文曆法與印度詩律學中。兩條歷史線在此交會：

1654 年，Pascal 與 Fermat 的通信：為解決賭徒 Chevalier de Méré 的「分賭金問題」，兩人各自發展出「樣本空間中等可能結果的計數」這一想法，機率論於焉誕生；其核心工具正是排列與組合。
1202 年，比薩的 Leonardo（綽號 Fibonacci）出版 Liber Abaci（計算之書）：把印度—阿拉伯數字系統引進歐洲，書中著名的兔子問題引出數列 \(1, 1, 2, 3, 5, 8, 13, \dots\) 。這條數列表面上屬於第四章的遞迴，但它與組合數有一個驚人的恆等式（見本章末），預告了「遞迴與組合是一體兩面」。

本章建立排列組合的標準工具箱，並以二項式定理作為壓軸——它是「計數與代數統一」的第一座橋。

排列：排一排有幾種？#

定義（k-排列）#

從 \(n\) 個相異物件中有序地選出 \(k\) 個的方法數，記 \(P(n,k)\) ：

\[P(n,k) = n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!}.\]

證明：乘法法則——第一個位置 \(n\) 種、第二個 \(n-1\) 種、……、第 \(k\) 個 \(n-k+1\) 種。 \(\blacksquare\)

當 \(k = n\) 時得全排列 \(n!\) 。Stirling 近似告訴我們其量級：

\[n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n,\]

這是演算法複雜度分析（04.3 節）的必備工具： \(n!\) 增長得比 \(2^n\) 還快，說明「窮舉所有排列」在 \(n \approx 15\) 之後即不可行。

有重複元素的排列#

\(n\) 個物件中有 \(n_1\) 個相同、 \(n_2\) 個相同……則相異排列數為多項式係數：

\[\binom{n}{n_1, n_2, \dots, n_m} = \frac{n!}{n_1!\,n_2!\cdots n_m!}.\]

直覺：先為每類物件在 \(n\) 個位置中「選位子」： \(\binom{n}{n_1}\binom{n-n_1}{n_2}\cdots\) ，展開即得上式。

組合：只選不排#

定義與定理（二項式係數）#

從 \(n\) 個相異物件中不計順序選出 \(k\) 個的方法數：

\[\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{k!\,(n-k)!}.\]

證明：每個 \(k\) -組合可產生 \(k!\) 個相異排列，而每個排列恰屬於一個組合；由「排列 = 組合 × 組內排列」除之即得。 \(\blacksquare\)

Pascal 恆等式#

\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.\]

證明（組合論證法，兩種觀點）：考慮是否包含第 \(n\) 個物件——包含則再從其餘 \(n-1\) 個選 \(k-1\) 個；不包含則從其餘 \(n-1\) 個選 \(k\) 個。兩案互斥且窮盡，由加法法則得證。 \(\blacksquare\)

此式即 Pascal 三角形（楊輝三角形，中國楊輝 1261 年《詳解九章算法》已載）的生成規則，也是下一章遞迴關係的第一個範例：一個計數量可由自身較小的情形遞迴定義。

恆等式的「組合證明」哲學#

以下兩式用代數（二項式定理）與組合論證皆可證，但組合證明揭示了「為什麼」：

Vandermonde 恆等式： \(\binom{m+n}{r} = \sum_{i=0}^{r}\binom{m}{i}\binom{n}{r-i}\) 。 組合證明：從 \(m\) 男 \(n\) 女中選 \(r\) 人，按男性人數分類求和。
** hockey stick（曲棍球杆）恆等式**： \(\sum_{i=k}^{n}\binom{i}{k} = \binom{n+1}{k+1}\) 。 組合證明： \(\binom{n+1}{k+1}\) 個選法按「選中者的最大編號」分類。

二項式定理#

定理#

對任意實數（此處取正整數 \(n\) ）：

\[(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k.\]

證明： \((x+y)^n\) 是 \(n\) 個因子 \((x+y)\) 相乘。展開式中每一項對應「從每個因子選 \(x\) 或 \(y\) 」的一種選擇；乘積含 \(k\) 個 \(y\) 的項，出現次數恰為「 \(k\) 個因子被選中提供 \(y\) 」的方法數，即 \(\binom{n}{k}\) 。 \(\blacksquare\)

代數證明（歸納）： \(n=1\) 顯然。設對 \(n\) 成立，則 \((x+y)^{n+1} = (x+y)\sum_k \binom{n}{k}x^{n-k}y^k\) ，合併 \(x^{n+1-k}y^k\) 的係數得 \(\binom{n}{k}+\binom{n}{k-1} = \binom{n+1}{k}\) （Pascal 恆等式）。 \(\blacksquare\)

兩種證明並陳正是本節的主題：計數觀點與代數觀點互為鏡像。

重要推論（代入特殊值）#

令 \(x=y=1\) ： \(\displaystyle\sum_{k=0}^n \binom{n}{k} = 2^n\) —— \(n\) 元集合的子集總數。
令 \(x=1, y=-1\) ： \(\displaystyle\sum_{k=0}^n (-1)^k\binom{n}{k} = 0\) ——奇偶大小子集一樣多，是容斥原理（下一節）的種子。
\(\displaystyle\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}\) （Vandermonde 的特例）——「二項式係數的平方和」這個乍看神秘的恆等式，翻譯成組合語言後一目了然。

from math import comb
from itertools import combinations

n = 5
S = list(range(n))

# 推論 1：子集個數 = 2^n
subsets = [c for k in range(n+1) for c in combinations(S, k)]
assert len(subsets) == 2**n

# 推論 3：Vandermonde
assert sum(comb(n, k)**2 for k in range(n+1)) == comb(2*n, n)

# 二項式定理數值驗證
x, y = 3, 2
lhs = (x + y)**n
rhs = sum(comb(n, k) * x**(n-k) * y**k for k in range(n+1))
assert lhs == rhs
print("all pass")

特殊排列：圓排列、項鍊與 Catalan 數#

圓排列： \(n\) 人圍桌而坐（旋轉視為相同）有 \((n-1)!\) 種——固定一人以打破旋轉對稱。若鏡射也視為相同（手鐲），則約 \(\frac{(n-1)!}{2}\) 種（ \(n \ge 3\) 時），嚴格值需下一節的 Burnside 引理處理對稱群。

Catalan 數： \(n\) 對括號的合法配對數

\[C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}.\]

證明（反射法）：總排列 \(\binom{2n}{n}\) 中，非法者（某前綴右括號過多）與「翻轉第一個違規點之後所有括號」的 \(\binom{2n}{n+1}\) 個 \(n+1\) 右括號序列一一對應，相減即得。 \(\blacksquare\)

Catalan 數出現在：二元樹形狀、三角形剖分、格路徑、堆疊輸出序列——Eugène Catalan 於 1838 年研究之，而歐拉早在 1751 年已為多邊形剖分算出。它是「組合結構等價」的教科書案例：數十種看似無關的問題共享同一計數。

與 Fibonacci 的意外重逢#

Liber Abaci 的兔子問題：一對兔子每月生一對新兔，新兔隔月開始生育， \(F_n\) 滿足 \(F_0=0, F_1=1, F_n = F_{n-1} + F_{n-2}\) 。組合學給出：

\[F_{n+1} = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}.\]

組合證明： \(F_{n+1}\) 計數「長度 \(n\) 、不含相鄰 1 的 0-1 序列」。恰含 \(k\) 個 1 時，需將 \(k\) 個 1 與 \(n-k\) 個 0 排列且 1 不相鄰，即把 \(k\) 個 1 插入 \(n-k\) 個 0 形成的 \(n-k+1\) 個縫隙中選 \(k\) 個，方法數 \(\binom{n-k+1}{k}\) 。對 \(k\) 求和即得（指標平移後與上式一致）。 \(\blacksquare\)

這個恆等式預告了第四章的主軸：遞迴數列常常有組合意義，而組合問題常常有遞迴結構——生成函數（04.2）就是把兩邊正式接線的機器。

from math import comb

def fib(n): 
    a, b = 0, 1
    for _ in range(n): a, b = b, a + b
    return a

for n in range(15):
    s = sum(comb(n-k, k) for k in range(n//2 + 1))
    assert s == fib(n+1), (n, s, fib(n+1))
print("Fibonacci = 對角線二項式係數之和：驗證通過")

章末小結#

\(P(n,k)\) 管「有序選取」， \(\binom{n}{k}\) 管「無序選取」，關係是 \(P(n,k) = k!\binom{n}{k}\) 。
Pascal 恆等式是計數與遞迴的第一座橋；Vandermonde、曲棍球杆等恆等式示範「組合證明」的解釋力。
二項式定理把代數展開翻譯成計數；令變數取特殊值即得子集計數與容斥的種子。
Catalan 數與 Fibonacci 恆等式顯示：同一個數可以統御許多看似無關的結構。

下一步#

當計數對象重疊（「會法文或會德文的人」）或帶對稱（項鍊、骰子、分子結構）時，單純的排列組合不夠用。下一節「容斥原理與 Pólya 計數」登場：前者由 de Moivre 開端、經 Sylvester 與 Whitworth 定型，後者用群論馴服對稱性——這是十九世紀組合學向抽象代數借力的轉捩點。