這個計算器能做什麼
這個工具會為你建立一張可重複組合(也稱為多重集係數)的表格。給定 \(n\) 種不同的物品類型,當每種物品都可以被選取任意多次時,它會計算出共有多少種大小為 \(r\) 的「不計順序」選法——而且會針對從起始值到結束值之間的每一個整數 \(r\) 逐一列出。此函數寫作 \(H(n, r)\),其值等於二項式係數 \(C(n + r - 1, r)\)。
使用方式
先輸入不同物品的數量 \(n\)(至少為 1),接著輸入 \(r\) 的起始值與結束值。計算器會為每一個 \(r\) 輸出一列,列出該情況下的精確數值 \(H(n, r)\)。由於這些數字成長得極為快速,引擎採用精確的大整數運算,因此即使是規模龐大的表格也能維持完全準確。
公式解析
經典的「隔板法(stars and bars)」告訴我們:從 \(n\) 種類型中可重複地選出 \(r\) 個物品,等同於把 \(r\) 顆相同的星號放進由 \(n - 1\) 條隔板分隔出的 \(n\) 個格子裡。這 \(n + r - 1\) 個符號的排列方式共有 \(C(n + r - 1, r)\) 種。 $$\overline{C}(n, r) = \binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$ 有兩個特例值得注意:\(H(n, 0) = 1\)(空集合的選法),以及 \(H(1, r) = 1\)(只有一種多重集,即把唯一的物品取 r 份)。
實例演算
以 \(n = 5\)、\(r\) 從 0 到 4 為例:\(H(5,0) = C(4,0) = 1\),\(H(5,1) = C(5,1) = 5\),\(H(5,2) = C(6,2) = 15\),\(H(5,3) = C(7,3) = 35\),\(H(5,4) = C(8,4) = 70\)。因此表格內容為 1、5、15、35、70。再驗算一個: $$H(30,4) = C(33,4) = \frac{33 \cdot 32 \cdot 31 \cdot 30}{24} = 40920$$
常見問題
這跟一般的組合有什麼不同?一般組合 \(C(n, r)\) 不允許重複;在這裡,每種物品類型都可以被選取多次,這正是公式的下標變成 \(n + r - 1\) 的原因。
順序重要嗎?不重要。{A, A, B} 與 {B, A, A} 算同一種選法。如果順序有差別,你應該改用可重複排列(\(n^r\))。
為什麼數值會變得這麼大?多重集係數大致以 \(r\) 的 \(n - 1\) 次多項式速度成長,所以只要 \(n\) 或 \(r\) 稍大,就會產生天文數字般的整數——本工具以精確運算妥善處理這類情況。