【基本】組合せ

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

5人から3人を選ぶ

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

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

1. A, B, C
2. B, C, A
3. C, A, B

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

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

4. A, C, B
5. C, B, A
6. B, A, C

よく見ると、「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$ までの整数の積なので、次のようにまとめることができます。

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

この式\[ \frac{ n(n-1)(n-2)\cdots (n-r+1) }{ r(r-1)\cdots 2\cdot 1 } \]は複雑そうに見えるかもしれません。しかし、分子は $n$ から順番に $r$ 個、分母は $r$ から順番に $r$ 個の整数が表れている、というだけなので、実は見た目ほど怖くはありません。

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

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

おわりに

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