這個計算機的用途
重複組合計算機可以算出:當允許重複選取、且不考慮選取順序時,從 n 種不同類型中挑選 r 個物品共有幾種方式。這是組合數學與機率中的核心公式,也常被稱為「隔板法(stars and bars)」問題。由於每一種類型都可以被重複挑選,因此計算結果會比「不可重複」的一般組合來得多。
需要輸入的數值
- 物品種類總數(n):可供挑選的不同類別有幾種——例如 3 種冰淇淋口味。
- 要挑選的物品數量(r):你總共挑選幾次,且同一種類型可以被重複選取。
兩者都以整數輸入,計算機便會立即回傳單一結果:相異多重集合(允許重複的無序選取)的數量。
計算公式
本工具採用標準的重複組合公式:
$$C^{R}(n,r) = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$
程式內部會計算三個階乘——\((n + r - 1)!\)、\(r!\) 與 \((n - 1)!\)——再依公式相除。由於採用精確階乘與整數運算,所得結果是精確的整數計數,而非近似值。
範例演算
假設一家冰淇淋店提供 n = 3 種口味,而你想點一杯有 r = 2 球的冰淇淋,且口味可以重複。代入 n = 3、r = 2:
- \(n + r - 1 = 3 + 2 - 1 = 4\)
- $$C(4, 2) = \frac{4!}{2!\cdot 2!} = \frac{24}{2 \cdot 2} = \mathbf{6}$$
因此共有 6 種兩球的搭配方式:AA、BB、CC、AB、AC 與 BC。計算機會立即回傳 6。
更多已實現的例子
下面的每個例子都使用同一個恆等式,\(C^{R}(n,r) = \binom{n+r-1}{r} = \frac{(n+r-1)!}{r!\,(n-1)!}\),其中 \(n\) 是可用的不同物品類型的數量,\(r\) 是選擇的物品數量。順序不重要,每種類型都可以重複使用,所以每個結果都是一個多重集。
例子 1 — 三個相同的骰子(n = 6, r = 3)
你擲三個難以區分的六面骰子,並只記錄顯示的面集合(所以 1-3-6 和 6-3-1 算作相同的結果)。有 \(n = 6\) 種面類型和 \(r = 3\) 次選擇,允許重複,因為兩個骰子可以顯示相同的面。
上方指數:\(n + r - 1 = 6 + 3 - 1 = 8\)。
$$C^{R}(6,3) = \binom{8}{3} = \frac{8!}{3!\,5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56$$所以有 56 個不同的無序面組合。注意這遠少於 \(6^3 = 216\) 個有序擲骰——216 個有序結果折疊成 56 個多重集,但不均勻(像 4-4-4 這樣的三倍有一種排列,而 1-3-6 有六種),這正是為什麼骰子和的概率必須從 216 個有序擲骰而不是 56 個多重集計算。
例子 2 — 勺子多於風味(n = 3, r = 5)
一家冰淇淋店提供 3 種風味,你訂購一個 5 勺的桶;允許同一風味的勺子,並且它們被打包的順序無關緊要。這裡 \(r = 5\) 大於 \(n = 3\),這對於不允許重複的組合是不可能的,但在這裡完全可以。
上方指數:\(n + r - 1 = 3 + 5 - 1 = 7\)。
$$C^{R}(3,5) = \binom{7}{5} = \frac{7!}{5!\,2!} = \frac{7 \times 6}{2 \times 1} = \frac{42}{2} = 21$$有 21 個可能的桶。取消 \(5!\) 而不是 \(2!\) 是這裡的快捷方式:因為 \(\binom{7}{5} = \binom{7}{2}\),只有兩個分子因子存活。用星條法術語,你正在放置 5 個星星(勺子)和 \(n - 1 = 2\) 個條(風味分隔符)在 7 個位置——例如 \(\star\star\,|\,\star\,|\,\star\star\) 表示 2 個香草,1 個巧克力,2 個草莓。
例子 3 — 兩個邊界情況(r = 1 和 n = 1)
選擇一個物品(n = 4, r = 1)。 你從 4 種大小中選擇一種飲料。只有一次選擇,重複永遠不會發生,所以答案必須就是類型的數量:
$$C^{R}(4,1) = \binom{4+1-1}{1} = \binom{4}{1} = \frac{4!}{1!\,3!} = \frac{4}{1} = 4$$這給出 4 個結果——任何這樣的表的 \(r = 1\) 列總是只有 \(n\)。
只有一種類型(n = 1, r = 7)。 一台販賣機只存放一種產品,你購買 7 個單位:
$$C^{R}(1,7) = \binom{1+7-1}{7} = \binom{7}{7} = \frac{7!}{7!\,0!} = \frac{5040}{5040 \times 1} = 1$$恰好有一個多重集——"七個唯一可用的東西"——因為只有一種類型,沒有選擇可以做。形式上 \(n - 1 = 0\) 個條是需要的,所有 7 個位置必須是星星,並且 \(\binom{7}{7} = 1\)。相同的邏輯使得 \(C^{R}(n,0) = 1\) 對於任何 \(n\):選擇什麼都不是一個有效的(空)選擇,這就是為什麼 \(0! = 1\) 是保持公式一致的約定。
帶替換的組合參考表
恰好 \(C^{R}(n,r) = \binom{n+r-1}{r}\) 對於 1–8 種物品類型各選擇 1–6 次的精確值。向下讀到你的類型數 \(n\),然後橫向讀到選擇數 \(r\)。
| n(類型) | r = 1 | r = 2 | r = 3 | r = 4 | r = 5 | r = 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 3 | 4 | 5 | 6 | 7 |
| 3 | 3 | 6 | 10 | 15 | 21 | 28 |
| 4 | 4 | 10 | 20 | 35 | 56 | 84 |
| 5 | 5 | 15 | 35 | 70 | 126 | 210 |
| 6 | 6 | 21 | 56 | 126 | 252 | 462 |
| 7 | 7 | 28 | 84 | 210 | 462 | 924 |
| 8 | 8 | 36 | 120 | 330 | 792 | 1716 |
如何讀取圖案
- 每一行都是帕斯卡三角形的對角線。 第 \(n = 1\) 行是常數序列 1s,第 \(n = 2\) 行是自然數 \(2, 3, 4, \dots\),第 \(n = 3\) 行是三角數 \(3, 6, 10, 15, 21, 28\),第 \(n = 4\) 行是四面體數 \(4, 10, 20, 35, 56, 84\)。這只是 \(\binom{n+r-1}{r}\) 沿著固定 \(n\) 追跡。
- 表在移位下是對稱的。 因為 \(\binom{n+r-1}{r} = \binom{n+r-1}{n-1}\),我們得到 \(C^{R}(n,r) = C^{R}(r+1,\,n-1)\)。例如 \(C^{R}(6,3) = 56 = C^{R}(4,5)\) 和 \(C^{R}(8,3) = 120 = C^{R}(4,7)\)。用這種方式交換"類型"和"選擇"的角色通常將長乘法變成短乘法。
- 增長是 r 的多項式,度數為 n − 1。 固定 \(n\),\(C^{R}(n,r) = \frac{(r+1)(r+2)\cdots(r+n-1)}{(n-1)!}\),度數為 \(n-1\) 的多項式——\(n = 2\) 時線性,\(n = 3\) 時二次,\(n = 4\) 時三次。固定 \(r\) 並增長 \(n\) 的行為方式相同,角色相反(\(n\) 中度數 \(r\))。無論哪種方式,計數都遠低於允許重複的有序選擇的 \(n^{r}\) 計數。
- 每個項都是它上面的項和它左邊的項的和(兩者都存在的地方):\(C^{R}(n,r) = C^{R}(n-1,r) + C^{R}(n,r-1)\)。檢查 \(n = 6\), \(r = 4\) 單元格中的 \(126 = 70 + 56\)。該遞推是手工擴展表的快速方法。
如何手工計算
星條圖
在進行算術之前,有助於理解為什麼公式具有該形式。將選擇表示為 \(r\) 個相同的星星(你拿走的物品)被分成 \(n\) 個群組,用 \(n-1\) 個條(連續物品類型之間的分隔符)分隔。第 \(i\) 組中的星星數是你選擇的類型 \(i\) 的副本數。\(r\) 個星星和 \(n-1\) 個條的每種排列恰好對應一個有效的選擇,行中有 \(r + (n-1) = n + r - 1\) 個位置。因此計數選擇意味著選擇那些 \(n+r-1\) 個位置中的哪 \(r\) 個持有星星:
$$C^{R}(n,r) = \binom{n+r-1}{r} = \binom{n+r-1}{n-1}$$例如,有 \(n = 4\) 種類型和 \(r = 5\) 次選擇,行 \(\star\,|\,|\,\star\star\star\,|\,\star\) 有 8 個位置,表示 1 個 A 類型,0 個 B 類型,3 個 C 類型,1 個 D 類型。
分步程序
- 檢查輸入。 確認 \(n\) 和 \(r\) 是整數,且 \(n \ge 1\) 和 \(r \ge 0\)。與不允許替換的組合不同,\(r\) 可能超過 \(n\) ——允許重複,所以 \(r\) 沒有上界。
- 計算上方指數。 計算 \(N = n + r - 1\)。這是星條位置的總數。
- 寫二項式。 \(C^{R}(n,r) = \dbinom{N}{r} = \dfrac{N!}{r!\,(n-1)!}\)。絕不要完全展開這些階乘——\(N!\) 爆炸式增長,大數字都會取消。
- 將 \((n-1)!\) 抵消 \(N!\)。 由於 \(N - r = n - 1\),商 \(N!/(n-1)!\) 在分子中留下恰好 \(r\) 個遞減因子:
- 將 \(r\) 個分子項相乘,然後除以 \(r!\)。 如果 \(r\) 大於 \(n-1\),首先使用對稱性 \(\binom{N}{r} = \binom{N}{n-1}\),以便你改為相乘較小數量的因子。
- 進行合理性檢查,確保結果是整數。 二項式係數總是整數,所以任何剩餘分數或餘數意味著算術錯誤。還有兩個快速檢查:\(r = 1\) 必須給出恰好 \(n\),\(n = 1\) 必須給出恰好 1。
計算示範(n = 5, r = 4)
從 5 種配料中選擇 4 勺冷凍酸奶,允許重複,順序無關。
- 步驟 2:\(N = 5 + 4 - 1 = 8\)。
- 步驟 3:\(C^{R}(5,4) = \dfrac{8!}{4!\,4!}\)。
- 步驟 4:取消 \((n-1)! = 4!\),留下 \(r = 4\) 個從 8 到 \(n = 5\) 的遞減因子:\(\dfrac{8 \times 7 \times 6 \times 5}{4!}\)。
- 步驟 5:\(\dfrac{1680}{24} = 70\)。
- 步驟 6:70 是整數,它與上面參考表的 \(n = 5\), \(r = 4\) 單元格匹配。
答案是 70 個不同的配料組合。一個有用的對比:如果順序重要,相同的輸入給出 \(5^4 = 625\),如果禁止重複,只有 \(\binom{5}{4} = 5\) ——所以在選擇公式之前始終決定順序和重複是否適用。
常見問題
這和一般的組合有什麼不同?一般組合 \(C(n, r)\) 不允許重複——每個物品最多只能被選一次。而重複組合允許同一種類型被多次挑選,因此公式要改用 \(C(n + r - 1, r)\)。
這裡需要考慮順序嗎?不用。AB 與 BA 視為相同的選取。如果順序有差別,那就要改用排列(permutation)了。
r 可以大於 n 嗎?可以。由於允許重複,你挑選的物品數量可以多於類型的種類數——例如從 3 種口味中挑 5 球完全沒問題,而且會得到更大的計數結果。