ホーム >> 場合の数 >> 重複組合せの考え方



⇨予備知識


重複組合せとは

異なる $n$ 個のものから異なる $r$ 個を取り出す組合せの総数は ${}_n \mathrm{C}_r$ でした.(→組合せの基礎) では,異なる $n$ 個のものから,重複を許して $r$ 個取り出す組合せの総数はいくつになるでしょうか. これを,$n$ 個から $r$ 個選ぶ重複組合せといいます.
たとえば,$A,B,C,D$ の $4$ 種類の記号から,重複を許して $3$ 個選ぶ組合せの総数はつぎのように,全部で $20$ 通りあります.
重複組合せ
さて,一般の重複組合せの総数はどのような値になるでしょうか.実は,重複組合せの総数を求める公式があるので,ひとつひとつ数え上げなくてもよいのです.

重複組合せの考え方

重複組合せの総数を知るためのアイデアは,$r$ 個の $\bigcirc$ と $n-1$ 本のしきり $|$ を一列に並べる,というものです.

たとえば,先ほどの例で考えてみましょう.$3$ つの $\bigcirc$ と $3$ 本のしきり $|$ を用意します.$\{A,A,B\},\{B,C,D\},\{A,C,C\}$ などはそれぞれつぎの $\bigcirc$ と $|$ の順列に対応します.
重複組合せの考え方
つまり,左から $1$ 番目の $|$ より左側にある $\bigcirc$ には $A$ を,$1$ 番目の $|$ と $2$ 番目の $|$ の間にある $\bigcirc$ には $B$ を,$2$ 番目の $|$ と $3$ 番目の $|$ の間にある $\bigcirc$ には $C$ を,$3$ 番目の $|$ より右側にある $\bigcirc$ には $D$ を対応させます.
すると,重複組合せはこの順列と一対一に対応します.したがって,求める組合せの総数は,$6$ 個の場所から $\bigcirc$ をいれる $3$ 個の場所を選ぶ方法の総数に等しいので, $${}_{6} \mathrm{C} _{3}=20$$ $20$ 通りです.

上記の考え方を一般化させると次の公式を得ます.

重複組合せ: 異なる $n$ 個のものから重複を許して $r$ 個選ぶ組合せの総数は $\large {}_{n+r-1} \mathrm{C} _r$


注意

・異なる $n$ 個のものから重複を許して $r$ 個選ぶ組合せの総数を ${}_n \mathrm{H} _r$ という記号で表すことがあります.ところが,上の考察より,${}_n \mathrm{H} _r={}_{n+r-1} \mathrm{C} _r$ であることがわかっているので,この ${}_n \mathrm{H} _r$ という記号は特に必要ありません.$\bigcirc$ と $|$ を並べるというアイデアさえ知っていれば,いつでも重複組合せの公式は作り出せるのです.

・$\bigcirc$ の個数と,しきり $|$ の本数が,どちらが何個でどちらが何個かは混乱しやすい (忘れやすい) ので注意が必要です.これらは,覚えなくとも意味を考えれば間違えません.$\bigcirc$ は取り出すものの個数です.それを $n$ 種類に分配するので,しきりが $n-1$ 本必要なのです.そのような自分なりのイメージを持っておくことが大切だと思います.

重複組合せと整数解の個数

典型的な重複組合せを用いる問題として,整数解の個数を求めるタイプの問題があります.

例題 $x+y+z=8$ を満たす非負整数 ($0$ 以上の整数)の組 $(x,y,z)$ の総数を求めよ.

たとえば,$(1,2,5),(2,2,4),(0,1,7)$ などが条件を満たす非負整数解の組です.念のため注意しておくと,$(2,2,4)$ と $(4,2,2)$ などは異なる組として区別します.

さて,この問題を重複組合せの考え方で解いてみましょう.$8$ 個の $\bigcirc$ と,$2$ 本の仕切り $|$ を適当に一列に並べると,そのひとつの並び方が上の問題のひとつの整数解の組に対応します.
重複組合せ
よって,求める整数解の個数は ${}_{10} \mathrm{C} _2=45$ 通りです.つまり,この問題は,『異なる $3$ 種類のものから重複を許して $8$ 個選ぶ組合せは何通りあるか』という問いの完全な言い換えです.

では,つぎの似て非なる問題はどうでしょうか.

例題 $x+y+z=8$ を満たす正の整数の組 $(x,y,z)$ の総数を求めよ.

さきほどの問題との違いは,非負整数か,正の整数かの違いです.すなわち,$0$ を含めるか,含めないかです.今回の問題は $0$ を含めません.したがって,$x,y,z$ がすべて $1$ 以上であるような解を考えます.

この問題は,先に分配しておくというアイデアでさきほどの問題のタイプに帰着できます.つまり,$x,y,z$ それぞれに先に $1$ ずつあげてしまうのです.要するに, $$X=x-1,Y=y-1,Z=z-1$$ という式変形をします.すると,問題の等式は,$X+Y+Z=5$ になります.そして,$x,y,z$ は正の整数なので,$X,Y,Z$ は非負整数です.したがって,この問題は,『$X+Y+Z=5$ を満たす非負整数の組 $(X,Y,Z)$ の総数を求めよ.』という問題と同じです.よって,求めるべき総数は, ${}_7 \mathrm{C} _2=21$ です.

さきほどの問題の答え $45$ から,$0$ を含む整数解の総数 $24$ を引いて求める方法でも解けます.

練習問題

 $6$ つの碁石を $3$ 人に分ける方法の総数はいくつか.ただし,ひとつも碁石がもらえない人がいてもよいとする.

→solution

碁石は区別できず,人は区別できると考える.求める組合せは $6$ つの $\bigcirc$ と $2$ つのしきり $|$ を一列に並べる順列と等しい.したがって,${}_{8} \mathrm{C} _{2}=28$ 通り.

 $n$ 個の区別のつくサイコロを同時に投げたとき,目の和が $n+5$ となる場合の数はいくつか.

→solution

サイコロの目は $1$ 以上なので,$5$ を $n$ 個のサイコロでどう分配するかのみを考えれば良い.したがって,求める場合の数は,$5$ つの $\bigcirc$ と $n-1$ 個のしきり $|$ を並べる順列の総数に等しい.よって,${}_{n+4} \mathrm{C} _{5}$ 通り.