二項係数に関する恒等式の組合せ的な証明

初めに

二項係数に関する恒等式の組合せ的な解き方を紹介します。
$doublecounting$、包除原理 包除原理の解説 、主客転倒を主に使っていきます！
有名な恒等式でも、僕が組合せ的に解くことができなかったり、組合せ的に解けても汚かったり、結局母関数の問題に帰着される方法しか分からなかったものは省いています...
実用性があるかはかなり分かれると思っています。
ただエレガントさ、面白さは絶対にほかの証明方には負けません！
間違いがあると教えてほしいです。
また$r<0,n<r$の時${}_n{\mathrm{C}}_r=0$とします。

Level1

1,${}_n{\mathrm{C}}_r={}_{n-1}{\mathrm{C}}_{r-1}+{}_{n-1}{\mathrm{C}}_r$

$n$個の区別するボールを$r$個選択する組合せについて考える。これは${}_n{\mathrm{C}}_r$通りである。
別の数え方をしてみる
一つのボールに着目してそのボールを選択するとき：残りの$n-1$個から$r-1$個選択すればいいので${}_{n-1}{\mathrm{C}}_{r-1}$通り
そのボールを選択しない時：残りの$n-1$個から$r$個選択すればいいので、${}_{n-1}{\mathrm{C}}_r$通り
よって${}_n{\mathrm{C}}_r={}_{n-1}{\mathrm{C}}_{r-1}+{}_{n-1}{\mathrm{C}}_r$

