このツールでできること
重複組合せ計算ツールは、n 種類の異なるものの中から、同じものを何度選んでもよく、かつ選ぶ順序を区別しない条件で r 個を取り出す方法が何通りあるかを計算します。これは組合せ論や確率の基礎となる考え方で、「重複組合せ」あるいは英語では「stars and bars(仕切り棒の方法)」とも呼ばれます。同じ種類を繰り返し選べるため、重複を許さない通常の組合せよりも数が多くなります。
入力する値
- ものの種類の数(n): 選ぶ対象となる異なるカテゴリーの数です。たとえばアイスクリームのフレーバーが3種類、といった具合です。
- 選ぶ個数(r): 合計で何個取り出すかを表します。同じ種類を何度選んでも構いません。
どちらも整数で入力すると、計算ツールが結果を瞬時に1つ返します。これは、重複を許す順序を区別しない選び方(多重集合)の総数です。
計算式
このツールは、重複組合せの標準的な公式を用います。
$$C^{R}(n,r) = \frac{(\text{n} + \text{r} - 1)!}{\text{r}!\,(\text{n} - 1)!}$$
内部では3つの階乗 ——(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}$$
つまり、2玉カップの組み合わせは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—3つの同じサイコロ(n = 6、r = 3)
区別できない3つの6面体サイコロを振り、出ている面の集合のみを記録します(1-3-6と6-3-1は同じ結果としてカウントされます)。\(n = 6\)面の種類と\(r = 3\)の選択があり、2つのサイコロが同じ面を表示する可能性があるため、繰り返しが許可されています。
上位インデックス:\(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のような3つは1つの順序を持ち、1-3-6は6つを持ちます)、これはサイコロの合計の確率が56のマルチセットからではなく216の順序付きロールから計算されなければならない理由がまさにそれです。
例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}\)であるため、2つの分子因子のみが生き残ります。スターとバーの用語では、5個のスター(スクープ)と\(n - 1 = 2\)個のバー(フレーバー区切り記号)を7つのスロットに配置しています—たとえば\(\star\star\,|\,\star\,|\,\star\star\)は2つのバニラ、1つのチョコレート、2つのイチゴを意味します。
例3—2つの境界ケース(r = 1およびn = 1)
1つのアイテムを選択する(n = 4、r = 1)。4つのサイズから1つのドリンクを選択します。1つの選択のみで、繰り返しは決して発生しないため、答えは単にタイプの数である必要があります:
$$C^{R}(4,1) = \binom{4+1-1}{1} = \binom{4}{1} = \frac{4!}{1!\,3!} = \frac{4}{1} = 4$$これにより4の結果が得られます—任意のそのようなテーブルの\(r = 1\)列は常に\(n\)です。
1つのタイプのみ(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$$正確に1つのマルチセットがあります—「利用可能な唯一のもののうち7つ」—タイプが1つあるため、選択肢は残りません。正式には\(n - 1 = 0\)バーが必要で、すべての7つの位置がスターである必要があり、\(\binom{7}{7} = 1\)です。同じロジックで、任意の\(n\)に対して\(C^{R}(n,0) = 1\)になります:何も選択しないことは1つの有効な(空の)選択であるため、\(0! = 1\)は公式を一貫性のあるものにする規約です。
置換付き組み合わせ参照テーブル
1~8個のアイテムタイプを1~6回選択する場合の\(C^{R}(n,r) = \binom{n+r-1}{r}\)の正確な値。タイプの数\(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\)は1の定数列、行\(n = 2\)は自然数\(2, 3, 4, \dots\)、行\(n = 3\)は三角数\(3, 6, 10, 15, 21, 28\)、行\(n = 4\)は四面体数\(4, 10, 20, 35, 56, 84\)です。これは単に固定された\(n\)に沿ってトレースされた\(\binom{n+r-1}{r}\)です。
- テーブルはシフトの下で対称です。\(\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-1\)個のバー(連続するアイテムタイプ間の区切り記号)で\(n\)グループに分割します。グループ\(i\)のスターの数は、タイプ\(i\)の何個のコピーを選択したかです。\(r\)個のスターと\(n-1\)個のバーのすべての配置は、正確に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個の位置を持ち、タイプAの1個、タイプBの0個、タイプCの3個、タイプDの1個を意味します。
ステップバイステップの手順
- 入力をチェックしてください。\(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}\)を使用して、代わりにより小さい数の因子を乗算します。
- 結果が整数であることを確認チェックしてください。二項係数は常に整数であるため、残りの分数または余りは算術エラーを意味します。さらに2つの簡単なチェック:\(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!\)をキャンセルし、8から\(n = 5\)までの\(r = 4\)個の降順因子を残します:\(\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)\) では重複が許されず、各要素は最大でも1回しか選べません。一方、重複組合せでは同じ種類を複数回選べます。そのため、式が \(C(n + r - 1, r)\) に変わるのです。
順序は関係しますか? いいえ、関係しません。AB と BA は同じ選び方として数えます。順序を区別したい場合は、組合せではなく順列を使います。
r が n より大きくてもよいですか? はい、問題ありません。重複が許されるため、種類の数より多くの個数を選ぶことができます。たとえば3種類のフレーバーから5玉を選ぶことも正しい計算で、結果はより大きな数になります。