跳轉到

1.2 排列組合與樣本空間#

本章導言#

Pascal 與 Fermat 的信件雖然解決了賭金分配，但真正讓機率計算成為「可批量生產」的技術的，是計數的理論：樣本空間的觀念、排列與組合的公式。本節將把 1654 年的啟發式計算鑄成現代語言——樣本空間、事件、古典機率，並介紹從中國《易經》到 Leibniz 的組合思想史。

樣本空間與事件：機率的舞台#

一切機率計算始於一個明確定義的集合。給定隨機試驗，其樣本空間 \(\Omega\) 是所有可能結果的集合，事件是 \(\Omega\) 的子集。以擲兩顆骰子為例：

\[ \Omega = \{(i, j) : i, j \in \{1, 2, 3, 4, 5, 6\}\}, \qquad |\Omega| = 36. \]

「點數和為 7」的事件 \(A = \{(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)\}\) ， \(|A| = 6\) 。古典機率定義（Laplace, 1812《機率的分析理論》正式表述）：

\[ P(A) = \frac{\text{有利結果數}}{\text{等可能結果總數}} = \frac{|A|}{|\Omega|}. \]

Laplace 對這個定義有清醒的自覺，他在定義後立即警告：古典定義是循環的——「等可能」本身就是機率概念。這個循環要到 1933 年 Kolmogorov 公理化（5.3 節）才被形式地打破：機率被定義為滿足公理的任意測度，等可能性只是眾多特例之一。

乘法原理：計數的發動機#

若一件事分 \(k\) 個步驟完成，第 \(i\) 步有 \(n_i\) 種選法，則總方法數為 \(n_1 n_2 \cdots n_k\) 。這條乘法原理看似顯然，卻是全部組合數學的地基。它的歷史可追溯到相當早：

文獻 年代 內容
《易經》卦象 先秦 \(2^6 = 64\) 卦，即六爻二值系的乘法原理
Ramon Llull 13 世紀 以組合輪盤生成概念組合， \(n(n-1)\) 型配對
Levi ben Gerson（Gersonides） 1321 《計算之書》嚴格證明排列數 \(n!\) 與組合數公式
Cardano 1550 《算術精要》給出 \(\binom{n}{2}\) 與骰子組合計算
Pascal 1654 《論算術三角形》證明 \(\binom{n}{k}\) 的遞迴與性質
Leibniz 1666 《論組合術》，少年之作，立志「把推理化為計算」

值得特別記述的是猶太數學家 Levi ben Gerson（1288–1344）：他在 1321 年就對「從 \(n\) 個不同物中取 \(r\) 個的排法數」給出了歸納法式的嚴格證明，比歐洲主流早了兩百多年。而 Pascal 的《論算術三角形》（Traité du triangle arithmétique，1654，與賭金通信同期完成）則首次系統證明 \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) ，並把三角形與賭博問題連結——這是組合數學與機率論的第一次正式握手。

排列與組合的三大公式#

排列（permutation）：從 \(n\) 個相異物中排 \(r\) 個成一列（有序）：

\[ P_n^r = n (n-1) (n-2) \cdots (n-r+1) = \frac{n!}{(n-r)!}. \]

組合（combination）：從 \(n\) 個相異物中取 \(r\) 個（無序）：

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

兩者的關鍵差別在於「順序是否有意義」： \(r\) 個物的排列方式有 \(r!\) 種，故 \(\binom{n}{r} = \dfrac{P_n^r}{r!}\) 。歷史上這個關係的釐清並不容易：十七世紀的作者常混用「變化」（variation）、「組合」（combination）等詞，直到 de Moivre 在 1711–1718 年《機遇原理》（Doctrine of Chances）中才建立了清晰的術語系統。

重複組合：取 \(r\) 個可重複、不計順序的物件數為 \(\binom{n+r-1}{r}\) ，可由「隔板法」（stars and bars）證明。三個基本公式合起來，構成古典機率計算的完整工具箱。

二項式定理：代數與計數的會師#

Pascal 三角形的每一列就是二項式係數，Newton（牛頓，1643–1727） 在 1665 年（瘟疫年間，與發明流數法同期）將其推廣到非整數指數：

\[ (1+x)^\alpha = \sum_{k=0}^{\infty} \binom{\alpha}{k} x^k, \qquad |x| < 1, \]

其中 \(\binom{\alpha}{k} = \frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}\) 。這是數學史上第一個無窮級數展開的嚴格成果，直接為微積分（見《微積分》教材 5.2 節）與後世的動差生成函數（2.3 節）鋪路。組合數由此獲得雙重身份：既是計數工具，又是代數展開的係數——這種「同一個物件、兩種意義」的現象，將反覆出現在機率論中（特徵函數、動差、分布）。

錯排問題：組合推理的經典深度#

錯排（derangement）： \(n\) 封信全部裝錯信封的方法數 \(D_n\) 。由容斥原理可得：

\[ D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}, \qquad \lim_{n\to\infty} \frac{D_n}{n!} = \frac{1}{e} \approx 0.3679. \]

