組合せ(二項係数)の公式を直接求める
Copyright (C) virtual_high_school, 2018

§0. はじめに

組合せ(二項係数)の公式とはもちろん
　　　$_{n}C_{r} =\frac{n!}{r! (n-r)!}$
である。数学�Uの展開式の係数（パスカルの三角形）で出てくるので、この公式を覚えなくてはいけない。

どうやって証明するかというと、数学Ａにおいては、順列で順序を無視(順序を変えただけのものは同一視)すればよいから
　　　$_{n}C_{r} =\frac{_{n}P_{r}}{r!} = \frac{n!}{r! (n-r)!}$
である---というやり方が多い。

もし生徒が数学Ａを既習であるなら、この公式を思い出せればよい。しかし、カリキュラム上、数学Ａを1年次に習っていないとか、数学Ａは3年次に初めて習うという学校においては組合せの公式を直接（順列を使わずに）導き出さなくてはならない。

その方法を以下に示そう。

§1. 漸化式を作る

$_{n}C_{r}$の値が既知として、それを使って$_{n}C_{r+1}$を表わしてみよう。

(1) でもいきなり文字では難しいので、ウォーミングアップとして、$_{4}C_{2}$から$_{4}C_{3}$を出してみよう。
　　　　　
前者は$(1,2), \cdots$のような組合せである。順序無視だから、取り出した要素は番号順に並べておこう。
ここから、$_{4}C_{3}$に属する組合せを作るには、まだ取り出していない要素(2個ある)から１つ取ってくればよいから、図中左側の組合せから2倍の種類の組合せ(図中右側)が生まれる。生まれる様子を矢印で示した。これで矢印は、
　　　$_{4}C_{2} \times (4-2) =12$(本)
できる。
矢印の終点の側に注目する。例えば$(1,2,3)$という組合せには要素が3個あって、そのうちの任意の1個が最後に付け足された要素だから、3本の矢印が入ってくる。図では3重丸としてそれを表わした。図中右側はすべて3重丸だから、これをダブって勘定すれば$_{4}C_{3} \times 3$となる。これが矢印の総数に等しいから
　　　$_{4}C_{3} \times 3=_{4}C_{2} \times (4-2)$
よって
　　　$_{4}C_{3}=\frac{_{4}C_{2} \times (4-2)}{3}$
で$12/3=4$と正解にたどり着く。

(2) $_{n}C_{r}$から$_{n}C_{r+1}$を出してみよう。　　　　　
前者は$(1,2,\cdots,r), \cdots$のような組合せである。順序無視だから、取り出した要素は番号順に並べておこう。
ここから、$_{n}C_{r+1}$に属する組合せを作るには、まだ取り出していない要素($n-r$個ある)から１つ取ってくればよいから、$_{n}C_{r}$通りの組合せから$n-r$倍の種類の組合せが生まれる。生まれる様子を矢印で示せば矢印は、
　　　$_{n}C_{r} \times (n-r) $(本)
できる。
矢印の終点の側に注目する。例えば$(1,2,\cdots,r+1)$という組合せには要素が$r+1$個あって、そのうちの任意の1個が最後に付け足された要素だから、$r+1$本の矢印が入ってくる。それを$r+1$重丸として表わすこともできる。このようにダブって勘定すれば$_{n}C_{r+1} \times (r+1)$となる。これが矢印の総数に等しいから
　　　$_{n}C_{r+1} \times (r+1)=_{n}C_{r} \times (n-r)$
よって
　　　$_{n}C_{r+1}=\frac{_{n}C_{r} \times (n-r)}{r+1}$
という漸化式が出てくる。

§2. 漸化式を適用する

(1) $_{n}C_{0}$は$n$個から$0$個取り出す方法の数だが、これを定義しないという考えもあろうが、ふつうは「何もしない」という方法が1つだけあるとして、
　　　$_{n}C_{0}=1$

(2) $n$個から$1$個だけ取り出す方法は、$n$通りあるというのは自明だろう。
　　　$_{n}C_{1}=n$

(3) $n$個から$2$個取り出す方法は、漸化式により
　　　$_{n}C_{2}=_{n}C_{1} \times \frac{n-1}{1+1}= \frac{n(n-1)}{2}$

(4) $n$個から$3$個取り出す方法なら
　　　$_{n}C_{3}=_{n}C_{2} \times \frac{n-2}{2+1}= \frac{n(n-1)(n-2)}{3 \cdot 2 \cdot 1}$

(5) あとは類推で
　　　$_{n}C_{r}= \frac{n(n-1)(n-2) \cdots (n-r+1)}{r \dots 3 \cdot 2 \cdot 1}$
階乗の記号を使えば
　　　$_{n}C_{r}= \frac{n!}{r! (n-r)!}$

§3. 証明する

類推で終わりにしたらマズイので、数学的帰納法で$_{n}C_{r}= \frac{n!}{r! (n-r)!}$を証明しよう。$r$の小さい方からたどっていけば、漸化式によりすべて値は確定するから、公式は一意に決まる。だから、あとは類推で出した公式が漸化式を満たしさえすればよい。

(1) $r=0$ のとき
　　　$_{n}C_{0}= \frac{n!}{0! n!}=1$
でOK。

(2) $r=1$ のとき
　　　$_{n}C_{1}= \frac{n!}{1! (n-1)!}=n$
でOK。

(3) $r$のとき公式が成り立つとする。すなわち
　　　$_{n}C_{r}= \frac{n!}{r! (n-r)!}$
ならば
　　　$_{n}C_{r+1}= _{n}C_{r} \times \frac{n-r}{r+1}= \frac{n!}{r! (n-r)!} \times \frac{n-r}{r+1}=\frac{n!}{(r+1)! (n-r-1)!}$
でやはりＯＫ。

(4) 漸化式の成り立つ$r$の変域を明示しておこう。
　　　$_{n}C_{r+1}=_{n}C_{r} \times \frac{n-r}{r+1}$
は、$r=0$および、$1 \leq r \leq n-1$において成り立つ。