【標準】組合せ

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

【広告】

「組合せ」の復習

例題1
大野、櫻井、相葉、二宮、松本の5人から3人を選んで新ユニットを作る。新ユニットに入る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
大野、櫻井、相葉、二宮、松本の5人から3人を選んで新ユニットを作る。新ユニットに入らない2人の選び方は何通りあるか。

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

これは、たまたま同じになったわけではありません。新ユニットを作るために「新ユニットに入る3人を選ぶ」ということは、見方を変えれば「新ユニットに入らない2人を選ぶこと」と同じです。例えば、「新ユニットに、大野、相葉、松本の3人を入れる」ということは、「新ユニットに、櫻井、二宮の2人を入れない」ことと同じです。なので、「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 \]直接計算するより楽ですね(直接計算しても、約分して上の形になります)。

おわりに

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