【標準】組合せ

ここでは、【基本】組合せで見た内容を振り返ったあとで、組合せの性質について見ていきます。

【広告】
※ お知らせ: 15秒で三平方の定理を示す、という動画を公開しました。

「組合せ」の復習

例題1
A, B, C, D, E の5人から3人の代表者を選ぶ。代表者の選び方は何通りあるか。

5人から3人を選ぶ方法の総数は、 ${}_5 \mathrm{ C }_3$ で表すのでしたね。これは次のように計算します。\[ {}_5 \mathrm{ C }_3 = \frac{5\cdot 4 \cdot 3}{3\cdot 2\cdot 1}=10 \]これから、10通りが答えとなります。

分子は ${}_5 \mathrm{ P }_3$ と同じで、分母は $3!$ と同じです。これは、5人から3人を選んで一列に並べる方法が ${}_5 \mathrm{ P }_3$ 通りあり、同じ選び方になっているものをそれぞれ $3!$ 回ダブって数えているので割った、という考え方で求めています。

これが、【基本】組合せで見た内容です。

階乗との関係

【標準】順列で見たように、\[ {}_n \mathrm{ P }_r = \frac{n!}{(n-r)!} \]が成り立ちます。これを $r!$ で割ったものが ${}_n \mathrm{ C }_r$ なので、 ${}_n \mathrm{ C }_r$ を階乗だけで書くと、次のようになります。

${}_n \mathrm{ C }_r$ と階乗の関係
$0\leqq r \leqq n$ のとき、次が成り立つ。\[ {}_n \mathrm{ C }_r = \frac{n!}{r! (n-r)!} \]

なお、$r=0$ のときは「0個を選ぶ方法」となって少し不自然な状況になりますが、上の式から\[ {}_n \mathrm{ C }_0=1 \]が導かれます(【標準】順列で $0!=1$ としていました)。

残す方法

上の例題と似ていますが、次の問題を考えてみましょう。

例題2
A, B, C, D, E の5人から3人の代表者を選ぶ。代表者にならない者の選び方は何通りあるか。

5人から「代表者にならない2人」を選ぶため、先ほどと同じように考えると、 ${}_5 \mathrm{ C }_2$ 通りとなることがわかりますね。これを計算すると\[ {}_5 \mathrm{ C }_2 = \frac{5\cdot 4}{2\cdot 1}=10 \]通り、となります。例題1と同じ答えですね。

これは、たまたま同じになったわけではありません。代表者3人を選ぶということは、見方を変えれば、代表者にならない2人を選ぶのと同じです。例えば、「A, B, C を代表者にする」ということは、「D, E を代表者にしない」ことと同じです。なので、「5人から3人を選ぶ方法」の総数と「5人から2人を残す方法」の総数は一致します。

これは一般化できます。 n 個の異なるものから、 r 個を選ぶということは、どの $n-r$ 個を残すか、ということと対応します。よって、次のことが成り立ちます。

${}_n \mathrm{ C }_r$ の性質
$0\leqq r \leqq n$ のとき、次が成り立つ。
\[ {}_n \mathrm{ C }_r = {}_n \mathrm{ C }_{n-r} \]

この内容は、数式で確認することもできます。

階乗を使って表すと、左辺は\[ {}_n \mathrm{ C }_r = \frac{n!}{r!(n-r)!} \]となります。また、右辺は
\begin{eqnarray}
{}_n \mathrm{ C }_{n-r}
&=&
\frac{n!}{(n-r)! \{n-(n-r)\}!} \\[5pt] &=&
\frac{n!}{(n-r)! r!} \\[5pt] \end{eqnarray}となります。一致していますね。 ${}_n \mathrm{ C }_r$ と ${}_n \mathrm{ C }_{n-r}$ が何を表しているかを考えることによって等しいことがわかるし、計算によって等しいこともわかります。

例えば、「9個の異なるものから、7個を選ぶ方法の総数を求めなさい」と言われた場合、 ${}_9 \mathrm{ C }_7$ を直接計算しなくても、上の性質を使えば次のように計算することができます。\[ {}_9 \mathrm{ C }_7 = {}_9 \mathrm{ C }_2 =\frac{9\cdot 8}{2\cdot 1}=36 \]直接計算するより楽ですね(直接計算しても、約分して上の形になります)。

おわりに

ここでは、組合せの復習、組合せと階乗との関係、そして、「残す方法」が「選ぶ方法」に対応していることを見ました。ここで見た式変形は、今後も組合せを考えるときに出てくるので、覚えておきましょう。