組み合わせ

異なる \(n\) 個から \(r\) 個取り出す組み合わせの総数 \({}_n C_r\) は次のような形で書けます。

\[ \begin{aligned} {}_n C_r &= \frac{n!}{r!(n-r)!} \end{aligned} \]

この記事ではこの式を導きます。

「順列」の知識が必要です。不安な人は先にそちらをみておいてください。

まずは具体例から。5 個から 3 個選ぶ組み合わせの数は？

今、 5 個のアルファベット \(A\), \(B\), \(C\), \(D\), \(E\) があって、そこから 3 個選んで取り出すのが何通りか考えましょう。

ひとつのパターンとして、今 \(A\), \(B\), \(C\) を取り出したとします。

\(A\), \(B\), \(C\) を順番に並べる方法は「順列」でみたように、 1 個目として \([A, B, C]\) の 3 パターン、2 個目として残りの 2 つから選ぶ 2 パターン、3 個目は自動的に決まるので、 \(3 \times 2 \times 1 = 3! \) パターンあります。

ここでもし、5 個から 3 個取り出す組み合わせが \({}_5 C_{3}\) 通りあるとします。

すると、順列の数は「コンビネーション数 \({}_5 C_{3}\)」× 「コンビネーション毎の並べ替え数 \(3!\)」ですから、

\[ {}_5 C_{3} \times 3! \]

であることがわかります。

一方、「順列」でみたように、\(n\) 個から \(r\) 個をとる順列は \({}_n P_r\) です。従って今回の例のように \(5\) 個から \(3\) 個をとる順列は

\[ {}_5 P_3 = \frac{ 5! }{( 5 - 3 )!} \]

です。

上の 2 式はどちらも等しいので、結局

\[ \begin{aligned} {}_5 C_{3} \times 3! &= \frac{ 5! }{( 5 - 3 )!} \\ \therefore \quad {}_5 C_{3} &= \frac{ 5! }{ 3! (5-3)! } \\ &= \frac{ 5 \cdot 4 \cdot 3 \cdot \cancel{ 2 \cdot 1} }{ 3 \cdot 2 \cdot 1 \cdot \cancel{ 2 \cdot 1 }}\\ &= \frac{ 5 \cdot 4 \cdot 3}{ 3 \cdot 2 \cdot 1} \\ &= 10 \end{aligned} \]

となり、コンビネーションの数は \(10\) 個であることがわかりました。

一般化して書くと

これを一般化すると、次のようになります。

何をしているかわからなくなったら、具体的な数字を当てはめて考えてね。

\(n\) 個の異なるものから \(r\) 個取り出す組み合わせの数を、\({}_n C_r\) 個とする。

取り出した \(r\) 個の順列の数は \(r!\) 個。

従って、\(n\) 個から \(r\) 個の順列の総数は、\({}_n C_r \times r!\) 個。

一方、「順列」から順列 \({}_n P_r\) は次のように書ける。

\[ {}_n P_r = \frac{n!}{(n-r)!} \]

これが \({}_n C_r \times r!\) 個に等しいので、

\[ \begin{aligned} {}_n C_r \times r! &=\frac{n!}{(n-r)!}\\ \therefore \quad {}_n C_r &= \frac{n!}{r!(n-r)!} \end{aligned} \]

5 個のアルファベット A, B, C, D, E から 3 個取り出すときの組み合わせは何通りあるか？

上で具体例として説明した内容と同じですね。

\(5\) 個の異なるものから 3 個取り出す組み合わせは \({}_5 C_3\) 通り。すなわち、

\[ \begin{aligned} {}_5 C_3 &= \frac{5 \cdot 4 \cdot 3}{3 \cdot 2 \cdot 1} \\ &= 10 \end{aligned} \]

よって 10 通り。

1 から 100 までの数字がひとつずつ書かれた 100 個のボールがあります。この中から 98 個取り出す取り出し方は何通りあるか？

\(100\) 個の異なるものから 98 個取り出す組み合わせは \({}_{100} C_{98}\) 通り。すなわち、

\[ \begin{aligned} {}_{100} C_{98} &= \frac{100 \cdot 99 \cdot \cancel{98 \cdot 97 \cdot 96 \cdots 4 \cdot 3}}{\cancel{98 \cdot 97 \cdot 96 \cdots 4 \cdot 3} \cdot 2 \cdot 1} \\ &= \frac{100 \cdot 99}{2 \cdot 1} \\ &= 4950 \end{aligned} \]

と計算しても答えは出ることはでますが、100 個から 98 個を選ぶコンビネーションの数は、選ばない 2 個のコンビネーションの数と同じなので、 \({}_{100} C_{98} = {}_{100} C_{100 - 98} = {}_{100} C_{2}\) と直してから、

\[ \begin{aligned} {}_{100} C_{98} &= {}_{100} C_{2} \\ &= \frac{100 \cdot 99}{2 \cdot 1}\\ &= 4950 \end{aligned} \]

とした方が間違いは少なそうです。

この問題でみたように、\(n\) 個から \(r\) 個選ぶコンビネーションの数は、選ばない \(n-r\) 個を選ぶコンビネーションの個数と同じです。

\[ {}_n C_r = {}_n C_{n-r} \]

選ばれない方が少ない時には、これを使って式を直すと計算が楽になることがあります。