組合與二項式係數

從有序到無序：把重複計數除掉

在上一篇你數的是排列：順序重要的排法。從 n 個人中選 k 個排成一列，共有 P(n, k) = n! / (n - k)! 種，這建立在乘法原理與階乘之上。但很多時候我們根本不在意順序。Ana 和 Ben 握手，跟 Ben 和 Ana 握手是同一次握手。一個三人委員會，不論我們以什麼次序唸出成員，都是同一個委員會。當順序不再重要時，排列數就會重複計數——而組合就是把這份重複除掉之後得到的東西。

把這個技巧具體化。假設我們從 {A, B, C, D, E} 中選 3 個字母。有序排法共有 P(5, 3) = 5 * 4 * 3 = 60 種。但每一個無序的選擇——例如集合 {A, B, C}——對於同樣 3 個字母的每一種排序都被各算一次，而這樣的排序有 3! = 6 種（ABC、ACB、BAC、BCA、CAB、CBA）。所以每一組 3 個都恰好被算了 6 次。要得到組的數目，就相除：60 / 6 = 10。這個除法——整體的排列數，除以每組內部的排列數——就是組合的全部概念。

二項式係數：n 取 k

我們剛發現的這個數有名字也有符號。從 n 個中選 k 個、忽略順序的方法數，就是二項式係數，寫作「n 取 k」，唸法也相同。依照「除掉重複計數」的邏輯，它等於 P(n, k) 除以 k!，化簡後得到一個乾淨的階乘公式。這一個量就是二項式係數，從紙牌遊戲到你再爬幾階會遇到的二項分配，到處都看得到它。

C(n, k)  =  P(n, k) / k!  =  n! / ( k! (n - k)! )

Example:  C(5, 3) = 5! / (3! 2!) = 120 / (6 * 2) = 10

Multiplicative form (fast by hand, no big factorials):
  C(n, k) = (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 1)
  C(52, 5) = (52*51*50*49*48) / (5*4*3*2*1) = 2,598,960

同一個數的三種等價面貌；乘法形式最適合手算。

有兩個事實值得記住，因為它們能快速抓出錯誤。第一，C(n, 0) = 1 且 C(n, n) = 1：選出「什麼都不選」恰有一種方式，選出「全部」也恰有一種方式（空集合與全集各算一次）。0! = 1 這個約定，正是讓公式正確給出這些結果的原因。第二，對稱性 C(n, k) = C(n, n - k)：選擇要留下哪 k 個，跟選擇要捨棄哪 n - k 個，是同一件事。所以不必重新計算，就知道 C(52, 5) = C(52, 47)。

巴斯卡三角形：用單一遞迴來計數

二項式係數不是孤立的數；它們透過一條漂亮的遞迴彼此扣連：C(n, k) = C(n - 1, k - 1) + C(n - 1, k)。其組合學上的理由是一個乾淨的「或者／或者」論證。挑出一個特別的元素，比如第 n 號元素。任何 k 元子集要嘛包含它、要嘛不包含。包含它的子集，必須從其餘 n - 1 個中選出剩下的 k - 1 個：那就是 C(n - 1, k - 1)。不含它的子集，必須從其餘 n - 1 個中選滿 k 個：那就是 C(n - 1, k)。每個子集都恰好落入一個桶子，所以兩個計數相加。

把這些係數一列一列堆疊起來，就得到巴斯卡三角形，其中每個項都是正上方兩個項之和。兩條邊全是 1（就是 C(n, 0) 與 C(n, n) 那兩個事實），而內部僅靠加法就把自己填滿——不需要階乘。這不只是趣味：它確實是你在不溢位的情況下計算這些數的方法，因為你始終只在加小整數，而不是去除龐大的階乘。

row n=0:            1
row n=1:          1   1
row n=2:        1   2   1
row n=3:      1   3   3   1
row n=4:    1   4   6   4   1
row n=5:  1   5  10  10   5   1

C(4,2) = C(3,1) + C(3,2) = 3 + 3 = 6   (each entry = sum of two above)

巴斯卡三角形：邊緣為 1，內部由加法建構。

為何叫「二項式」？二項式定理

這個係數的名字來自二項式定理，它展開兩項之和的乘冪：(x + y)^n 是一串項 C(n, k) x^k y^(n-k) 的總和，其中 k 從 0 跑到 n。它與計數的關聯不是巧合——這正是同樣的數會出現的全部原因。當你把 n 個因式 (x + y)(x + y)...(x + y) 乘開時，展開乘積中的每一項，都是從每個因式裡挑 x 或挑 y 而來。要得到 x^k y^(n-k)，你必須在 n 個因式中恰好從 k 個挑出 x——而選出這 k 個因式的方法數，正好就是 C(n, k)。

這個觀點還免費送你恆等式。令 x = y = 1：則 (1 + 1)^n = 2^n 等於所有 C(n, k)（k 從 0 到 n）之和。換句話說，一個 n 元集合的子集總數是 2^n，因為每個子集都是對每個元素做「是／否」的選擇——而把子集按大小 k 加總起來，就重現了 2^n。這是一個小而實在的預告，說明計數論證與代數如何彼此印證；那些用來數委員會的同一批係數，也在替多項式的各項加權。

一個範例，以及一個要避開的陷阱

讓我們用一個經典問題來實作：一手 5 張的撲克牌中，恰好含有兩張 A 的有幾種？標準 52 張牌中有 4 張 A 與 48 張非 A，而一手牌是無序的，所以從頭到尾都該用組合這個工具。

從現有的四張 A 中選兩張：C(4, 2) = 6 種。
從 48 張非 A 中選出剩下三張（如此 A 的數目才會恰好保持為兩張）：C(48, 3) = 17,296 種。
用乘法原理把兩個獨立的選擇相乘：6 * 17,296 = 103,776 手。

請留意是什麼樣的紀律讓這個計算保持正確。我們把任務拆成獨立的子選擇（先選哪些 A，再選哪些非 A），各用一個組合來數，然後相乘。我們沒有再乘上任何排序因子，因為在一手牌之內，牌是無序的。一個常見的失誤是把兩種模式混用——例如算出 C(4, 2) 後又把另外三張牌「依序排列」——這會把實際上相同的牌手重複計算。整道題要一致地決定把順序算進去或排除掉。