什麼是重複組合?
重複組合用來計算:在「允許重複挑選同一種類型」且「不考慮挑選順序」的情況下,從 n 種不同的類型中選出 r 個,總共有幾種不同的選法。這個數量通常記為 nHr,也稱為多重集合係數(multiset coefficient)。它可以回答像這樣的問題:「冰淇淋有 4 種口味,挖 2 球而且可以重複,總共能組合出幾種不同的搭配?」
如何使用這個計算器
輸入不同類型的數量 n(至少為 1),以及你想挑選的個數 r(0 或以上)。按下計算,工具就會回傳 nHr,也就是不同多重集合的精確數量。兩個欄位都是單純的非負整數,沒有任何單位需要換算。
公式說明
核心公式為 $$\overline{C}(n,r) = \binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r! \cdot (n - 1)!}$$ 背後的巧思在於:把 \(r\) 個被選中的項目,以及用來區隔各類型的 \((n - 1)\) 個分隔線排成一列,總共有 \(n + r - 1\) 個位置,我們只需決定項目(或分隔線)要放在哪些位置即可。為了避免出現龐大的階乘運算,本計算器採用穩定的連乘迴圈來求二項式係數:令 \(m = n + r - 1\)、\(k = \min(r, n - 1)\),對 \(i = 1..k\) 依序乘上 \((m - k + i)\) 再除以 \(i\)。
實際範例
以預設值 \(n = 4\)、\(r = 2\) 為例:$$nHr = C(4 + 2 - 1, 2) = C(5, 2) = \frac{5 \cdot 4}{2 \cdot 1} = 10$$ 從類型 \(\{a, b, c, d\}\) 得到的十種組合分別是:aa、ab、ac、ad、bb、bc、bd、cc、cd、dd。
常見問題
這和一般的組合有什麼不同?一般組合 \(C(n, r)\) 不允許重複,因此每個項目最多只能選一次;這裡則允許重複,所以算出來的數量會比較大。
如果 \(r = 0\) 呢?此時剛好有一種組合,也就是「什麼都不選」的空集合,因此 \(nHr = 1\)。
如果 \(n = 1\) 呢?只有一種類型時,你只能把它選 \(r\) 次,所以對任何 \(r\) 而言都只有一個多重集合,\(nHr = 1\)。