組合せ (C) では、「異なる n 個から r 個を選ぶ」場合を考えましたが、選ぶ際に「同じものを何回選んでも良い（重複を許す）」という状況があります。このような場合の数を計算するのが「重複組合せ」です。記号 H を使って nHr と表されます。一見複雑に思えるかもしれませんが、「仕切りとボール」という非常に巧妙なモデルを使うことで、通常の組合せ (C) の計算に帰着させることができます。ここでは、重複組合せの基本的な考え方、特に重要な「仕切りモデル」、そして典型的な問題の解き方を解説します。
目次
第1章：重複組合せ (H) とは？
まず、重複組合せがどのような状況で使われ、通常の組合せとどう違うのかを理解しましょう。
1. 定義：重複を許して選ぶ組合せ
- 異なる n 種類のものの中から、重複を許して r 個を選ぶ組合せの総数を「n 種類から r 個取る重複組合せ」といい、記号 nHr または H(n, r) で表します。
- ポイント：
- 重複OK: 同じ種類を何個選んでも良い。
- 組合せ: 選ぶ順番は問わない（最終的に各種類を何個選んだかが重要）。
- n 種類から: 選ぶ対象は区別できる n 種類である。
2. 通常の組合せ (C) との違い
- 通常の組合せ (nCr): 異なる n 個の「具体的な物」から r 個を選ぶ。同じ物は選べない（非復元抽出）。
- 例：A, B, C, D, E の5人から3人を選ぶ → 5C3
- 重複組合せ (nHr): 異なる n 個の「種類」から、合計 r 個になるように選ぶ。同じ種類を繰り返し選んで良い。
- 例：りんご、みかん、バナナの3種類から、合計5個の果物を選ぶ（りんご5個でもOK）→ 3H5
3. 具体例：好きな果物を複数個買う
- りんご、みかんの2種類の果物から、重複を許して3個買う方法を考えます (n=2, r=3 なので 2H3)。
- 買い方をすべて書き出すと：
- {りんご, りんご, りんご}
- {りんご, りんご, みかん}
- {りんご, みかん, みかん}
- {みかん, みかん, みかん}
- この4通りが考えられます。よって 2H3 = 4 となります。（計算方法は後述）
第2章：重複組合せの考え方：「仕切り」と「ボール」
nHr の計算には、「仕切り ( | )」と「ボール ( ○ )」を使ったモデルで考えるのが最も理解しやすく、応用も利きやすいです。
1. モデルの説明：なぜ ○ と | で考えられるのか？
- 目的: n 種類の異なるものから、重複を許して r 個を選ぶ方法を数えたい。
- モデル化:
- 選ぶ r 個のものを、区別のない r 個の ボール (○) で表す。
- n 種類のものを区切るために、(n – 1) 個の 仕切り ( | ) を用意する。
- これら r 個のボールと (n – 1) 個の仕切りを一列に並べることを考える。
- 対応関係:
- 仕切りによって区切られた各領域にあるボールの数が、それぞれの種類を何個選んだかに対応します。
- 左から1番目の仕切りより左にあるボールの数 → 1種類目の個数
- 1番目と2番目の仕切りの間にあるボールの数 → 2種類目の個数
- …
- (n-1)番目の仕切りより右にあるボールの数 → n種類目の個数
- このように考えると、「n 種類から r 個を重複を許して選ぶ組合せ」と「r 個の ○ と (n – 1) 個の | を一列に並べる順列」が 1対1に対応します。
2. 具体例を用いたモデルの確認 (3H5 の例)
- 問題設定: 3種類 (A, B, C) のものから重複を許して 5個 (r=5) 選ぶ (n=3)。
- モデル:
- 5個のボール (○○○○○)
- (3 – 1) = 2個の仕切り ( | | )
- 合計 5 + 2 = 7 個のアイテムを一列に並べる。
- 並び方の例と対応:
- ○○|○○○| → 1番目の仕切りより左に○2個、間 に○3個、2番目より右に○0個 → A を 2個, B を 3個, C を 0個 選んだことに対応。
- |○○○○○| → A を 0個, B を 5個, C を 0個 選んだことに対応。
- ○○○○○|| → A を 5個, B を 0個, C を 0個 選んだことに対応。
- ○|○|○○○ → A を 1個, B を 1個, C を 3個 選んだことに対応。
- このように、7つの場所への ○ と | の並べ方一つ一つが、3種類から5個を選ぶ一つの組合せに対応していることがわかります。
3. 同じものを含む順列への帰着
- r 個の ○ と (n – 1) 個の | を一列に並べる順列の総数は、まさに「同じものを含む順列」の計算で求められます。
- 全体の個数： r + (n – 1) = n + r – 1 個
- ○ の個数： r 個
- | の個数： n – 1 個
- 同じものを含む順列の公式より、その総数は：
- (n + r – 1)! / {r! × (n – 1)!}
第3章：重複組合せの計算公式 (nHr)
「仕切りとボール」モデルから、nHr を計算するための公式を導き、使い方を学びましょう。
1. 公式：nHr = (n + r – 1)Cr
- n 種類から r 個取る重複組合せ nHr は、次の公式で計算できます。
- nHr = (n + r – 1)Cr
- または、nCr = nC(n-r) の性質を使うと、以下とも等しくなります。
- nHr = (n + r – 1)C(n – 1)
2. 公式の導出（仕切りモデルから）
- 前章で見たように、nHr の総数は、r 個の ○ と (n – 1) 個の | を一列に並べる順列の総数に等しく、それは (n + r – 1)! / {r! × (n – 1)!} でした。
- 一方、組合せの公式 nCr = n! / {r! × (n – r)!} を思い出してください。
- (n + r – 1)! / {r! × (n – 1)!} という式は、組合せの公式において、
- 全体の数 n に (n + r – 1) を、
- 選ぶ数 r に r を、
- (n – r) に (n + r – 1) – r = (n – 1) を
- 代入したものと同じ形をしています。
- つまり、(n + r – 1)! / {r! × (n – 1)!} = (n + r – 1)Cr となります。
- これは、「合計 (n + r – 1) 個の場所から、ボール (○) を置く r 個の場所を選ぶ組合せ」と解釈できます。残りの場所には自動的に仕切り (|) が入ります。
- 同様に、「合計 (n + r – 1) 個の場所から、仕切り (|) を置く (n – 1) 個の場所を選ぶ組合せ」と考えて (n + r – 1)C(n – 1) としても同じ結果になります。
3. 具体的な計算例
- 例1：2H3 の計算 (りんご、みかんの2種類から3個選ぶ)
- n = 2, r = 3
- 2H3 = (2 + 3 – 1)C3 = 4C3
- 4C3 = 4C1 = 4
- 第1章の具体例と一致します。
- 例2：3H5 の計算 (3種類から5個選ぶ)
- n = 3, r = 5
- 3H5 = (3 + 5 – 1)C5 = 7C5
- 7C5 = 7C2 = (7 × 6) / (2 × 1) = 21
- 例3：4H6 の計算
- n = 4, r = 6
- 4H6 = (4 + 6 – 1)C6 = 9C6
- 9C6 = 9C3 = (9 × 8 × 7) / (3 × 2 × 1) = (3 × 4 × 7) / 1 = 84
第4章：重複組合せの典型問題と解法
重複組合せは、特定のタイプの問題設定で頻繁に利用されます。
1. 問題タイプ1：重複を許す物の選び方（果物、お菓子など）
- 問題： りんご、みかん、バナナ、ももの4種類の果物の中から、重複を許して7個の果物を選ぶ方法は何通りあるか？ただし、含まれない種類の果物があってもよい。
- 考え方：
- 異なる n=4 種類から、重複を許して r=7 個選ぶ組合せ。
- まさに重複組合せ nHr の定義通り。
- 4H7 を計算する。
- 計算：
- 4H7 = (4 + 7 – 1)C7 = 10C7
- 10C7 = 10C3 = (10 × 9 × 8) / (3 × 2 × 1) = (10 × 3 × 4) / 1 = 120
- 答え： 120通り
2. 問題タイプ2：方程式の非負整数解の個数 (x+y+z=r, x≧0, y≧0, z≧0)
- 問題： 方程式 x + y + z = 8 を満たす非負整数解 (x, y, z) の組は何個あるか？ (x, y, z は 0 以上の整数)
- 考え方：
- これを「x, y, z の3種類のものから、合計で8個選ぶ重複組合せ」と解釈します。
- x：1種類目 (x) を選んだ個数
- y：2種類目 (y) を選んだ個数
- z：3種類目 (z) を選んだ個数
- 合計で r=8 個選びます。選ばない種類があっても良い (x=0 など)。
- したがって、n=3, r=8 として 3H8 を計算します。
- 仕切りモデルとの対応：
- 8個のボール (○) と (3-1)=2個の仕切り (|) を並べます。
- 例: ○○○|○○|○○○ → x=3, y=2, z=3 (合計8)
- 例: ||○○○○○○○○ → x=0, y=0, z=8 (合計8)
- 計算：
- 3H8 = (3 + 8 – 1)C8 = 10C8
- 10C8 = 10C2 = (10 × 9) / (2 × 1) = 45
- 答え： 45個
3. 問題タイプ3：方程式の正の整数解の個数 (x+y+z=r, x≧1, y≧1, z≧1)
- 問題： 方程式 x + y + z = 8 を満たす正の整数解 (x, y, z) の組は何個あるか？ (x, y, z は 1 以上の整数)
- 考え方：
- このままでは、x=0 などが許されないため、直接 3H8 は使えません。
- そこで、あらかじめ各変数に1ずつ割り当てておくという工夫をします。
- x, y, z は最低でも 1 なので、先に x, y, z に1つずつ配分します。合計3個配りました。
- 残りの (8 – 3) = 5 個を、x, y, z に自由に（0個でもOKで）振り分けると考えます。
- これは、「x, y, z の3種類に、合計5個を重複を許して割り振る」ことと同じです。
- つまり、3H5 を計算します。
- 置き換えによる考え方：
- x’ = x – 1, y’ = y – 1, z’ = z – 1 と置きます。
- x≧1, y≧1, z≧1 なので、x’≧0, y’≧0, z’≧0 となります。
- 元の式 x + y + z = 8 に x = x’ + 1, y = y’ + 1, z = z’ + 1 を代入すると、
- (x’ + 1) + (y’ + 1) + (z’ + 1) = 8
- x’ + y’ + z’ = 8 – 3 = 5
- この方程式を満たす非負整数解 (x’, y’, z’) の組の個数を求めればよく、これは問題タイプ2と同じ形です。
- n=3, r=5 として 3H5 を計算します。
- 計算：
- 3H5 = (3 + 5 – 1)C5 = 7C5
- 7C5 = 7C2 = (7 × 6) / (2 × 1) = 21
- 答え： 21個
第5章：まとめと注意点
重複組合せは「仕切り」モデルの理解が鍵となります。
1. 重複組合せ (nHr) のポイント整理
- 状況: 異なる n 種類から、重複を許して r 個を選ぶ組合せ（順番は問わない）。
- 考え方: r 個のボール (○) と (n – 1) 個の仕切り (|) を一列に並べる。
- 計算式: nHr = (n + r – 1)Cr (= (n + r – 1)C(n-1))
- 典型例: 物の選び方（在庫無限、選ばないものOK）、方程式の非負整数解。
2. 「仕切り」モデルの重要性
- 公式 nHr = (n+r-1)Cr だけを覚えても、なぜその計算になるのか、どのような問題に適用できるのかが分かりにくく、応用が利きません。
- 「仕切りとボール」のモデルを理解することで、様々な問題設定を重複組合せの考え方に帰着させることができます（特に方程式の整数解問題など）。
3. 混同しやすい概念（通常の組合せ、順列など）との比較
- vs 通常の組合せ (nCr): 重複を許すか許さないかが最大の違い。
- vs 通常の順列 (nPr): 選ぶだけでなく順番も区別するかどうかが違い。
- vs 同じものを含む順列 (n!/(p!q!…)): 使う場面が違う。nHr は「選ぶ」組合せ、同じものを含む順列は「すべてを並べる」順列。ただし、nHr の計算過程で「仕切りとボール」を並べる際に、同じものを含む順列の考え方（または組合せの考え方）が現れる。
- vs 重複順列 (n^r): 選んだものを順番も区別して並べるかどうかが違い（重複順列は順番も区別する）。
4. 注意事項
- 問題文の読解: 「重複を許すか？」「順番は関係あるか？」「選ぶ対象は『種類』か『具体的な物』か？」を正確に読み取ることが、nHr を使うべきか判断する上で非常に重要です。
- 整数解の条件: 方程式の整数解問題では、「非負整数 (0以上)」なのか「正の整数 (1以上)」なのかで、r の値や H の使い方が変わる点に注意が必要です。
潜在的なリスクについて:
この記事では、重複組合せの基本的な考え方と典型問題を中心に解説しました。最も重要なのは「仕切りとボール」のモデルを理解することですが、このモデル化に慣れないと、nHr を適用すべき問題を見抜けなかったり、n と r の値を誤って設定したりする可能性があります。公式 nHr = (n+r-1)Cr の暗記だけでは不十分であり、モデルに基づいた理解が不可欠です。また、方程式の整数解問題で「x≧2」のようなさらに複雑な条件が付く場合や、不等式で表される領域の格子点の数を数える問題など、より応用的な問題では、単純な公式適用だけでなく、さらなる工夫や場合分けが必要になることがあります。