この計算ツールでできること
このツールは、重複組合せ（重複を許す組合せ、多重集合係数とも呼ばれます）の一覧表を作成します。異なるn種類のものがあるとき、同じものを何個でも選んでよいという条件で、順序を区別せずにr個を選ぶ選び方が何通りあるかを計算します。しかもrを開始値から終了値まで整数で変化させ、それぞれの値について一度に求められます。この個数は \(H(n, r)\) と書き、二項係数 \(C(n + r - 1, r)\) に等しくなります。
使い方
まず異なるものの種類数n（1以上）を入力し、続いてrの開始値と終了値を入力します。するとrごとに1行ずつ、\(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)!}$$ 覚えておきたい特別な場合が2つあります。\(H(n, 0) = 1\)（何も選ばない場合）と、\(H(1, r) = 1\)（1種類しかないものをr個選ぶ多重集合は1通りだけ）です。
計算例
\(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\) が大きいと天文学的な整数になりますが、本ツールでは厳密計算で正確に扱います。
