二項係数に関する等式の組み合わせ論的解釈
注意
もしかしたらこの内容は既出かもしれません。一応私が独自に発見したものなので記事にしました。
数学的な注意
$ n < k $のとき、$ \binom{n}{k} = 0 $と定義します。
導入
次の等式を考えます:
$$ \sum_{k:\text{even}} \binom{n}{k} = 2^{n-1} \ (n \geq 1) $$
この等式は、次のようにして証明されることが多いです:
$$ (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} $$
$$ (1+(-1))^n = \sum_{k=0}^{n} (-1)^k\binom{n}{k} $$
これらを足し合わせて
$$ 2^n = \sum_{k:\text{even}} 2\binom{n}{k} $$
両辺を$ 2 $で割ることで元の式が得られる。
この等式を組み合わせ論的にも証明できることを発見したので紹介します。
証明
まず$ (n - 1) \times 1 $のマス目を用意し、それぞれに$ \circ $または$ \times $を書き込む。このとき、それぞれの書き込み方に対する「連続する$ \times $のグループの個数」を$ P $で表すことにする。
![!FORMULA[12][-893864407][0]のときの例](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2FTPXCYlTlz0LjouvkgdZw.png?alt=media)
$ n = 6 $のときの例
このとき、$ P = k $であるような書き込み方の総数は、次のようにして求められる:
マス目の間と両側の$ n $本の縦線の中から「$ k $個の$ \times $のグループの開始位置と終了位置」を指定すればよい。開始位置と終了位置は必ず交互に現れ、最初の開始位置より左に終了位置が来ることはないので、これは相異なる$ 2k $本の縦線を選ぶことと同等である。したがってそのような書き込み方の総数は$ \binom{n}{2k} $通りである。
ただし、$ 2k > n $のときは$ \binom{n}{2k} = 0 $とする。
どのような書き込み方に対しても$ P $が必ず一意に定まるので、$ P = k $であるような書き込み方の総数を$ P_{n-1}(k) $と書くことにすると、次の等式が成り立つ:
$$ \sum_{k=0}^{\infty} P_{n-1}(k) = 2^{n - 1} $$
$ P_{n-1}(k) = \binom{n}{2k} $であるから、$ 2k $を改めて$ k $と書き直すと、与式が得られる:
$$ \sum_{k:\text{even}} \binom{n}{k} = 2^{n-1} $$
