数学A / 場合の数と確率
重複組合せと二項定理との関係
要点整理
重複組合せとは何か
前のページでは、$n$ 個の異なるものから $r$ 個を、順序を区別せずに選ぶ場合の数を、組合せ ${}_n\mathrm{C}_r$ として学びました。組合せでは、同じものを2回選ぶということは考えません。たとえば5人の中から3人を選ぶとき、同じ人をもう一度選ぶことはできませんね。
ここで学ぶ重複組合せは、「同じものを何度選んでもよい」という条件をつけた組合せのことです。たとえば、赤・青・黄の3種類の玉があり、これらの中から重複を許して(同じ色の玉を何個選んでもよいものとして)合計4個を選ぶ場合の数を考える、というような問題です。
この場合の数は、記号 ${}_n\mathrm{H}_r$ で表します。$n$ が種類の数、$r$ が選ぶ個数です。(Hの由来には諸説ありますが、"Homogeneous"(同種の)に由来するという説がよく紹介されます。)
重複組合せの公式を作る
${}_n\mathrm{H}_r$ の値を、すでに知っている組合せ ${}_n\mathrm{C}_r$ を使って求める公式を作っていきます。
$n$ 種類のもの(種類1、種類2、……、種類$n$)から、重複を許して合計 $r$ 個選ぶとします。それぞれの種類を何個ずつ選んだかを、
$x_1 + x_2 + \cdots + x_n = r$
という式で表すことができます。ここで $x_1, x_2, \ldots, x_n$ は、それぞれ種類1、種類2、……、種類$n$を選んだ個数を表す文字で、どれも0以上の整数(0, 1, 2, 3, …のいずれか)です。つまり、重複組合せの場合の数を求めることは、この式を満たす0以上の整数の組 $(x_1, x_2, \ldots, x_n)$ の個数を数えることと同じになります。
この個数を数えるために、「○」と「|」という2種類の記号を1列に並べる方法を使います。
- 選んだ合計 $r$ 個を、$r$ 個の「○」で表します。
- $n$ 種類を区切るための仕切りとして、「|」を $(n-1)$ 個使います(仕切りが $n-1$ 本あれば、玉の並びは $n$ 個のグループに分かれます)。
たとえば $n=3$(種類が3つ)、$r=4$(選ぶ個数が4個)のとき、
$\text{○○|○|○}$
という並び方は、「種類1を2個、種類2を1個、種類3を1個選んだ」ことを表します。並べる記号は、○が4個と|が2個で、合計6個です。
一般に、○は $r$ 個、|は $(n-1)$ 個なので、記号は全部で $r+(n-1)$ 個並びます。この $r+(n-1)$ 個の位置のうち、○を置く $r$ 個の位置を決めれば、並び方がひとつに決まります(残りの位置には自動的に|が入るからです)。これは、$r+(n-1)$ 個の位置から $r$ 個を選ぶ組合せの数、つまり ${}_{n+r-1}\mathrm{C}_r$ に等しいので、次の公式が得られます。
${}_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r$
(○を置く位置の代わりに|を置く位置を決めても同じ並び方が決まるので、${}_n\mathrm{C}_r={}_n\mathrm{C}_{n-r}$ の性質より ${}_{n+r-1}\mathrm{C}_r = {}_{n+r-1}\mathrm{C}_{n-1}$ とも書けます。)
例:赤・青・黄の3種類($n=3$)から、重複を許して4個($r=4$)選ぶ場合の数は、
${}_3\mathrm{H}_4 = {}_{3+4-1}\mathrm{C}_4 = {}_6\mathrm{C}_4$
です。${}_n\mathrm{C}_r={}_n\mathrm{C}_{n-r}$ の性質を使うと ${}_6\mathrm{C}_4={}_6\mathrm{C}_2$ なので、
${}_6\mathrm{C}_2 = \frac{6\times5}{2\times1} = 15$
より、15通りとわかります。
二項定理を振り返る
ここで、いったん別の定理である二項定理を確認しておきます。二項定理とは、$(a+b)^n$ を展開したときの各項の係数を求める定理で、次のように表されます。
$(a+b)^n = \sum_{k=0}^{n} {}_n\mathrm{C}_k\, a^{n-k}b^k$
右辺にある $\displaystyle\sum_{k=0}^{n}$ は、シグマ記号(総和記号)と呼ばれるもので、「$k$ を $0$ から $n$ まで1つずつ変えながら、その後ろの式($_n\mathrm{C}_k a^{n-k}b^k$)を全部足し合わせる」という意味です。つまり二項定理は、
$(a+b)^n = {}_n\mathrm{C}_0\,a^n + {}_n\mathrm{C}_1\,a^{n-1}b + {}_n\mathrm{C}_2\,a^{n-2}b^2 + \cdots + {}_n\mathrm{C}_n\,b^n$
という展開を表しています。
なぜ各項の係数が ${}_n\mathrm{C}_k$ になるのかを、確認しておきましょう。$(a+b)^n$ は、$(a+b)$ を $n$ 個かけ合わせたものです。これを展開するというのは、$n$ 個の $(a+b)$ のそれぞれから「$a$」か「$b$」のどちらか一方を選び出し、その $n$ 個の選んだ文字をすべてかけ合わせる、という操作を、選び方をいろいろ変えながらすべて行い、最後にそれらを足し合わせる、という作業です。
このとき、$n$ 個の $(a+b)$ のうち、ちょうど $k$ 個から $b$ を選び、残りの $(n-k)$ 個から $a$ を選ぶと、その積は $a^{n-k}b^k$ になります。$n$ 個の $(a+b)$ のうち、どの $k$ 個から $b$ を選ぶかという選び方の数は、$n$ 個の中から $k$ 個を選ぶ組合せなので ${}_n\mathrm{C}_k$ 通りです。これが $a^{n-k}b^k$ の係数が ${}_n\mathrm{C}_k$ になる理由です。
重複組合せと二項定理の関係
ここが、このページでいちばん大事なところです。上で確認した「$n$ 個の $(a+b)$ のそれぞれから $a$ か $b$ を選ぶ」という操作は、実は「$a$ と $b$ という2種類の文字から、重複を許して合計 $n$ 個選ぶ」重複組合せそのものになっています。
確かめてみましょう。$a$ を $(n-k)$ 個、$b$ を $k$ 個選ぶという組み合わせは、「$a$, $b$ の2種類から、重複を許して合計 $n$ 個選ぶ」選び方の1つです。$k$ は $0, 1, 2, \ldots, n$ のどれかの値をとるので、こうした選び方(=展開したときにできる項の種類)は全部で $(n+1)$ 通りあります。
これを重複組合せの公式を使って確認してみます。重複組合せの公式 ${}_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r$ において、種類の数の部分に $2$($a$ と $b$ の2種類)、選ぶ個数の部分に $n$(二項定理の指数と同じ $n$ 個)を当てはめると、
${}_2\mathrm{H}_n = {}_{2+n-1}\mathrm{C}_n = {}_{n+1}\mathrm{C}_n$
となります。ここで ${}_n\mathrm{C}_r={}_n\mathrm{C}_{n-r}$ の性質を使うと、
${}_{n+1}\mathrm{C}_n = {}_{n+1}\mathrm{C}_{(n+1)-n} = {}_{n+1}\mathrm{C}_1 = n+1$
となり、確かに $(n+1)$ 通りと一致します。これは、二項定理で $(a+b)^n$ を展開したときにできる項の数($a^n, a^{n-1}b, \ldots, b^n$ の $(n+1)$ 個)と、ぴったり同じ数です。
つまり、二項定理の各項は、「$a$ と $b$ の2種類から重複を許して $n$ 個選ぶ重複組合せ」と1対1に対応しているのです。文字の種類をさらに増やして $a, b, c$ の3種類にすると、$(a+b+c)^n$ を展開したときにできる項の種類の数は、重複組合せの考え方を使って ${}_3\mathrm{H}_n$ で求めることができます。このように、二項定理を3種類以上の文字に拡張したものを多項定理と呼びます。
例題
例題1(基本)
問題
みかん、りんご、ぶどうの3種類の果物がある。これらの中から、重複を許して(同じ果物を何個選んでもよいものとして)合計5個選ぶとき、その選び方は何通りあるか。
解答・解説を見る
3種類の果物から、重複を許して5個選ぶ場合の数を求めるので、これは重複組合せの問題です。種類の数を $n=3$、選ぶ個数を $r=5$ として、公式
${}_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r$
に当てはめます。
${}_3\mathrm{H}_5 = {}_{3+5-1}\mathrm{C}_5 = {}_7\mathrm{C}_5$
ここで、組合せの性質 ${}_n\mathrm{C}_r = {}_n\mathrm{C}_{n-r}$ を使うと、
${}_7\mathrm{C}_5 = {}_7\mathrm{C}_{7-5} = {}_7\mathrm{C}_2$
${}_7\mathrm{C}_2$ を計算します。
${}_7\mathrm{C}_2 = \frac{7\times6}{2\times1} = \frac{42}{2} = 21$
よって、選び方は 21通り です。
例題2(標準)
問題
$x+y+z=8$ を満たす0以上の整数の組 $(x, y, z)$ は何組あるか。
解答・解説を見る
この問題は、一見すると重複組合せとは関係のない方程式の問題に見えますが、要点整理で確認した通り、「$x_1+x_2+\cdots+x_n=r$ を満たす0以上の整数の組の個数」は「$n$ 種類のものから重複を許して $r$ 個選ぶ場合の数」と同じ考え方で数えられます。
ここでは、$x, y, z$ という3種類のもの($n=3$)から、重複を許して合計8個($r=8$)選び、$x$ を選んだ回数が $x$ の値、$y$ を選んだ回数が $y$ の値、$z$ を選んだ回数が $z$ の値になる、と考えれば対応がつきます。したがって、求める組の個数は ${}_3\mathrm{H}_8$ です。
公式 ${}_n\mathrm{H}_r={}_{n+r-1}\mathrm{C}_r$ に $n=3$、$r=8$ を当てはめると、
${}_3\mathrm{H}_8 = {}_{3+8-1}\mathrm{C}_8 = {}_{10}\mathrm{C}_8$
${}_n\mathrm{C}_r={}_n\mathrm{C}_{n-r}$ の性質を使うと、
${}_{10}\mathrm{C}_8 = {}_{10}\mathrm{C}_{10-8} = {}_{10}\mathrm{C}_2$
${}_{10}\mathrm{C}_2$ を計算します。
${}_{10}\mathrm{C}_2 = \frac{10\times9}{2\times1} = \frac{90}{2} = 45$
よって、条件を満たす整数の組は 45組 です。
例題3(応用)
問題
$(a+b+c)^4$ を展開して同類項をまとめたとき、異なる項(単項式)は何種類できるか。重複組合せの考え方を用いて求めよ。
解答・解説を見る
$(a+b+c)^4$ は、$(a+b+c)$ を4個かけ合わせたものです。
$(a+b+c)^4 = (a+b+c)(a+b+c)(a+b+c)(a+b+c)$
これを展開するというのは、4個の $(a+b+c)$ のそれぞれから「$a$」「$b$」「$c$」のいずれか1つを選び出し、その4個の文字をすべてかけ合わせる、という操作を、選び方をいろいろ変えながらすべて行い、最後にそれらを足し合わせる作業です。
ここで、それぞれの選び方でできる積(たとえば $a\times b\times a\times c$)は、かけ算の順序を並べ替えても値が変わらないので、同じ組み合わせで文字を選べば同じ単項式($a^2bc$ など)になります。つまり、できあがる単項式の種類は、「$a, b, c$ の3種類の文字から、重複を許して(同じ文字を何回選んでもよいものとして)合計4個選ぶ」選び方の種類と、ちょうど1対1に対応しています。
これは重複組合せの考え方そのものなので、種類の数 $n=3$、選ぶ個数 $r=4$ として公式に当てはめます。
${}_3\mathrm{H}_4 = {}_{3+4-1}\mathrm{C}_4 = {}_6\mathrm{C}_4$
${}_n\mathrm{C}_r={}_n\mathrm{C}_{n-r}$ の性質を使うと、
${}_6\mathrm{C}_4 = {}_6\mathrm{C}_2 = \frac{6\times5}{2\times1} = 15$
よって、異なる項は 15種類 できます。
これは、要点整理で扱った「赤・青・黄の3種類から重複を許して4個選ぶ場合の数」の計算とまったく同じ式・同じ答えになっていることに気づいたでしょうか。玉を選ぶ問題も、多項式を展開して項の種類を数える問題も、数学的には同じ「重複組合せ」の問題なのです。
練習問題
問題
$(a+b)^7$ を展開したときにできる項の数を、重複組合せの考え方を用いて求めよ。また、二項定理の一般項 ${}_7\mathrm{C}_k\,a^{7-k}b^k$ の $k$ が動く範囲から数えた結果と一致することを確認せよ。
答え
$a, b$ の2種類($n=2$)から重複を許して7個($r=7$)選ぶ場合の数を考えて、
${}_2\mathrm{H}_7 = {}_{2+7-1}\mathrm{C}_7 = {}_8\mathrm{C}_7 = {}_8\mathrm{C}_1 = 8$
より、8個。
二項定理では $k$ が $0, 1, 2, \ldots, 7$ の8通りの整数値をとるので、項の数はやはり8個であり、一致する。