什麼是「不重複組合」?
不重複組合(combination without repetition)計算的是:從 n 個不同的項目中挑出 r 個,在「不計順序」且「同一項目不能重複選取」的前提下,總共能組成幾種相異的群組。它可以回答像是「五張牌的撲克牌型共有幾種?」或「從 10 個人中選出 3 人組成委員會有幾種選法?」這類問題。
如何使用這個計算機
在 n 欄位輸入可供挑選的項目總數,在 r 欄位輸入你想挑選的項目數量,計算機就會立即算出 \(C(n, r)\),也就是相異組合的總數。請注意 \(r\) 不能大於 \(n\);一旦 \(r\) 超過 \(n\),結果會是 0,因為你無法挑出比現有項目還多的數量。
公式解析
公式為 $$C(n, r) = \frac{n!}{r!\,(n - r)!}$$其中「!」代表階乘(即從 1 連乘到該數字的乘積)。分子 \(n!\) 計算的是所有「有順序」的排列方式;除以 \(r!\) 是為了去除被挑選群組內部的順序差異,再除以 \((n - r)!\) 則是去除沒被挑到的項目之間的順序差異。為了在數字很大時仍維持精準,本工具採用逐步迭代運算,而非直接計算龐大的階乘值。
實際範例
從 5 種配料中挑出 2 種,共有幾種選法?$$C(5, 2) = \frac{5!}{2!\,\cdot\,3!} = \frac{120}{2 \cdot 6} = \frac{120}{12} = \mathbf{10}$$也就是說,總共有 10 種不同的配料搭配組合。
帕斯卡三角形與常見的 C(n, r) 值
此表列出 n = 0 至 10 的 C(n, r)。空白格表示 r > n,此時無法做任何選取(其值為 0)。
| n \ r | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||||||
| 1 | 1 | 1 | |||||||||
| 2 | 1 | 2 | 1 | ||||||||
| 3 | 1 | 3 | 3 | 1 | |||||||
| 4 | 1 | 4 | 6 | 4 | 1 | ||||||
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | |||||
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||
| 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | |||
| 8 | 1 | 8 | 28 | 56 | 70 | 56 | 28 | 8 | 1 | ||
| 9 | 1 | 9 | 36 | 84 | 126 | 126 | 84 | 36 | 9 | 1 | |
| 10 | 1 | 10 | 45 | 120 | 210 | 252 | 210 | 120 | 45 | 10 | 1 |
- 對稱性: \(C(n,r)=C(n,n-r)\)。選出 r 個項目的方式數,與選出要留下的 n − r 個項目的方式數相同。每一列從前往後與從後往前讀都一樣。
- 帕斯卡法則: \(C(n,r)=C(n-1,r-1)+C(n-1,r)\)。每個數字都是其正上方兩個數字之和,例如第 10 列中 120 = 36 + 84。
- 每一列的總和為 \(2^n\),例如第 10 列的總和為 1,024。
如何手算 nCr
- 運用對稱性。 比較 r 與 n − r,並使用較小的那個數,因為 \(C(n,r)=C(n,n-r)\)。例如,C(50,48) = C(50,2)。
- 從 n 開始向下寫出 r 個因子: \(n\cdot(n-1)\cdot(n-2)\cdots(n-r+1)\)。這是分子。
- 在分母寫出 r!: \(r\cdot(r-1)\cdots 2\cdot 1\)。
- 在相乘之前先約去公因數。 若分子與分母的項有共同因數,就先相除。這樣可以讓數字保持較小,並得到精確結果,因為最終答案必定是整數。
- 將剩下的部分相乘,即得結果。
- 以小例子驗算。 對於 C(7,3):\(\frac{7\cdot 6\cdot 5}{3\cdot 2\cdot 1}=\frac{210}{6}=35\)。對稱性檢查:C(7,4) = \(\frac{7\cdot 6\cdot 5\cdot 4}{24}=35\),這也與上表相符。
常見問題
組合(combination)和排列(permutation)有什麼不同?排列在意順序(AB ≠ BA);組合則不計順序(AB = BA)。因此在相同條件下,組合的數量一定小於或等於排列的數量。
\(C(n, 0)\) 等於多少?等於 1——因為「什麼都不選」剛好只有一種方式。
這裡的「不重複」很重要嗎?很重要。「不重複」表示每個項目在一個群組中最多只能出現一次,這正是本計算機所處理的標準 nCr 情境。