組合與計數：算出「有多少種」的藝術

一份菜單能變出多少種便當？

午餐時間，你站在自助餐檯前：三種主菜、四種配菜、兩種飯。你只是想吃頓飯，卻不知不覺啟動了一個古老的數學問題——「到底有多少種組合？」如果每樣各挑一種，答案是 $3 \times 4 \times 2 = 24$ 種便當。聽起來很簡單，但只要把問題改成「四種配菜要挑兩種」「主菜可以重複」「飯的順序重不重要」，數字就會以驚人的速度膨脹或收縮。

這正是「組合與計數（combinatorics and counting）」的核心：在不真的把所有可能性一個一個列出來的前提下，精準地算出「有多少種」。它是離散數學（discrete mathematics）的基石，也是機率（probability）、密碼學（cryptography）、演算法分析（algorithm analysis）背後共同的語言。讓我們從最根本的兩條原理開始。

兩條計數原理：乘法與加法

所有計數問題，幾乎都可以拆解成兩個基本動作的組合。

乘法原理（multiplication principle）：如果一件事要分成連續的幾個步驟完成，第一步有 $m_1$ 種選法，第二步有 $m_2$ 種選法，……，第 $k$ 步有 $m_k$ 種選法，且每一步的選擇互不影響，那麼總共有

$$ m_1 \times m_2 \times \cdots \times m_k $$

種完成方式。前面的便當就是 $3 \times 4 \times 2$。

加法原理（addition principle）：如果一件事可以歸入「彼此互斥」的幾類，第一類有 $n_1$ 種、第二類有 $n_2$ 種……，且沒有任何方式同時屬於兩類，那麼總數是

$$ n_1 + n_2 + \cdots + n_k $$

關鍵字是「步驟」對「分類」、「相乘」對「相加」。判斷用哪一個，先問自己：這些選擇是「接連發生」（→ 乘法），還是「擇一發生」（→ 加法）？

看一個例子：車牌有幾種？

假設某種車牌格式是「三個英文字母接三個數字」，字母與數字都可重複。

字母每一位有 $26$ 種，三位就是 $26^3$；數字每一位有 $10$ 種，三位是 $10^3$。整張車牌是「先排字母、再排數字」的連續步驟，用乘法原理：

$$ 26^3 \times 10^3 = 17576 \times 1000 = 17\,576\,000 $$

約一千七百萬種。如果規定「字母不可重複」，第一位 $26$、第二位 $25$、第三位 $24$，字母部分變成 $26 \times 25 \times 24 = 15600$，這就把我們帶向了下一個概念——排列。

排列：當順序很重要

排列（permutation） 處理的是「順序有意義」的選取。從 $n$ 個相異物件中取出 $r$ 個排成一列，記作 $P(n, r)$ 或 $_nP_r$：

$$ P(n, r) = n \times (n-1) \times \cdots \times (n-r+1) = \frac{n!}{(n-r)!} $$

這裡的 $n!$ 是 $n$ 的階乘（factorial），即 $n! = n \times (n-1) \times \cdots \times 2 \times 1$，並約定 $0! = 1$。

直覺上：第一個位置有 $n$ 種選擇，選掉一個後第二個位置剩 $n-1$ 種，依此類推到第 $r$ 個位置剩 $n-r+1$ 種，全部相乘即為乘法原理的直接應用。

當 $r = n$ 時，$P(n, n) = n!$，意思是把 $n$ 個物件全部排成一列的方法數。例如 $5$ 本不同的書排上書架有 $5! = 120$ 種。

動手試試：頒獎台問題

班上 $8$ 位同學參加賽跑，要決定金、銀、銅牌得主，有幾種可能結果？

因為「金牌給誰、銀牌給誰、銅牌給誰」是有順序之分的（金牌和銅牌顯然不同），這是排列：

