重複組合せの計算

同じ種類を何度選んでもよく、順序は問わないときに、n種類からr個を選ぶ方法の数を求めます。味のリストから選ぶアイスのスクープ、額面の異なる硬貨からの選択、ベーカリーのトレイから選ぶドーナツなどが例です。この数は重複組合せ、または多重集合の数、「n multichoose r」とも呼ばれ、小さい場合はすべての選び方を一覧にして表示します。

使い方

1. n、つまり選べる異なる種類の数を入力します。
2. r、つまり合計で何個選ぶかを入力します。nより大きくても構いません。
3. 重複組合せの数を確認します。比較用に、重複なしの組合せの数と、順序を区別する場合の数も表示されます。

計算式

C(n + r − 1, r) = (n + r − 1)! ÷ (r! × (n − 1)!)

「スターズ・アンド・バーズ」の考え方で説明できます。r個の星（選んだもの）とn − 1本の仕切り（種類の区切り）を一列に並べます。このn + r − 1個の記号の並びは、それぞれちょうど1つの選び方に対応し、r個の星を置く位置の選び方を数えると上の公式になります。

計算例

5種類の味から3スクープを、重複を許して選ぶと、C(5 + 3 − 1, 3) = C(7, 3) = 7! ÷ (3! × 4!) = 5040 ÷ 144 = 35通りです。重複なしならC(5, 3) = 10通りだけで、スクープの順序も区別するなら5³ = 125通りです。