DEGwer氏による「数え上げPDF」、競プロer の間では知らない者はないほど有名…
しかし、対象読者層が青上位〜赤下位と非常に高度な内容です。緑コーダーの私にとっては、正直言って行間が多すぎます。
…行間があるなら、埋めればいいじゃない？
ということで、数え上げPDFの中でも特に有名な、 「(p.30) 二項係数のテクニック 14.1 頻出公式集」 に書かれている 6 つの公式 について、解釈と導出を考えてみたいと思います。
とりあえず全体像
まずは数え上げPDFの公式を眺めましょう。
頻出公式？（原文まま）
\(\sum_{i=0}^n \binom ni = 2^n\)
\(\sum_{i=0}^{\left\lfloor \frac n2 \right\rfloor} \binom n{2i} = 2^{n-1}\)
\(\sum_{i=0}^k \binom{n +i}i = \binom{n +i+1}i\)
\(\sum_{i=0}^k \sum_{j=0}^l \binom{i+j}i = \binom{k+l+2}{k+1}\)
\(\sum_{i=0}^k \binom ni \binom m{k-i} = \binom{n+m}k\)
\(\sum_{i=0}^k \binom{n +i}i \binom{m-i}{k-i} = \binom{n+m+1}k\)
前情報として、この中には「誤植があるかもしれない」と言われています。 （※上記は原文ままなので、信用しないように）
正直なところ、上記の式がどういうことを示しているのか、緑コーダーの私には全くイメージが湧きません。
第 1 回では、これらの公式が本当に成り立つのか確認するところから、ゆっくり見ていくことにしましょう。
公式成立の確認
公式 1
公式 1 \[\displaystyle\sum_{i=0}^N \binom Ni = 2^N\]
では 1 つ目から見ていきます。
（数式中の文字は、プログラマが（私が）見やすいように多少改変しています。）
ここで使う図がこちら。
出ました。パスカルの三角形。
これは分かりやすくて、この図でいう \(N\) 行目の合計が \(2^N\) になっています。
どの \(N\) をとっても、そうなっていますね。
これを応用すると、\(N\) 行目より上の三角形全体の合計も分かりますね。
そうですね。 \[\sum_{i=0}^N \sum_{j=0}^i \binom ij = 2^{N+1} -1\] で求まります。
公式 2
公式 2 \[\sum_{i=0}^{\left\lfloor N/2 \right\rfloor} \binom N{2i} = 2^{N-1} \qquad (N\ge 1)\]
まだ穏便です。
\(N\) 行目の偶数番目の数を拾ってきて合計すると、 \(2^{N-1}\) となります。
えっ、待って、なんでですか？
こんなバラバラの数を 1 つおきに足したら、1 行分のちょうど半分になるんですか？
この時点で、かなり非直感的な気がします。
あと、奇数番目を足したものも \(2^{N-1}\) で等しくなりますね。
何故そうなるかは全く分かりません… が、そうなっています。
あっ、でも \(N=0\) では成り立たないようです。
証明とかは次回に回すとして、次に進みましょう。
公式 3
公式 3 \[\sum_{i=0}^K \binom{N +i}i = \binom{N+K+1}K\]
一気に雲行きが怪しくなりました。
しかも、オリジナルの数式には誤植がありますね。
（右辺に \(i\) が出てくるのは、明らかに変です。）
\(N\) 行目の左端からスタートして、\((K+1)\) 個だけ斜めに足していく訳ですね。
これは、ホッケースティック恒等式というそうです。
さらに、 \(\binom {A+B}A = \binom {A+B}B\) であることを用いると、次のように変形できます。 \[\sum_{i=0}^K \binom{N +i}N = \binom{N+K+1}{N+1}\]
実用上は、こちらの方が便利そうな雰囲気がありますね。（本当に？）
公式 4
この式、またしても誤植でした！！！
（→その 指摘の様子 ）
正しいものは下記となります。
公式 4 \[\sum_ {i=0}^K \sum_{j=0}^L \binom{i+j}i = \binom{K+L+2}{K+1} - 1\]
最後に \(-1\) が必要となります。
図で見ると、公式 3 との関係が分かりやすいですね。
公式 5
公式 5 \[\sum_{i=0}^K \binom Ni \binom M{K-i} = \binom{N+M}K\]
ここからは積和が絡んできます。
\(N\) 行目と \(M\) 行目の要素を逆順にかけて、その合計をとりましょう。
答えが \((N+M)\) 行目に出てきました。
ここで、ちょっと意地悪して「\(K\) が大きいとき」も見てみます。
成り立ちました。マジかよ… 超強力じゃん…
公式 6
公式 6 \[\begin{split} \sum_{i=0}^K \binom{N +i}i \binom{M-i}{K-i} &= \binom{N+M+1}K \cr &\qquad\qquad (M\ge K) \end{split}\]
今度は斜めバージョンです。
ここで \(M=K\) とすると、公式 3 が出てきます。
また、\(M\lt K\) では図の外にはみ出るので、困ってしまいます。
また、これも線対称で変形できて、
\[\sum_{i=0}^K \binom{N +i}N \binom{M-i}{M-K} = \binom{N+M+1}{N+M-K+1}\]
こういう見方もできますね。（右辺は、\(\binom{N+M+1}K\) でいいですよ？）
でもこれ、どういう場面で使うのでしょうか。
結論
数え上げ頻出公式について、ちゃんと成り立つ（？）ことをビジュアルに確認しました。
と同時に、誤植を修正してまとめ直すと次のようになります。
頻出公式（修正版）
\(\displaystyle\sum_{i=0}^N \binom Ni = 2^N\)
\(\displaystyle\sum_{i=0}^{\left\lfloor N/2 \right\rfloor} \binom N{2i} = 2^{N-1} \quad\) \((N\ge 1)\)
\(\displaystyle\sum_{i=0}^K \binom{N +i}i = \binom{N+K+1}K\)
\(\displaystyle\sum_ {i=0}^K \sum_{j=0}^L \binom{i+j}i = \binom{K+L+2}{K+1} - 1\)
\(\displaystyle\sum_{i=0}^K \binom Ni \binom M{K-i} = \binom{N+M}K\)
\(\displaystyle\sum_{i=0}^K \binom{N +i}i \binom{M-i}{K-i} = \binom{N+M+1}K \quad\) \((M\ge K)\)
※特に断りがない場合、変数は非負整数です。
これで、だいぶ読みやすくなりました。
次回以降、いよいよ導出にチャレンジしていきたいと思います。
