【数学IA】組合せの総数の求め方

ここでは「組合せ」について説明します。

いくつかあるものの中からその一部を取り出して組を作ることを考えます。

取り出す組合せのみに着目して，取り出したものを1列に並べるといった順序を考えないとき，その組の総数の求め方について説明します。

Contents

1 組合せの総数
2 $\nCk{n}{n}$ と $\nCk{n}{0}$ について
3 組合せ $\nCk{n}{r}$ を計算する練習
4 組合せ $\nCk{n}{r}$ に関する公式
5 練習問題

組合せの総数

ヒロ

例えば4つの文字A, B, C, Dから2つを選んでつくることができる組を考えよう。

【4文字から2文字を選ぶ組合せ】
具体的に組を書き出すと次のようになる。
(A, B), (A, C), (A, D), (B, C), (B, D), (C, D)
このように漏れなく重複なく書き出すことで6通りあることが分かる。

ヒロ

具体的に書きだすと組合せの総数を求めることはできるが，文字数が多くなるとやってられなくなる。

ヒロ

そこで計算で求めることができるようになると楽ができる。

【4文字から2文字を選ぶ組合せを計算で求める】
4文字から2文字を選んで1列に並べる方法を考える。1文字目の決め方が4通りあり，それに応じて2文字目の決め方が3通りあるから，全部で $4\times3=12$ 通りあることは簡単に分かる。
これを別の考え方をすると，次の手順で4文字から2文字を選んで1列に並べることができる。
　① 4文字から2文字を選ぶ。
　② 2文字を1列に並べる。
①の方法が何通りあるかを知りたいので $x$ 通りとする。②の方法は $2!=2$ 通りであるから，全部で $2x$ 通りあることになる。これが12通りであるから，

\begin{align*}
&2x=12 \\[4pt]
&x=6
\end{align*}

ヒロ

最初に求めた6通りと一致するね。

ヒロ

今回の場合は4つの文字から2つの文字を選ぶ組合せ（combination）だから，$\nCk{4}{2}$ と表す。つまり $\nCk{4}{2}=6$ である。

ヒロ

一般化しておこう。

【組合せ $\nCk{n}{r}$ の一般化】
異なる $n$ 個のものから $r$ 個取って1列に並べる方法は $\nPk{n}{r}$ 通りある。これを2つの手順に分けると次のようになる。
　① 異なる $n$ 個のものから $r$ 個を選ぶ。
　② $r$ 個を1列に並べる。
①の方法は $\nCk{n}{r}$ 通りある。②の方法は $r!$ 通りある。よって，全部で $\nCk{n}{r}\times r!$ 通り。これが $\nPk{n}{r}$ と等しいから

\begin{align*}
&\nCk{n}{r}\times r!=\nPk{n}{r} \\[4pt]
&\nCk{n}{r}=\dfrac{\nPk{n}{r}}{r!}
\end{align*}

ここで $\nPk{n}{r}=n(n-1)(n-2)\cdots(n-r+1)$ であるから，

\begin{align*}
\nCk{n}{r}=\dfrac{\overbrace{n(n-1)(n-2)\cdots(n-r+1)}^{r~個}}{\underbrace{r(r-1)(r-2)\cdots 3\Cdot2\Cdot1}_{r~個}}
\end{align*}

となる。階乗を用いて表すと $\nPk{n}{r}=\dfrac{n!}{(n-r)!}$ であるから，

\begin{align*}
\nCk{n}{r}=\dfrac{n!}{r!(n-r)!}
\end{align*}

となる。