順列と組合せを理解してみる－組合せ

はじめに

前回、順列を説明しました。今回は組合せとなります。 yaju3d.hatenablog.jp

順列と組合せの違いですが、順列の場合は「順番をつける」、組合せの場合は「順番をつけない」となります。

組合せ

組合せには下記の公式があります。Cはcombination(コンビネーション)の頭文字です。
公式： $\displaystyle _n C _r = \frac{_n P _r}{r!}$

問題と解説

A、B、C、D、Eの5人から3人を選ぶ

理解するために公式を使わずに問題を解いてみましょう。
3人を選ぶというのは、選ばれた組（3人）と選ばれない組（2人）に分けるということです。
まず、選ばれた組に1人目、2人目、3人目という「席」があると考えて順列と同様に考えます。
$_5 P _3 = 5 \times 4 \times 3 = 60$ 通りとなります。

ところが、これでは「1人目、2人目、3人目」が「A、B、C」のときと「A、C、B」のときは、組としては同じなのに重複して数えられています。
f:id:Yaju3D:20160717113527p:plain

同じ3人が選ばれたときの並び方 $3! = 6$ 通り分が重複しています。
これが「B、C、D」…「C、D、E」など他の組合せでも同様となるため、元の式を $3!$ で割ってしまえばいいです。

$\displaystyle \frac{_5 P _3}{3!} = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10$ 通りとなります。

計算式を一般化

先程の計算式を一般化してみます。

$\displaystyle \frac{_5 P _3}{3!} = \frac{1}{3!} \times \frac{5!}{2!}$ （← $\displaystyle _n P _r = \frac{n!}{(n - r)!}$ より）
$\displaystyle = \frac{5!}{3! \times (5 - 3)!}$

よって、組合せは次の方法で計算できます。
$\displaystyle = \frac{n!}{r!(n-r)!}$
最初の式に戻すと公式と同じになります。
$\displaystyle = \frac{_n P _r}{r!}$

問題と解説

10人の人間から7人の代表を選ぶとき、選び方の場合の数を求めよ。

公式を使ってみます。
$\displaystyle _{10} C _7 = \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4}{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$ 通りとなります。

これくらいならまだしも、例えば、 $_{100} C _{98}$ だと計算が大変になります。
コンビネーションにはこれを簡単にできる性質があります。
$\displaystyle _n C _r = _n C _{(n-r)}$
先程の計算を当てはめてみます。
$\displaystyle _{10} C _7 = _{10} C _{(10-7)} = _{10} C _3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$ 通りで同じとなります。