03.1 計數原理：加法乘法法則與鴿籠原理的威力#

為什麼要「學會數數」？#

聽起來可笑——誰不會數數？但離散數學所謂的「計數」（counting / enumeration），指的是在不真正逐一列舉的情況下，預知有多少個物件。這個能力是整個計算機科學的地基：

• 演算法分析：一個排序法要處理 \(n!\) 種輸入排列，我們不可能窮舉，但可以「算出」 \(n!\) 有多大。
• 密碼學：金鑰空間有 \(2^{128}\) 種，暴力破解為何不可行？這是乘法法則的直接應用。
• 資料結構：雜湊表為何會碰撞？鴿籠原理保證：元素個數超過桶子數，碰撞必然發生。

計數的歷史幾乎與人類文明同壽，但系統化的計數理論遲至十七世紀才在 Pascal 與 Fermat 的通信（1654 年，賭徒 de Méré 提出的分賭金問題）中誕生。本章先建立兩條最基本的法則，再介紹一個看似幼稚、實則威力驚人的原理——鴿籠原理。

加法法則與乘法法則#

定義（任務與分解）#

一個「計數任務」是問：某集合 \(S\) 的元素個數 \(|S|\) 為何？計數的核心策略是分解：把 \(S\) 拆成較簡單的集合之聯集、笛卡兒積，再由法則組合。

定理（加法法則）#

若 \(S = S_1 \cup S_2\) 且 \(S_1 \cap S_2 = \varnothing\) ，則

一般化為容斥形式（下一節詳談）：

定理（乘法法則）#

若 \(S = S_1 \times S_2 \times \cdots \times S_k\) （所有選擇序列的集合），則

