2014/02/23

二項係数の有名公式を2つの方法で導く

分野: 場合の数  レベル: 最難関大学

二項係数の有名公式を3つほど紹介し,それぞれ代数的な方法と組み合わせ的な方法で導きます。
特に3つ目の公式は整数問題にも応用することができる重要な公式です。

なお,二項定理の基本的な話題については二項定理の意味と2通りの証明を参照して下さい。

二項係数の有名公式

パスカルの三角形

(i) ${}_n\mathrm{C}_r$ =${}_n\mathrm{C}_{n-r}$
(ii) ${}_n\mathrm{C}_r$ =${}_{n-1}\mathrm{C}_r$ +${}_{n-1}\mathrm{C}_{r-1}$
(iii)  $r{}_n\mathrm{C}_r$ = $n{}_{n-1}\mathrm{C}_{r-1}$

公式(i), (ii)は多くの人が知っている公式だと思います。公式(i)はパスカルの三角形が左右対称であることを,公式(ii)はパスカルの三角形において「上の2つの数字を足したら下の数字になる」という事実を表しています。

公式(iii)も便利な公式なのでこの際覚えてしまいましょう。例えば,公式(iii)から以下のような事実が分かります:
「 $n$ が素数で $1\leq r\leq n-1$ のとき${}_n\mathrm{C}_r$ は $n$ の倍数となる」
この事実は,難関大学の受験問題や数学オリンピックに出題される整数問題を解く際に役に立つことがあるので頭の片隅にとどめておくとよいでしょう。

二項係数の有名公式の代数的な証明

二項係数の関係式は代数的に証明することができます。
つまり,${}_n\mathrm{C}_r=\dfrac{n!}{r!(n-r)!}$ という二項係数の定義式を用いて公式の左辺と右辺が等しいことを示します。公式の組み合わせ的な意味を忘れて機械的に計算していきます。

(i)の証明:
${}_n\mathrm{C}_r=\dfrac{n!}{r!(n-r)!}=\dfrac{n!}{(n-r)!\{n-(n-r)\}!}={}_n\mathrm{C}_{n-r}$

(ii)の証明(右辺を変形していく):
$\begin{align*}{}_{n-1}\mathrm{C}_r+{}_{n-1}\mathrm{C}_{r-1}&=\dfrac{(n-1)!}{r!(n-1-r)!}+\dfrac{(n-1)!}{(r-1)!(n-r)!}\\
&=\dfrac{(n-1)!}{(r-1)!(n-1-r)!}(\dfrac{1}{r}+\dfrac{1}{n-r})\\
&=\dfrac{n!}{r!(n-r)!}\\
&={}_n\mathrm{C}_r\end{align*}$

(iii)の証明:
$\begin{align*}r{}_{n}\mathrm{C}_r&=r\dfrac{n!}{r!(n-r)!}\\
&=n\dfrac{(n-1)!}{(r-1)!(n-r)!}\\
&=n{}_{n-1}\mathrm{C}_{r-1}\end{align*}$

これくらいの単純な公式なら機械的に証明することができますが,より複雑な二項係数の公式が出現してきたら複雑な計算をすることになり,気合いが必要になります。(例:ヴァンデルモンドの畳み込み公式の証明)もちろん時間と気合いがある場合は複雑な場合も代数的な方法を使えば良いです!

二項係数の有名公式の組み合わせ的な証明

つぎに,上記の公式を組み合わせ的に証明します。
組み合わせ的な考え方は代数的な方法と異なりひらめきが必要になりますが,代数的な方法より美しい場合が多く,気合いも必要ないです。

(i)の証明:
$n$ 個のものから $r$ 個のものを選ぶ組み合わせの数は,$n-r$ 個の「選ばないものを選ぶ」組み合わせの数に等しい。

(ii)の証明:
(特定のものAを含む)$n$ 個のものから $r$ 個のものを選ぶ組み合わせの数は
「Aを選ばず残り $n-1$ 個の中から $r$ 個のものを選ぶ組み合わせの数」
+「Aを選び残り $n-1$ 個の中から $r-1$ 個のものを選ぶ組み合わせの数」
に等しい。

(iii)の証明:
$n$ 人から $r$ 人採り,1人をリーダーにする組み合わせの数を2通りの方法で考える。
「 $n$ 人の中から $r$ 人選んでそのグループのリーダーを選ぶ組み合わせの数」
=「 $n$ 人の中から1人リーダーを選んで残り $n-1$ 人から $r-1$ 人選ぶ組み合わせの数」

なお,上記の(i), (iii)の説明をより丁寧に視覚的に説明しているサイトを発見したので,こちらも参考にしてみてください。(東大生が教えるビジュアル数学:組み合わせで用いられる重要な性質

重要なのは,同じ公式を代数的にも組み合わせ的にも捉えることができる,ということです。代数的によくわからなくて覚えづらい公式も組み合わせ的な意味を考えればスッキリすることがあるし,逆もまた然りです。

1つの公式の成り立ちを多面的に理解することで,咄嗟に応用することができる場面が増えます。二項係数の関係式を見たときは代数的な方面,組み合わせ的な方面の双方からアプローチしましょう。


分野: 場合の数  レベル: 最難関大学