前回の続きです。 6 つの公式 について、解釈を考えています。
残り、2 つ。
6 つの公式
数え上げPDF の公式（修正版）です。
前回は、4 つ目まで扱いました。
頻出公式（修正版）
\(\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)\)
もうおなじみですね。
※ \(\displaystyle \binom {N}K = {}_ N {\mathrm C} _ K \)\({}= \displaystyle\frac{N!}{(N - K)!\ K!}\) は、二項係数です。
証明らしきもの
準備：最短経路の数
今回の準備は、グリッド上の最短経路の話です。
まずは基本編。
左下をスタートして、右上のゴールに辿り着く最短経路は、何通りあるでしょうか？
…
……はい。
答えはもちろん、\(\displaystyle \binom {N+M}N = \binom {N+M}M \)\({}= \displaystyle\frac{(N+M)!}{N!\ M!}\) です。
上に進む ↑ が \(N\) 個と、右に進む → が \(M\) 個あります。
ひとつの最短経路は、これらの矢印の同じものを含む順列と見ることができます。
そうなると、「枠」が \((N+M)\) 個並んでいて、その「枠」のうち \(N\) 個を選びとって ↑ を入れる（残った枠は → で埋める）という操作を考えれば、\(\displaystyle \binom {N+M}N \) 通りであることが分かります。
思い出してきましたか？
…
……
では次に、応用編です。
スタートから、途中の点 P を通って、ゴールに到達する最短経路は何通りあるでしょうか？
そのままだと微妙に難しいですが、
「経路は最短である」という制約から、絶対に通らない辺があるので、削除してしまいましょう。
これだと見通しが立ちやすいですね。
という訳で、\(\displaystyle \binom {N_1+M_1}{N_1} \binom {N_2+M_2}{N_2}\) となります。
公式 5
公式 5 \[\sum_{i=0}^K \binom N i \binom M{K -i} = \binom{N+M}K\]
これは、ヴァンデルモンドの恒等式という名前がついているそうですね。
この式についてのみ、数え上げPDFの中でも解釈が示されています。
点 P 、動きます。
いや、これ思いつくの天才か？
いったん落ち着いて、
- 左下の小領域：
- よこ： \(N -i\)
- たて： \(i\)
- 経路数： \(\displaystyle \binom {(N -i) +i}{i} = \binom N i\)
- 右上の小領域：
- よこ： \(M -K +i\)
- たて： \(K -i\)
- 経路数： \(\displaystyle \binom {(M -K +i) +(K - i)}{K -i} = \binom {M}{K -i}\)
- 全体：
- よこ： \(N -K +M\)
- たて： \(K\)
- 経路数： \(\displaystyle \binom {(N -K +M) +K}{K} = \binom {N +M}{K}\)
となることから、公式 5 が導かれました。
あと、\(K\) が大きいときにどうなりますかという話ですが、なんか点 P がハミ出た場合に最短経路数が \(0\) になって（ハミ出たら最短じゃないので）、いい感じにうまいこといくんですね。
公式 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}\]
最後は斜めバージョンです。
先程と同じように考えれば、次のような図に思い至るでしょう。
残念ながらこれは罠で、うまく数えられていません。
どこが良くないかというと、
実は、同じ経路を何回も数えてしまっています。
たとえば上図の場合、
\(i\) 番目 \(( 0 \le i \le K)\) の点 P\({}_i\) の担当範囲だと思って設定した経路ですが、他の赤い点たち（いわば P の残像です）を幾つも踏みつけてしまっています。
こうなると、点 P\({} _{i +1}\) や P\({} _{i -1}\), P\({} _{i -2}\) を通る経路は何個ですかという課題に対しても全く同じ経路が登場してくるため、全体として数が合いません。
……では、どうしましょうか？？？
私は、こうします。
もうお分かりでしょう。
点 P たちには、少しだけ右に移動していただきました。
（同時に、グリッドの横幅が \(1\) 増加しています。）
こうしてあげることで、
どの最短経路も、ちょうど \(1\) つの赤い点を通過するようにできます。
- 左下の小領域：
- よこ： \(N\)
- たて： \(i\)
- 経路数： \(\displaystyle \binom {N +i}{i}\)
- 右上の小領域：
- よこ： \(M -K\)
- たて： \(K -i\)
- 経路数： \(\displaystyle \binom {(M -K) +(K - i)}{K -i} = \binom {M -i}{K -i}\)
- 全体：
- よこ： \(N +1 +M -K\)
- たて： \(K\)
- 経路数： \(\displaystyle \binom {(N +1 +M -K) +K}{K} = \binom {N +M +1}{K}\)
となるので、公式 6 が導かれますね。
でもこれ、どういう場面で使うのでしょうか。
完結ーー
数え上げ頻出公式について、解釈と導出を確認しました。
緑コーダーでも証明まで辿り着くことができましたね。（記事に 1 年くらいかかりましたが）
頻出公式（修正版）
\(\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)\)
もう、この式を見ても怖くないと思います。
数え上げPDFの内容を全部追うのは何年かかりますか？