$$ P(8, 3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \times 7 \times 6 = 336 $$

共 $336$ 種頒獎結果。

組合：當順序不重要

如果我們只關心「挑到哪幾個」而不在乎「以什麼順序挑」，就是組合（combination）。從 $n$ 個相異物件取 $r$ 個，記作 $C(n, r)$、$_nC_r$ 或更常見的二項式記號 $\binom{n}{r}$：

$$ \binom{n}{r} = \frac{P(n, r)}{r!} = \frac{n!}{r!\,(n-r)!} $$

為什麼要除以 $r!$？因為同一組 $r$ 個物件，本身有 $r!$ 種排列順序，但在組合中這些都算「同一種選法」。排列把它們重複數了 $r!$ 次，所以除回去。

看一個例子：從排列到組合

回到賽跑，如果改成「從 $8$ 位同學中選 $3$ 位代表參加團體賽」，誰先誰後都一樣，是組合：

$$ \binom{8}{3} = \frac{8!}{3!\,5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56 $$

注意 $336$（排列）正好是 $56$（組合）的 $3! = 6$ 倍，印證了上面的關係。

組合有幾個漂亮的性質值得記住：

• 對稱性：$\binom{n}{r} = \binom{n}{n-r}$。選出 $r$ 個要帶走，等價於選出 $n-r$ 個留下。
• 邊界值：$\binom{n}{0} = \binom{n}{n} = 1$（一個都不選或全選，各只有一種）。
• 巴斯卡法則（Pascal's rule）：$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$。

二項式定理與巴斯卡三角形

組合數 $\binom{n}{r}$ 又稱二項式係數（binomial coefficient），因為它正是展開 $(x+y)^n$ 時各項的係數：

$$ (x + y)^n = \sum_{r=0}^{n} \binom{n}{r} x^{n-r} y^{r} $$

這就是二項式定理（binomial theorem）。例如

$$ (x+y)^4 = \binom{4}{0}x^4 + \binom{4}{1}x^3 y + \binom{4}{2}x^2 y^2 + \binom{4}{3}x y^3 + \binom{4}{4}y^4 $$

$$ = x^4 + 4x^3 y + 6x^2 y^2 + 4x y^3 + y^4 $$

把係數一列列疊起來，就是著名的巴斯卡三角形（Pascal's triangle）：

$$ \begin{array}{ccccccc} & & & 1 & & & \\ & & 1 & & 1 & & \\ & 1 & & 2 & & 1 & \\ 1 & & 3 & & 3 & & 1 \end{array} $$

每個數都是上方兩個數之和，正是巴斯卡法則的視覺化。把 $x = y = 1$ 代入二項式定理，還能得到一個優雅的恆等式：

$$ \sum_{r=0}^{n} \binom{n}{r} = 2^n $$

它的組合意義是：一個 $n$ 元素的集合，其所有子集（含空集與本身）的總數是 $2^n$——因為每個元素都面臨「選或不選」兩種獨立決定。

可重複的選取與容斥原理

現實問題常有變化。兩個常見的進階模型：

重複組合（combination with repetition）：從 $n$ 種物件中取 $r$ 個、允許重複且不計順序（例如從三種口味的飲料買五杯），方法數為

$$ \binom{n + r - 1}{r} $$

這個公式可用「隔板法（stars and bars）」證明：把 $r$ 個相同的星號用 $n-1$ 個隔板分成 $n$ 組，每組對應一種物件的數量。以三種口味買五杯為例：

$$ \binom{3 + 5 - 1}{5} = \binom{7}{5} = \binom{7}{2} = 21 $$

容斥原理（inclusion-exclusion principle）：當分類彼此有重疊、不能直接相加時，用加加減減修正。兩集合版本：

$$ |A \cup B| = |A| + |B| - |A \cap B| $$

三集合版本：

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

例如：$1$ 到 $100$ 中，被 $2$ 或 $3$ 整除的數有幾個？被 $2$ 整除有 $50$ 個，被 $3$ 整除有 $33$ 個，同時被 $6$ 整除有 $16$ 個，故

$$ 50 + 33 - 16 = 67 \text{（個）} $$

重點回顧

• 乘法 vs 加法：連續步驟用乘法，互斥分類用加法。判斷前先問「接連發生還是擇一發生」。
• 排列重順序、組合不重順序：$P(n,r) = \dfrac{n!}{(n-r)!}$；$\binom{n}{r} = \dfrac{n!}{r!\,(n-r)!} = \dfrac{P(n,r)}{r!}$。
• 組合是排列除以 $r!$：因為每組 $r$ 個物件被排列重複算了 $r!$ 次。
• 二項式係數連結代數與計數：$(x+y)^n$ 的展開係數、巴斯卡三角形、子集總數 $2^n$ 三者一脈相承。
• 進階模型：重複組合用隔板法 $\binom{n+r-1}{r}$；有重疊的分類用容斥原理加減修正。

深入探討（研究所視角）

從研究的高度看，組合學遠不只是「算有幾種」，它是一門關於結構（structure）與生成（generation）的學問。

生成函數（generating function） 是現代組合學最強大的工具之一。把一個數列 $\{a_n\}$ 編碼成形式冪級數 $A(x) = \sum_{n \ge 0} a_n x^n$，許多看似困難的計數遞迴關係，在生成函數的代數操作下變得透明。例如費氏數列（Fibonacci）的生成函數是有理函數 $\frac{x}{1 - x - x^2}$，由此可直接導出 Binet 閉式解。指數生成函數（exponential generating function）$\sum a_n \frac{x^n}{n!}$ 則特別適合處理「有標記結構（labeled structures）」，是 Flajolet 與 Sedgewick《Analytic Combinatorics》一書中「符號方法（symbolic method）」的核心：物件的構造規則（序列、集合、循環）可機械地翻譯成生成函數的運算（乘積、指數、對數），再用複分析（complex analysis）的奇異點分析（singularity analysis）萃取漸近行為。

漸近與機率方法 把組合學帶向分析與機率的交界。Stirling 近似 $n! \sim \sqrt{2\pi n}\,(n/e)^n$ 讓我們估計巨大階乘的量級；中央二項式係數 $\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}$ 在隨機漫步與 Catalan 數中反覆出現。Erdős 開創的機率方法（probabilistic method） 更顛覆直覺：要證明某種組合物件「存在」，不必真的構造它，只要證明隨機選取時它出現的機率大於零即可——這在拉姆齊理論（Ramsey theory）與圖論的下界證明中威力驚人。

跨領域連結 處處可見。在演算法分析中，二項式係數刻畫了排序與搜尋的比較次數下界；在統計力學中，組態（configuration）的計數即是配分函數（partition function）；在編碼理論中，漢明球（Hamming ball）的大小由 $\sum_r \binom{n}{r}$ 決定碼的糾錯能力；在機器學習裡，VC 維（Vapnik–Chervonenkis dimension）的成長函數本質上是被組合不等式（Sauer–Shelah 引理 $\sum_{i=0}^{d}\binom{n}{i}$）所界定。

對 Uedu 而言，這種「離散結構的精確計數」也滲透在教育數據的分析中：當我們研究 Educational Omics 框架下多模態資料的組合配對、學習路徑的可能分支、或同儕分組的設計時，背後的可行空間規模，往往就是一個排列、組合或容斥的問題。理解計數，就是理解「可能性的版圖」有多大——這是從刷題邁向研究的關鍵一步。