2,${\displaystyle \sum _{k=0}^n{m}^k{}_n{\mathrm{C}}_k=(m+1{)}^n}$($m$は自然数）

二項定理より一瞬で示すことができる。
$n$個の区別するボールを非負整数個選択し選択したボールを$m$個の箱に分配する（空の箱があってもよい）組合せについて考える。
選択するボールが$k$個の時、$m^k{}_n{\mathrm{C}}_k$通り。よって求めたい組合せは$k$が0の時から$n$の時まで足し合わせると求められるので、${\displaystyle \sum _{k=0}^n{m}^k{}_n{\mathrm{C}}_k}$通り
別の数えかたをしてみる。
箱を新たに一つ追加してそれを箱$X$と呼ぶことにする。
選択しないボールを箱$X$に入れると言い換えることで、求めたい組合せは$(m+1{)}^n$通りとなる。
mが自然数の時にしか示せないので面白さ以外完全に下位互換である。

3,${\displaystyle \sum _{k=0}^{\lfloor {\displaystyle \frac{n}{2}}\rfloor }{}_n{\mathrm{C}}_{2k}=2^{n-1}}$

区別する$n$個のボールを偶数個選択する組合せについて考える
選択するボールが$2k$個であるとき、組合せは${}_n{\mathrm{C}}_{2k}$通り。そして$k$が$0$の時から$\lfloor {\displaystyle \frac{n}{2}}\rfloor$のときまで足し合わせると求められるので、求めたい組合せは${\displaystyle \sum _{k=0}^{\lfloor {\displaystyle \frac{n}{2}}\rfloor }{}_n{\mathrm{C}}_{2k}}$通り
別の数え方をしてみる。
$n$個のボールのうち一つボールを決めそれをボール$X$とする。
ボール$X$以外の$n-1$個のボールについて考え、そのボールを非負整数個選択する。この組み合わせは$2^{n-1}$通りである。この時、選択したボールが偶数個であるなら、ボール$X$を選択せず、選択したボールが奇数個であるときはボール$X$を選択することで、求めたい組合せを得ることができる。よって$2^{n-1}$通り。

4,$r{}_n{\mathrm{C}}_r=n{}_{n-1}{\mathrm{C}}_{r-1}$

$n$個の区別する白いボールがあり、そのうち$r-1$個を赤色に塗り、$1$ つを青色に塗る組合せについて考える。
$n$個のボールの中から染色するボールを$r$個選び、選んだ$r$個の中から一つ青色に塗るボールを決め、残りの$r-1$個を赤色に塗ると良いので、求めたい組合せは$r{}_n{\mathrm{C}}_r$通り。
別の数え方をしてみる。
先に青色に塗るボールを$n$個の中から選び、残りの$n-1$個のボールの中から赤色に塗るボールを選ぶと良いので、求めたい組合せは$n{}_{n-1}{\mathrm{C}}_{r-1}$通り

Level2

5,${\displaystyle \sum _{k=0}^n{m}^{k}k{}_n{\mathrm{C}}_k=mn(m+1{)}^{n-1}}$

2,4より一瞬で分かる
$n$個の区別する箱があり、すべての箱の中に$m$個の区別できる玉が入っている。
このとき非負整数個の箱を選び、選んだ箱から一つずつボールを選択する組合せは、すべての箱について
{$m$個のうちどの玉を選択するか($m$通り)} or {その箱を選ばない（ボールをとらない）}選択を$n$回することになるので、$(m+1{)}^n$通り。
ここで以下のようなことを考えてみる。

玉の取り出し方$(m+1{)}^n$通りすべてについて選択された玉の数の合計はいくつか？

選択する箱が$k$個の時で場合分けをしてそれを足し合わせることで求めてみる。
選択する箱が$k$個の時
箱の選択の仕方は${}_n{\mathrm{C}}_k$通り。
玉の選択の仕方は$m^k$通り。
よって、選択された玉の数の合計は$m^{k}k{}_n{\mathrm{C}}_k$となる。
したがって求めたい「玉の取り出し方$(m+1{)}^n$通りすべてについて選択された玉の数の合計」は
${\displaystyle \sum _{k=0}^n{m}^{k}k{}_n{\mathrm{C}}_k}$となる。

別の方法で求めてみる。

ここで競技数学でよく使われる主客転倒という手法を使います。
玉はすべてで$mn$個あります。このうち一つの玉に着目してそれを玉$X$とします。
この時、玉$X$が何回カウントされるか数え、それに$mn$を掛けることで、「玉の取り出し方$(m+1{)}^n$通りすべてについて選択された玉の数の合計」求めることができる。

玉$X$が選択された時、残りの$n-1$個の箱すべてについて、$m$個のうちどの玉を選択するか($m$通り) or その箱を選ばない（ボールをとらない）選択をすることになる。したがって玉$X$が選択される組合せは$(m+1{)}^{n-1}$通りとなる。これは玉$X$が選択された玉の合計として$(m+1{)}^{n-1}$回足されることを意味する。

したがって「玉の取り出し方$(m+1{)}^n$通りすべてについて選択された玉の数の合計」は$mn(m+1{)}^{n-1}$となる。

6,${\displaystyle \sum _{k=0}^m{}_{n+k}{\mathrm{C}}_k={}_{n+m+1}{\mathrm{C}}_m}$ $hockeystick$恒等式

$n+1$個の|と$m$個の○を並び変える組合せについて考える。
この並べ替えは${}_{n+m+1}{\mathrm{C}}_m$ 通りである。

別の方法で数えてみる。

一番右側にある|に着目してそれより右側にある○の数で場合分けをして、それを足し合わせることで求めてみる。
一番右側にある|の右に○が$n-k$個あるとき、それより左にある|$n$個と○$k$個を自由に並びかえたらいいので、${}_{n+k}{\mathrm{C}}_k$通りとなる。
したがって求めたい組合せは${\displaystyle \sum _{k=0}^m{}_{n+k}{\mathrm{C}}_k}$通りとなる。

パスカルの三角形を使った証明もかなりエレガントだと思っています。

7,${\displaystyle \sum _{k=0}^r{}_n{\mathrm{C}}_k\times {}_m{\mathrm{C}}_{r-k}={}_{n+m}{\mathrm{C}}_r}$$vandermonde$の畳み込み

神恒等式です これに関しては組合せ的証明のほうがシンプルで分かりやすいと思ってます！

箱$A$に$n$個、箱$B$に$m$個の区別できるボールが入っています。
この中から合計$r$個ボールを選択する組合せについて考える。
箱$A$,$B$からいくつのボールを選択するか場合分けをして、それを足し合わせることで求めてみる。
箱$A$から$k$個、箱$B$から$r-k$個選択する時、${}_n{\mathrm{C}}_k\times {}_m{\mathrm{C}}_{r-k}$通りとなる。
したがって求めたい組合せは
${\displaystyle \sum _{k=0}^r{}_n{\mathrm{C}}_k\times {}_m{\mathrm{C}}_{r-k}}$通りとなる。

別の方法で求めてみる

箱を無視して、全部で$n+m$個ボールがある中から$r$個のボールを選択すればいいので、
求めたい組合せは${}_{n+m}{\mathrm{C}}_r$通りとなる。

Level3

8,${\displaystyle \sum _{k=0}^n(-1{)}^{k+n}{k}^n{}_n{\mathrm{C}}_k=n!}$

$n$個の星があります。
ここで直行便というものを以下のように定義します。
直行便：始点として設定された一つの星から、終点として設定された一つの星を結ぶ一方通行の便。但し、始点と終点を同じ星にすることができる。

この時、以下の条件を満たす直行便の組合せについて数える。
条件：直行便の数は$n$個であり、すべての星は最低一つの始点と終点に設定されている。

この条件を満たす直行便の組合せは、$n$個の星の並び替えに等しいので$n!$通り

別の数え方をしてみる。

条件を以下のように少し変える。
条件：直行便の数は$n$個であり、すべての星は最低一つの始点に設定されているが必ずしも終点に設定されてるとは限らない。

この条件を満たす直行便の組合せは、すべての直行便について$n$個ある星の中から終点を選ぶ。この選択を$n$回するので、$n^n$通りである。

この中から最初に設定した「すべての星は最低一つの終点に設定されている」という条件を満たさないものを引くことで最初の条件を満たす直行便の組合せを求める。

ここで包除原理を使います。星を($H_1,H_2,H_3,...,H_n$)とし、

${\displaystyle \sum }$（星$H_k$が終点として設定されてない組合せ）$-$${\displaystyle \sum }$（星$H_k$と星$H_l$が終点として設定されてない組合せ）
$+$${\displaystyle \sum }$（星$H_k$と星$H_l$と星$H_m$が終点として設定されてない組合せ）$-$${\displaystyle \sum }$...

上記のようにして求めることができる。
したがって、求めたい組合せは、$n^n-{\displaystyle \sum _{k=1}^n(-1{)}^{k+1}(n-k{)}^n{}_n{\mathrm{C}}_k}$=${\displaystyle \sum _{k=0}^n(-1{)}^{k+n}{k}^n{}_n{\mathrm{C}}_k}$

9,${\displaystyle \sum _{k=0}^{\lfloor {\displaystyle \frac{n}{2}}\rfloor }{m}^k{}_{n-k}{\mathrm{C}}_k={\displaystyle \frac{1}{\sqrt{4m+1}}}\{({\displaystyle \frac{1+\sqrt{4m+1}}{2}}{)}^{n+1}-({\displaystyle \frac{1-\sqrt{4m+1}}{2}}{)}^{n+1}\}}$

$n$段の階段を考える。
$A$君はその階段を一歩で$1$段または$2$段進むことができます。但し、$A$君は$m$通りの方法で一歩で$2$段進むことができます。（これからは一歩で$2$段進むことを「1段飛ばし」、一歩で$1$段進むことを「普通」と呼ぶことにする。）
この時、$A$君が$n$段の階段を昇る方法は何通りあるか考える。

一段飛ばしを何回するかで場合分けをしてそれを足し合わせることで求めてみる。
一段飛ばしを$k$回するとき、$A$君は普通と一段飛ばしを合計$n-k$回することになるので、一段飛ばしと普通の並び替えは${}_{n-k}{\mathrm{C}}_k$通り。
一段飛ばしは$m$種類あるので、一段飛ばしを$k$回行うとき$m^k{}_{n-k}{\mathrm{C}}_k$通りとなる。

別の数え方をしてみる。

求めたい組合せを$a_n$とおき漸化式を立てる。$a_1=1,a_2=m+1$
$n+2$段の昇り方は$n+1$段昇ったあと一段進む又は、$n$段昇った後一段飛ばしをすることによって得られるので、
$a_{n+2}=a_{n+1}+m{a}_n$という漸化式が得られる。
この漸化式を解くと$a_n={\displaystyle \frac{1}{\sqrt{4m+1}}}\{({\displaystyle \frac{1+\sqrt{4m+1}}{2}}{)}^{n+1}-({\displaystyle \frac{1-\sqrt{4m+1}}{2}}{)}^{n+1}\}$が得られる。

最後に

8の説明がかなり大変でした...包除原理を説明すること自体かなり難しい...
まだ紹介したいものがありますが、これくらいにしておきます...