数学A「場合の数」の発展事項として登場する「重複組合せ」。
重複組合せの公式は少しとっつきにくいので、苦手意識を持っている方もいると思います。
でもその本質は〇と仕切りの並べ方を考えているだけ！
この仕組みが理解できていれば、公式を覚える必要もありません。
本記事では、重複組合せの意味や公式、具体例について解説をしていきます。
✓本記事の内容
・重複組合せとは
・〇と｜を用いた求め方
・重複組合せの公式
・重複組合せの練習問題
・整数解問題への応用
重複組合せとは?
重複組合せとは「重複」を許して選ぶ組合せのこと
※「重複」は「ちょうふく」と読みます
では、次の例を見てみましょう。
例題
「赤、青、黄」3種類の玉がそれぞれたくさんある。
ここから重複を許して、5個の玉を選ぶとき選び方は何通りあるか。
選び方の例を挙げてみると
などが挙げられます。
①では、赤と青を重複してそれぞれ2個ずつ選んでいます。
②では、青１個、黄を重複して4個選んでいます。赤は選んでいません。
③では、5個すべて赤を選んでいます。
このように同じ色のものを何度選んでもよいという条件のもとで、その組み合わせを考えるのが重複組合せです。
組合せなので色の順番は考えません。また、選ばない色があってもよく、③のようにすべて同じ色でも構いません。
これをまともに数えると大変なので、次のような工夫をしてみます。
重複組合せの考え方
先ほどと同じ例で考えてみましょう。
例題
「赤、青、黄」3種類の玉がそれぞれたくさんある。
ここから重複を許して、5個の折り紙を選ぶとき選び方は何通りあるか。
例えば、先ほどの①の並べ方「赤赤青青黄」について、それぞれの色を〇で表し、異なる色の間に仕切り線｜を入れてみます。すると次の図のようになります。
この図を頭に入れたうえで、次の説明を見てください。
【重複組合せの考え方】
（１）５個の玉が入る５個の〇と、３色の色を区別する２つの仕切り｜の並べ方を考える。つまり
〇〇〇〇〇｜｜
の並べ方を考える。
（２）（１）の並べ方それぞれに対して、左の仕切りの左側に赤玉を入れ、左の仕切りと右の仕切りの間に青玉を入れ、右の仕切りの右側に赤玉を入れる。
＜例＞
すると、「 〇と｜の並べ方 」と「 玉の選び方 」が１対１に対応する
「 〇と｜の並べ方 」と「 玉の選び方 」が１対１に対応している例を、いくつか挙げておきます。
以上のことをまとめると
「 玉の選び方の総数 」は
「 〇〇〇〇〇｜｜ の並べ方の総数 」と同じ！
ということが言えます。
よって、解答は次のようになります。
【解答】
３種類の玉から重複を許して５個取る組合せの総数は、５個の〇と２個の｜の順列の総数と等しい。
よって、求める組合せの総数は、７個の場所から〇を置く５個の場所を選ぶ場合を考えて
\[ {}_7{\rm C}_5={}_7{\rm C}_2=\frac{7\cdot 6}{2\cdot 1}=21（通り）\]
同じものを含む順列の公式を使って
\[ \frac{7!}{5!2!}=21 (通り) \]
とすることも可能です。
重複組合せの公式
ここでは、次の重複組合せの公式を導いてみます。
異なる\( n \) 個のものから重複を許して\( r \) 個取る組合せの総数は
\[ {}_{n+r-1}{\rm C}_{r} \]
先ほどの玉を取り出す重複組合せと同様に考えます。
異なる\( n \) 個のものから重複を許して\( r \) 個取る組合せの総数は、\( r \) 個の〇と\( (n-1) \) 個の|を並べる順列の総数に等しい。
すなわち、\( r+(n-1) \) 個の場所から\( r \) 個の場所を選ぶ方法の総数に等しい。
よって、求める総数は
\[ {}_{n+r-1}{\rm C}_{r} \]
\( n \) 種類のものを分けるためにの仕切りは、\( n \)個より１つ少ない, \( n-1 \) 個であることに注意しましょう。
さらに、異なる\( n \) 個のものから重複を許して\( r \) 個取る組合せの総数を
\[ {}_n {\rm H} _r\]
と表すこともあります。
これをまとめると次のようになります。
異なる\( n \) 個のものから重複を許して\( r \) 個取る組合せの総数\( {}_n {\rm H} _r\) は
\[ {}_n {\rm H} _r={}_{n+r-1}{\rm C}_{r} \]
※重複組合せの公式は覚える無理に覚えなくても大丈夫です。〇と｜を並べる考え方を押さえておけば十分です。
重複組合せ【練習問題】
それでは、練習問題です。
問題
4個の文字\( a,\; b,\; c,\; d\) から重複を許して6個取る組合せの総数を求めよ。
解答
求める総数は\( a,\; b,\; c,\; d\) が入る６個の〇と、これらを分ける３個の仕切り｜を並べる順列の総数に等しい。
すなわち，〇〇〇〇〇〇｜｜｜ を並べる順列の総数に等しい。
よって
\[ {}_{9}{\rm C}_{6}={}_{9}{\rm C}_{3}=\frac{9\cdot 8 \cdot 7}{3\cdot 2 \cdot 1} =84 (通り) \]
次のように公式を用いる方法もあります。
別解
異なる4個のから6個取る重複組合せなので、公式を用いて
\[ {}_4 {\rm H} _6={}_{4+6-1}{\rm C}_{6}={}_{9}{\rm C}_{6}={}_{9}{\rm C}_{3}=84 (通り) \]
重複組合せを動画で学びたい方へ
Udemyで公開されている次のコースをおすすめします。
■【完全マスター】数学講師が教えるゼロからの「場合の数・確率」入門
教科書レベルの「場合の数・確率」をゼロから一歩ずつ、網羅的に学べるコースです。
＜コースの特徴＞
✔︎数学講師が丁寧に分かりやすく解説
✔︎高校の教科書レベルの内容をほぼカバー
✔︎定理や公式の仕組みまで学べる
✔︎効率よく学べるように編集済み
✔︎7時間のボリューム
✔︎豊富な練習問題
「排反事象」「確率の加法定理」「独立」「反復試行」「条件つき確率」「乗法定理」「原因の確率」・・・など、確率で登場する様々な定理や概念をきちんと理解していくことを目標にしたコースです。
もちろん「重複組合せ」についても扱っています。
ぜひこの機会に、「場合の数・確率」の基礎固めをしてみませんか？
整数解の問題
重複組合せは整数解の組を求める問題に利用できます。
非負の整数解の組を求める問題
問題１
\( x+y+z=7\; \) かつ\( \; x\geqq 0,\; y \geqq 0,\; z \geqq 0 \; \) を満たす整数\(x,\; y,\; z \) の組\( (x,\; y,\; z)\) は、全部で何組あるか。
考え方
\( x,\; y,\; z\; \) は負でない整数であることに注目し、右辺の７を７個の〇で表します。
ここで、７個の〇を2個の仕切りで３つに分け、〇の数を左からそれぞれ\( x,\; y,\; z\)の値に対応させます。例えば
〇〇| 〇〇〇｜〇〇 → \( (x,\; y,\; z)=(2,\; 3,\; 2) \)
〇〇〇〇〇｜〇|〇 → \( (x,\; y,\; z)=(5,\; 1,\; 1) \)
〇〇〇〇||〇〇〇 → \( (x,\; y,\; z)=(4,\; 0,\; 3) \)
というように，〇と｜の並べ方と１対１に対応させます。
解答
求める組は，７個の〇と２個の仕切り｜の並べ方と１対１に対応する。
〇〇〇〇〇〇〇｜｜の順列を考えて
\[{}_{9}{\rm C}_{7}={}_9{\rm C}_2=36 (組) \]
となります。
正の整数解の組を求める問題
問題２
\( x+y+z=7\; \) を満たす正の整数\(x,\; y,\; z \) の組\( (x,\; y,\; z)\) は、全部で何組あるか。
考え方
問題１と似ていますが、\( x,\; y,\; z \) は正の整数ですので注意が必要です。
「正の整数」は「1以上の整数」と言い換えることができるので、問題を書き直すと次のようになります。
問題２（言い換え）
\( x+y+z=7\; \) かつ\( \; x\geqq 1,\; y \geqq 1,\; z \geqq 1 \; \) を満たす整数\(x,\; y,\; z \) の組\( (x,\; y,\; z)\) は、全部で何組あるか。
問題１との違いに注意してください。
この問題の場合、\( x,\; y,\; z \) は0にはならないので，７個の〇と２個の仕切り｜を並べる方法は使えません。
なぜならば、
｜〇〇〇｜〇〇〇〇 → \( (x,\; y,\; z)=(0,\; 3,\; 4) \)
〇〇〇｜｜〇〇〇〇 → \( (x,\; y,\; z)=(3,\; 0,\; 4) \)
のように，仕切り｜が両端に来たり、連続して２つ並ぶと、\( x,\; y,\; z \) の中で０になるものが出てきてしまうからです。
これを回避する方法が２つあります。
解答１で解説する方法は
\( x-1 =X,\;\; y-1 =Y,\;\; z-1=Z \)
とおいて，
\( X\geqq 0,\; Y\geqq 0,\; Z\geqq 0\)
のように\( 0\) を含んでもよい整数\( X,\; Y,\; Z \) の式を考える方法。
解答２で解説する方法は，全く別の方法になります。
解答１
\( x-1 =X,\; y-1 =Y,\; z-1=Z \) とおくと
\( \; x\geqq 1,\; y \geqq 1,\; z \geqq 1 \; \)より
\[ X\geqq 0,\; Y\geqq 0,\; Z\geqq 0\]
ここで、\( x+y+z=7 \) の式を\( X,\; Y,\; Z \) で表すと
\[ (X+1)+(Y+1)+(Z+1) =7 \]
となる。これを変形すると
\[ X+Y+Z=4,\quad X\geqq 0,\; Y\geqq 0,\; Z\geqq 0\cdots ①\]
となる。したがって、求める正の整数解の組の個数は、①を満たす0以上の整数解\( X,\; Y,\; Z\) の組の個数に等しい。
よって、４個の〇と２個の仕切り｜の順列の総数を求めて
\[ {}_6{\rm C}_4={}_6{\rm C}_2=15 (組) \]
次にご紹介する別解はおすすめです。
解答２
右辺の７を、７つの〇で表す。
〇〇〇〇〇〇〇
ここで、〇と〇の間６カ所から２カ所を選んで仕切りを入れ、左の仕切りの左側にある〇の数を\( x\) 、左と右の仕切りの間にある〇の数を\( y \) 、右の仕切りよりも右側にある〇の数を\( z \) とすると、解が１つに決まる。よって
\[ {}_6{\rm C}_4={}_6{\rm C}_2=15 (組) \]
問題２については、重複組合せではありませんが、簡単な方法なのでおすすめです。
まとめ
今回は重複組合せについて解説をしました。
・重複組合せとは
・〇と｜を用いた求め方
・重複組合せの公式
・重複組合せの練習問題
・整数解問題への応用
重複組合せの問題では、無理に公式を覚えて使うよりも、〇と｜を並べる考え方を使うと分かりやすくなります。〇と｜を使った考え方は様々な問題に活用することもできて非常に便利です。
繰り返し練習を積み上げて、重複組合せの考え方を身につけていきましょう。
