[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる 探したい言葉はここへ→
組合せ(二項係数)の公式を直接求める
Copyright (C) virtual_high_school, 2018
§0. はじめに
組合せ(二項係数)の公式とはもちろん
$_{n}C_{r} =\frac{n!}{r! (n-r)!}$
である。数学Uの展開式の係数(パスカルの三角形)で出てくるので、この公式を覚えなくてはいけない。
どうやって証明するかというと、数学Aにおいては、順列で順序を無視(順序を変えただけのものは同一視)すればよいから
$_{n}C_{r} =\frac{_{n}P_{r}}{r!} = \frac{n!}{r! (n-r)!}$
である---というやり方が多い。
もし生徒が数学Aを既習であるなら、この公式を思い出せればよい。しかし、カリキュラム上、数学Aを1年次に習っていないとか、数学Aは3年次に初めて習うという学校においては組合せの公式を直接(順列を使わずに)導き出さなくてはならない。
その方法を以下に示そう。
§1. 漸化式を作る
$_{n}C_{r}$の値が既知として、それを使って$_{n}C_{r+1}$を表わしてみよう。
(1) でもいきなり文字では難しいので、ウォーミングアップとして、$_{4}C_{2}$から$_{4}C_{3}$を出してみよう。
前者は$(1,2), \cdots$のような組合せである。順序無視だから、取り出した要素は番号順に並べておこう。
ここから、$_{4}C_{3}$に属する組合せを作るには、まだ取り出していない要素(2個ある)から1つ取ってくればよいから、図中左側の組合せから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$個ある)から1つ取ってくればよいから、$_{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)!}$
でやはりOK。
(4) 漸化式の成り立つ$r$の変域を明示しておこう。
$_{n}C_{r+1}=_{n}C_{r} \times \frac{n-r}{r+1}$
は、$r=0$および、$1 \leq r \leq n-1$において成り立つ。
[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる 探したい言葉はここへ→