【基本】組合せ

ここでは、組合せの総数を数える問題を考えます。順列のように並べることはしないで、選んだらおしまい、という点が違います。これが総数にどう影響するかを考えていきましょう。

【広告】

5人から3人を選ぶ

例題
大野、櫻井、相葉、二宮、松本の5人から3人を選んで新ユニットを作るとき、新ユニットの作り方は何通りあるか。

【基本】順列で見たように、「順列」は選んだ後に並べましたね。ここで考えるのは、選ぶだけです。順番は気にしません。

例えば、もし問題が「1列に並べる」となっていれば、次の3つの並べ方は「別物」とカウントします。

1. 大野、櫻井、相葉
2. 櫻井、相葉、大野
3. 相葉、大野、櫻井

しかし、3人を選ぶだけなら、上の3つはすべて同じものになります。ということは、「1列に並べ」たあとに、同じ組合せになるものをのぞけばいいですね。

上の例で挙げた「大野、櫻井、相葉」と同じ組合せになる並べ方は何通りあるでしょうか。これは、上にあげた3通り以外に、次のものがあります。

4. 大野、相葉、櫻井
5. 櫻井、大野、相葉
6. 相葉、櫻井、大野

よく見ると、「3人を1列に並べる」方法の数と一致しますね。

以上のことをまとめると、5人から3人を選んで並べる方法が ${}_5 \mathrm{ P }_3$ 通りあるが、同じ組合せになるものをそれぞれ $3!$ 回重複して数えることになるので\[ \frac{{}_5 \mathrm{ P }_3}{3!} = \frac{60}{6}=10 \]通りとなります。

なお、場合の数を数えるうえで樹形図は基本ですが、組合せの数を数えるのには適していません。樹形図は、基本的に「並べる」ものを数えるときに使うからです(根から順番に並んでいましたよね)。組合せの総数を数えるときには、いったん並べた後で、「同じ組合せになる、重複した並べ方をどう処理するか」を考慮して数えるようにします。

組合せ

上の例題のように n 個の異なるものから r 個を選ぶ方法(順序は考慮しない)を、組合せ(combination)といいます。この組合せの総数は、combinationの頭文字 C を使って、 ${}_n \mathrm{ C }_r$ と書きます。 C の左下に全体の数、右下に選ぶ数を書きます。例題であれば、 ${}_5 \mathrm{ C }_3$ となります。順列のときに用いた ${}_n \mathrm{ P }_r$ の記号とよく似ていますね。

${}_n \mathrm{ C }_r$ をもう少し具体的に書いてみましょう。例題のときと同じように、まず n から r 個を選んで並べます。これは ${}_n \mathrm{ P }_r$ 通りあります。この中で、同じ組合せになる並べ方をそれぞれ $r!$ 回重複して数えることになるので\[ {}_n \mathrm{ C }_r = \frac{{}_n \mathrm{ P }_r}{r!} \]となります。また、この分子は、 n から $n-r+1$ までの整数の積、分母は r から $1$ までの整数の積なので、次のようにまとめることができます。

${}_n \mathrm{ C }_r$
$n\geqq r$ とする。異なる n 個のものから r 個を選ぶ組合せの総数は、次のとおり。
\begin{eqnarray}
{}_n \mathrm{ C }_r
&=&
\frac{{}_n \mathrm{ P }_r}{r!} \\[5pt] &=&
\frac{ n(n-1)(n-2)\cdots (n-r+1) }{ r(r-1)\cdots 2\cdot 1 }
\end{eqnarray}

上の式を使うと、例題は
\begin{eqnarray}
{}_5 \mathrm{ C }_3
&=&
\frac{ 5\cdot4\cdot3 }{ 3\cdot2\cdot1 } \\[5pt] &=&
10 \\[5pt] \end{eqnarray}通りとなります。

また、特殊なケースを考えると、 ${}_n \mathrm{ C }_n=1$ となります。分母・分子がともに $n!$ になるからです。 n 個のものから n 個を選ぶ、ということは、全部選ぶのだから1通りなのは当然ですね。

変わった例ですが、 ${}_n \mathrm{ C }_0=1$ も成り立ちます。【標準】順列で見たように、 ${}_n \mathrm{ P }_0=1$, $0!=1$ を代入して得られます。n 個のものから 0 個を選ぶ、というのは不自然な状況ですが、1通りと数えます。

おわりに

ここでは、組合せの総数について考えました。順列と組合せを学ぶと、これからはその違いについてよく考えなければいけなくなります。何を区別するのか、何を重複とみなすのかを考えながら、問題を解くようにしていきましょう。