ホーム >> 場合の数 >> 二項係数のいろいろな公式

二項係数について成り立ついろいろな公式について,その意味合いとともに紹介します.




二項係数のいろいろな公式

二項係数 ${}_n \mathrm{C} _k$ とは,$n$ 個のものの中から,$k$ 個のものを順序を考慮せず選ぶ選び方の総数です.ここで,自然数 $k$ の範囲は $0 \le k \le n$ で,$k=0$ のときは,${}_n \mathrm{C} _0=1$ と定めます.

代数的には, $${}_n \mathrm{C} _k=\frac{n!}{k!(n-k)!}$$ とかけます.さて,二項係数について,以下の $3$ つの等式が有名です.

$$(1)\ \ {}_n \mathrm{C} _k={}_n \mathrm{C} _{n-k}$$ $$(2)\ \ {}_{n} \mathrm{C} _{k} ={}_{n-1} \mathrm{C} _{k-1} +{}_{n-1} \mathrm{C} _{k}$$ $$(3)\ \ k{}_n \mathrm{C} _k=n{}_{n-1} \mathrm{C} _{k-1} $$

公式の代数的な証明

公式の証明は,${}_n \mathrm{C} _k=\frac{n!}{k!(n-k)!}$ と,階乗の簡単な性質を使うだけで示すことができます.

証明:
$$(1)\ \ {}_n \mathrm{C} _k=\frac{n!}{k!(n-k)!}=\frac{n!}{(n-k)!\{n-(n-k)\}!}={}_n \mathrm{C} _{n-k}$$
$$(2)\ \ {}_{n-1} \mathrm{C} _{k-1} +{}_{n-1} \mathrm{C} _{k}$$ $$=\frac{(n-1)!}{(k-1)!\{(n-1)-(k-1)\}!}+\frac{(n-1)!}{k!\{(n-1)-k\}!}$$ $$=\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}$$ $$=\frac{k(n-1)!+(n-k)(n-1)!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}={}_{n} \mathrm{C} _{k} $$
$$(3)\ \ k{}_n \mathrm{C} _k=\frac{k(n!)}{k!(n-k)!}$$ $$=\frac{n!}{(k-1)!(n-k)!}=\frac{n(n-1)!}{(k-1)!\{(n-1)-(k-1)\}!}=n{}_{n-1} \mathrm{C} _{k-1}$$


($2$) を示すときは,(左辺) から (右辺) は示しにくいので,(右辺) から出発して,(左辺) になることを示しました. いずれも,何を示せばよいのかを考えながら式変形していけば自然と導けます.

さて,これらの公式を覚えるべきかどうかは人によるでしょうが,なんだがややこしくて,覚えにくいですよね.公式をそのまま丸暗記してもよいですが,($2$),($3$) などはそこまで使う頻度も多くないので,忘れてしまう危険性は高いです.

そこで,筆者のオススメは以下の組合せ論的な解釈を覚える方法です.等式をただ覚えるより,組み合わせ論的な意味合いを知っていた方が圧倒的に忘れにくいです.

公式の組み合わせ論的な意味

($1$) $n$ 人から,$k$ 人を順序を考慮せず選ぶ組み合わせの数 (${}_n \mathrm{C} _k$)は,$n$ 人から,選ばれなかった $n-k$ 人の組み合わせの数 (${}_n \mathrm{C} _{n-k}$) に等しい.

$n$ 人から $k$ 人を選ぶと,$n-k$ 人の人が選ばれなかった事になります.つまり,$n$ 人から $k$ 人選ぶごとに,選ばれなかった $n-k$ 人を選んでいるともいえます.これが,${}_n \mathrm{C} _k={}_n \mathrm{C} _{n-k}$ の組合せ論的な解釈です.

($2$) 特別な人 $1$ 人を含む $n$ 人から,$k$ 人を順序を考慮せず選ぶ組み合わせの数 (${}_n \mathrm{C} _k$)は,特別な人を先に選び,残りの $n-1$ 人から $k-1$ 人を選ぶ組合わせの数 (${}_{n-1} \mathrm{C} _{k-1} $) と,特別な人を選ばずに,残りの $n-1$ 人から $k$ 人を選ぶ組み合わせの数 (${}_{n-1} \mathrm{C} _{k}$) に等しい.

$n$ 人から $k$ 人を選ぶことを考えてみてください.ただし,$n$ 人の中にはひとりだけ特別な人がいます (たとえば,あなたの好きな人とか).このとき,$n$ 人から $k$ 人を選ぶ組み合わせの数は,その特別な人を選ぶものと,選ばないものの $2$ つに分けられます.これが,${}_{n} \mathrm{C} _{k} ={}_{n-1} \mathrm{C} _{k-1} +{}_{n-1} \mathrm{C} _{k}$ の組合せ論的な解釈です.

($3$) $n$ 人から代表一人を含む $k$ 人を選ぶ際,$n$ 人から $k$ 人を選んだ後,その中から代表者を一人選ぶ組み合わせの数 ($k{}_n \mathrm{C} _k$) は,$n$ 人から先に一人代表者を選び,それ以外の $n-1$ 人から残りの $k-1$ 人を選ぶ組み合わせの数 ($n{}_{n-1} \mathrm{C} _{k-1}$) に等しい.

$n$ 人から代表者一人を含む $k$ 人を選ぶ方法は,代表者を先に選ぶか,グループを先に選ぶかの順序の違いで,$2$ 通りあります.これが,$k{}_n \mathrm{C} _k=n{}_{n-1} \mathrm{C} _{k-1}$ の組合せ論的な解釈です.


代数的な等式に組み合わせ論的な解釈ができるのは面白いことですよね.