證明：對 \(k\) 歸納。 \(k=1\) 顯然。設 \(S' = S_1 \times \cdots \times S_{k-1}\) ，則 \(S = S' \times S_k = \bigsqcup_{s \in S'} \{(s, t) : t \in S_k\}\) ，這是 \(|S'|\) 個兩兩不相交、每個大小 \(|S_k|\) 的集合之聯集，由加法法則得 \(|S| = |S'| \cdot |S_k|\) 。 \(\blacksquare\)

範例#

例 1（密碼空間）：8 位密碼，每碼為大小寫字母或數字（62 種），則共有 \(62^8 \approx 2.18 \times 10^{14}\) 種。若每秒可試 \(10^{10}\) 次，破解平均需約 3 小時——這就是為何 8 位密碼已不夠，而 128 位金鑰（ \(2^{128} \approx 3.4 \times 10^{38}\) ）即使動用全球算力也遙不可及。

例 2（IPv4 位址耗盡）：IPv4 位址是 32 位元，共 \(2^{32} \approx 43\) 億個。乘法法則告訴我們上限就是這個數——而世界人口早已超過它，於是網際網路被迫走向 IPv6（128 位元， \(2^{128}\) 個位址，「足以為地球上每一粒沙分配一個」）。

from itertools import product

# 例 1 的驗證：小規模版——2 碼密碼，字元集 {a,b,c,1,2}
alphabet = "abc12"
total = len(alphabet) ** 2          # 乘法法則：25
brute = sum(1 for _ in product(alphabet, repeat=2))
print(total, brute)                 # 25 25

鴿籠原理#

敘述與直覺#

定理（鴿籠原理，Pigeonhole Principle；又稱 Dirichlet 抽屜原理）

若把 \(n+1\) 個物件放進 \(n\) 個盒子，則必有一盒至少含兩個物件。

一般形式：若把 \(N\) 個物件放進 \(k\) 個盒子，則必有一盒至少含 \(\lceil N/k \rceil\) 個物件。

證明（反證法）：若每盒至多 \(\lceil N/k \rceil - 1 < N/k\) 個，則總數 \(< k \cdot \frac{N}{k} = N\) ，矛盾。 \(\blacksquare\)

此原理由 Dirichlet 於 1834 年（他二十二歲時）首次用於數論證明，後人稱之為 Schubfachprinzip（抽屜原理）。它的力量在於：它證明某種物件「存在」，卻完全不告訴你如何找到它——這是「非建構性證明」的經典範式，也預告了二十世紀複雜度理論中 P 與 NP 的鴻溝。

經典應用#

例 3（生日悖論的反面）：367 人中必有兩人生日相同（一年至多 366 天）。這是直接套用。更有趣的是相反方向的問題：多少人才足以使「有兩人生日相同」的機率過半？答案是 23 人——這需要機率工具，但它顯示鴿籠原理給的是「保證」，而非「多半」。

例 4（同餘與無理數）：任意 \(n+1\) 個整數中，必有兩數之差被 \(n\) 整除。因為餘數只有 \(n\) 種（ \(0\) 到 \(n-1\) ），放入 \(n\) 個「餘數盒」中必撞盒。Dirichlet 正是用它證明：對任意無理數 \(\alpha\) 與任意 \(N\) ，存在 \(p, q \le N\) 使 \(|q\alpha - p| < 1/N\) ，從而開啟了丟番圖逼近理論。

例 5（匈牙利的愛多許傳統）：任意取 \(n+1\) 個不超過 \(2n\) 的相異正整數，必有兩數互相整除。 證明：把每個數寫成 \(2^k \cdot m\) （ \(m\) 為奇數）。不超過 \(2n\) 的奇數只有 \(n\) 個，但數有 \(n+1\) 個，故有兩數的奇數部分相同，則其中冪次較小者整除較大者。 \(\blacksquare\)

這類問題是 Erdős 及其學派每年舉辦的數學營（匈牙利自 1894 年的 KöMaL 傳統）的核心素材，培養了二十世紀組合學的半壁江山——鴿籠原理看似初等，卻是 Ramsey 理論（03.6 節）的直系祖先。

例 6（Ramsey 起點：六人派對）#

任取六人，必有三人互相認識，或三人互相不認識。 證明：固定一人 \(A\) ，其餘五人與 \(A\) 的關係分兩類（認識/不認識），由鴿籠原理至少三人同類，設 \(B, C, D\) 都認識 \(A\) 。若 \(B,C,D\) 中任兩人認識，得三人團；否則 \(B,C,D\) 三人互相不認識。 \(\blacksquare\)

記號上這是 \(R(3,3) \le 6\) ，我們將在第六章正式研究 Ramsey 數——「完全的無序是不可能的」。

from itertools import combinations
import random

def verify_r33(trials=10000):
    """隨機圖驗證：K6 的任意 2-著色邊必含同色三角形"""
    for _ in range(trials):
        edges = list(combinations(range(6), 2))
        color = {e: random.randint(0, 1) for e in edges}
        found = any(
            all(color.get(tuple(sorted((a, b)))) == c
                for a, b in combinations(tri, 2))
            for tri in combinations(range(6), 3)
            for c in (0, 1)
        )
        if not found:
            return False
    return True

print(verify_r33())   # True：從未找到反例

鴿籠原理的進階變形#

平均化原理：若 \(N\) 個物件總值為 \(T\) 分給 \(k\) 個盒子，則某盒至少得 \(T/k\) 。 應用：任意 10 個相異正整數皆 \(\le 100\) ，必有兩數之差在 \(1\) 到 \(9\) 之間？不對——正確版本：必有兩數，大者除以小者的商與餘數構成的某結構重複。這類變形訓練的是「設計合適的鴿籠」。

例 7（棋盤覆蓋）： \(8 \times 8\) 棋盤去掉對角兩格後，無法用 31 片 \(1 \times 2\) 多米諾覆蓋。 證明：多米諾必一黑一白；去掉的兩格同色，故剩 30 黑 32 白，黑白「鴿籠」不平衡。 \(\blacksquare\)

此題的深遠後續是 1962 年 Golomb 的五連方塊（pentomino）理論與 Conway 的演算法分析——「覆蓋問題」成為精確覆蓋演算法（Knuth 的 Dancing Links, 2000）的試金石。

例 8（單調子序列）：長度 \(n^2+1\) 的相異實數序列中，必有長 \(n+1\) 的單調（遞增或遞減）子序列（Erdős–Szekeres 定理，1935）。 證明：對每個位置 \(i\) 記 \((a_i, b_i)\) = 以 \(i\) 結尾的最長遞增／遞減子序列長。若所有 \(a_i, b_i \le n\) ，則只有 \(n^2\) 種數對，但位置有 \(n^2+1\) 個；又相異實數的數對必相異（若 \(i<j\) 且 \(a_i=a_j\) 則 \(x_i < x_j\) 迫使 \(a_j > a_i\) ，矛盾），鴿籠得證。 \(\blacksquare\)

Erdős–Szekeres 是「快樂末點問題」（happy ending problem）的副產品——他們原本想證：足夠多的平面點集中必有凸 \(n\) 邊形。這條線延伸到今日的極限組合學與 Szemerédi 正則性引理。

計數的極限：何時「數得出」不代表「數得完」#

計數法則告訴我們總量，但總量的大小本身就是工程訊息。這裡先建立尺度感，為 04.3 節的複雜度理論鋪路。

例 9（西洋棋的 Shannon 數）：西洋棋狀態數約 \(10^{43}\) ，合法賽局樹約 \(10^{120}\) （Shannon, 1950 的估計）。乘法法則（每步平均 35 種走法，對局 80 步）給出 \(35^{80} \approx 10^{123}\) ——即使每秒檢查 \(10^{18}\) 個局面，窮舉也要 \(10^{95}\) 倍宇宙年齡。計數證明了「蠻力下棋」不可行，於是人工智慧被迫發展啟發式搜尋（alpha-beta 剪枝、1997 年 Deep Blue 的評估函數、2017 年 AlphaZero 的神經網路）——技術路線由一個簡單的乘法決定。

例 10（雜湊表的必然碰撞）：把 \(n\) 個任意金鑰放進 \(m\) 個桶，由鴿籠原理，最滿的桶至少有 \(\lceil n/m \rceil\) 個元素。設計者無法消滅碰撞，只能管理它——這催生了鏈結法、開放定址與 1979 年 Carter–Wegman 的通用雜湊（universal hashing），後者用隨機化把「最壞鴿籠」變成「平均鴿籠」。

表格的最後一列說明：多項式尺度與指數尺度之間隔著「可行/不可行」的鴻溝——這條鴻溝的精確刻畫，正是 P vs NP 問題（04.3 節）的內容。

章末小結#

• 加法法則處理「或」（不相交聯集），乘法法則處理「且」（獨立選擇序列）；先分解、再組合，是所有計數的思維骨架。
• 鴿籠原理以反證證明存在性，是非建構性證明的範式；核心技巧是「設計鴿籠」——把問題的物件與分類方式對準。
• 歷史脈絡：Dirichlet（1834）→ Erdős–Szekeres（1935）→ Ramsey 理論 → 現代極限組合學。
• 工程意涵：雜湊碰撞、密碼空間、位址耗盡——上限由計數法則決定，而非工程努力。

下一步#

下一節「排列組合與二項式定理」將把今天的法則推到極致：當我們要數的是「選一堆」而非「排一排」時， \(P(n,k)\) 、 \(C(n,k)\) 與二項式定理登場——並回到 1202 年 Fibonacci 的 Liber Abaci，看兔子問題如何牽起遞迴（第四章）與組合學。