這個問題由 Pierre Rémond de Montmort（1678–1719） 在 1708 年以「相遇遊戲」（jeu de rencontre）提出，de Moivre 與 Nicholas Bernoulli 隨後給出完整解答。它的重要性在於示範了容斥原理（inclusion-exclusion）這個超越「窮舉」的高級計數技術，並首次讓常數 \(e\) 從機率計算中自然湧現——機率論與分析學的第一次深度聯姻。

一個具體例題#

例題 1.2.1：一副 52 張撲克牌發 5 張，求「正好 3 張同點數（三條）且不是四條、不是兩對」的機率。

解：樣本空間為 \(\binom{52}{5} = 2{,}598{,}960\) 個等可能組合。「三條」的結構：三張同點數 + 一張不同點數 + 一張再另一個不同點數（且不與前兩張同點數成對，否則成為葫蘆）。

步驟分解（乘法原理）：

  1. 選三張同點數的點數： \(13\) 種；從該點數 4 張中取 3 張： \(\binom{4}{3} = 4\) 種；
  2. 剩餘兩張必須不同點數且不同於三條的點數：從 12 個點數選 2 個： \(\binom{12}{2} = 66\) ；
  3. 每個選定點數取 1 張： \(4 \times 4 = 16\) 。

故有利組合數為：

\[ 13 \times 4 \times 66 \times 16 = 54{,}912. \]

機率為：

\[ P(\text{三條}) = \frac{54{,}912}{2{,}598{,}960} \approx 0.02113 \approx \frac{1}{47.3}. \]

歷史註記：這正是 1663 年 Cardano 與 1711 年 de Moivre 處理的同類問題。注意分解時必須互斥且完備地刻畫事件——漏掉「排除葫蘆」的條件就會把 \(\binom{13}{1}\binom{4}{3}\binom{12}{2}16\) 多算進葫蘆的情況，這是初學者最常見的錯誤，也是 Montmort 在《機遇分析》(1708) 中特別警告的陷阱。

歷史啟示#

  • 計數先於機率：先有「數得出」的可能結果，才有「比得出」的機率。組合數學是機率論的第一具引擎。
  • 術語的澄清是學科成熟的標誌：從 Montmort 到 de Moivre 的術語整理說明，一門科學需要先「說清楚」才能「算正確」。
  • 同一公式的多重身份： \(\binom{n}{k}\) 同時是計數、代數係數與（後來的）二項分布機率——概念的複用是數學力量的來源。
  • 循環定義的警覺：Laplace 對古典機率「等可能」循環性的自覺，預告了公理化革命的必要性。

與其他章節及領域的關聯#

  • 1.1 節：賭金分配中的「枚舉等可能序列」即本節樣本空間方法的原型。
  • 1.3 節：條件機率 \(P(A|B) = P(AB)/P(B)\) 建立在樣本空間的子集語言上。
  • 3.1 節：二項分布 \(P(X=k) = \binom{n}{k} p^k q^{n-k}\) 的 \(\binom{n}{k}\) 即本節組合數的機率化身。
  • 2.1 節：當樣本空間無限（如 \([0,1]\) 區間），「數個數」失效，需改用測度——這是從古典機率到現代機率的分水嶺（Bertrand 悖論是經典警示）。
  • 資訊科學：排列組合是演算法複雜度分析、密碼學金鑰空間估計的基礎工具。
  • 統計力學：Boltzmann 的熵公式以微觀狀態數（組合計數）為核心，是「組合數學驅動物理」的二十世紀範例。

練習#

  1. 用乘法原理證明 \(n\) 個相異物的排列數為 \(n!\) ，並模仿 Levi ben Gerson 的歸納法嚴格證明。
  2. 一個班有 20 名學生，選 5 人組成委員會且其中甲、乙兩人不可同時入選，求選法總數。
  3. 求擲 5 顆骰子「點數和為 12」的方法數（提示：先考慮不設上限的隔板法，再用容斥原理扣除某顆骰子超過 6 的情形）。
  4. 證明 \(\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n\) （用二項式定理與組合論證各證一次）。
  5. 思考題：Bertrand 悖論（「圓內隨機弦長超過內接正三角形邊長」的機率因取弦方式不同而得 \(\frac{1}{3}, \frac{1}{2}, \frac{3}{4}\) ）暴露了古典機率定義的什麼缺陷？

進階研讀：樣本空間思想的五個深化場景#

場景一：樣本空間的選擇即建模。同一試驗可用不同樣本空間描述：擲兩顆骰子可用有序對 \(\Omega_1\) （36 點）或點數和 \(\Omega_2 = \{2,\ldots,12\}\) （11 點）。關鍵規則：只有在「樣本點等可能」的空間上才能用古典定義。 \(6\) 是兩種骰子序的「和」這件事提醒我們：粗化的空間不再等可能。這個原則在統計的充分性理論（8.2 節）中將以精確形式重現。

場景二：容斥原理與 Bonferroni 不等式。 \(|A_1 \cup \cdots \cup A_n|\) 的交錯和級數，其部分和交替給出上界與下界（Bonferroni 不等式，1936）。這使容斥從「精確公式」升級為「近似工具」：取前幾項即可估計「至少發生一個」的機率，誤差方向已知。這在系統可靠度計算（元件失效並集）中是標準技術。

場景三：占位問題與生日悖論。 \(n\) 個人分入 365 天，至少兩人生日相同的機率為 \(1 - \frac{365!}{(365-n)! \, 365^n}\) 。 \(n = 23\) 時已超過 \(\frac{1}{2}\) ——直覺再次敗給計算。占位模型（balls into bins）是雜湊碰撞分析、負載均衡演算法的基礎，Montmort 1713 年的「贈券收集問題」是其姊妹問題。

場景四：Catalan 數與投票問題。序列 \(\binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}\) 計數「路徑不越過對角線」的結構。其機率化身是投票問題（Bertrand, 1887）：開票過程中甲票數始終領先的機率為 \(\frac{a-b}{a+b}\) 。這類「部分和路徑」問題在 6.1 節隨機漫步與 7.2 節布朗運動中將成為主角（反射原理）。

場景五：從組合到生成函數。Euler 1748 年《無窮分析引論》確立：一個數列可以打包成一個冪級數（生成函數），計數問題於是化為代數運算。機率論的版本就是動差生成函數與機率生成函數（2.3 節）——擲骰子點數和的分布，可以由 \(G(z) = \left(\frac{z + z^2 + \cdots + z^6}{6}\right)^k\) 的係數一次讀出。組合數學的「打包技術」在機率論中獲得了最成功的應用。

名詞速查表（本節出現的核心術語）#

  • **樣本空間 \(\Omega\) **：隨機試驗全部可能結果的集合。
  • 事件： \(\Omega\) 的子集；古典機率下機率為 \(|A|/|\Omega|\) 。
  • 古典機率定義：Laplace 1812 年表述的「有利除以等可能」。
  • 乘法原理：分步驟事件的選法數相乘。
  • 排列 / 組合： \(P_n^r = \frac{n!}{(n-r)!}\) 、 \(\binom{n}{r} = \frac{n!}{r!(n-r)!}\) 。
  • 重複組合： \(\binom{n+r-1}{r}\) ，隔板法計數。
  • 容斥原理：交錯和計算聯集大小，部分和給 Bonferroni 上下界。
  • 錯排： \(D_n = n!\sum(-1)^k/k!\) ，比例趨近 \(1/e\) 。
  • Bertrand 悖論：等可能性的定義依賴於「如何隨機」，古典定義的破口。

年表速查（本節涉及的關鍵年份）#

  • 先秦：《易經》64 卦，乘法原理的早期體現。
  • 1321：Levi ben Gerson《計算之書》嚴格證明排列組合公式。
  • 13 世紀：Llull 組合輪盤，組合思想的神秘主義前史。
  • 1550：Cardano《算術精要》給出骰子組合計算。
  • 1654：Pascal《論算術三角形》。
  • 1663：Cardano《論賭博》出版，含骰子組合。
  • 1665：Newton 廣義二項式定理。
  • 1666：Leibniz《論組合術》。
  • 1708：Montmort《機遇分析》提出相遇遊戲與錯排。
  • 1711–1718：de Moivre《機遇原理》統一術語。
  • 1748：Euler《無窮分析引論》確立生成函數方法。
  • 1812：Laplace《機率的分析理論》正式表述古典機率。
  • 1887：Bertrand 提出投票問題與弦悖論。
  • 1936：Bonferroni 不等式。

深化問答三則#

問：古典機率定義的「循環性」有多致命？ 答：它使「等可能」淪為主觀判斷的依據，Bertrand 悖論顯示同一句話「隨機取弦」可對應不同機率。但致命的只是「以此為定義」，不是「以此為方法」：只要明確指定樣本空間與等可能假設（即選定一個測度），計算依然嚴格。Kolmogorov 公理（5.3 節）做的事正是把「機率」從定義層面移到公理層面，等可能性降級為常見的建模選擇。

問：組合爆炸為什麼在實務上需要「不數」的技術？ 答： \(\binom{52}{5} \approx 2.6 \times 10^6\) 尚可容忍，但 \(\binom{100}{50} \approx 10^{29}\) 完全無法逐一枚舉。生成函數、容斥、遞迴與（二十世紀的）蒙地卡羅模擬（10.2 節）都是「繞過枚舉」的策略。計數理論的發展史，就是一部「聰明地不數」的歷史。

問：Pascal 三角形在東方與伊斯蘭世界的先行版本說明了什麼？ 答：中國賈憲（約 1050）與楊輝（1261）的「賈憲三角」、伊斯蘭 al-Karaji（約 1000）與 Omar Khayyam 的相關結果，都早於 Pascal 數百年。這提醒我們：數學成果的發現與進入持續傳播的理論體系是兩回事。Pascal 的貢獻不在「發現數字三角形」，而在把它與機率問題連結並給出一般證明——連結產生學科。

（本節完）