F - Many Many Pathsを解いててパスカルの三角形おもしろと思ったのでメモる。

メモです。内容が乏しい。

以下のDPテーブルを考える。

このDPテーブルは各グリットの最短経路の個数を示す。（0-indexed)

すなわちdp[i][j] = comb(i+j,j)である。

(comb(x,y) = $\binom{x}{y}$ を表す。)

このテーブルで(0,0)を一番上に来るように回転させて見るとパスカルの三角形の一部が現れる。

dp[i][j] = dp[i-1][j] + dp[i][j-1]

dpの配り方から明らか。あるマスは左のマスと下のマスの和である。（範囲外は0と考えてよい。ただしdp[0][0]=1である。）

$\displaystyle{ \sum_{k=0}^{n} dp[k][n-k] = 2^n }$

これは二項定理を考えるとわかりやすい。

$(1+x)^ n$ を展開したときの多項式の係数がそれぞれdp[i][n-i]に一致する。ここでx=1とすると上式が導ける。

あるいはbit全探索を思い出してほしい。生成可能な長さnのビット列において１が立っている個数がi個であるビット列はいくつか？という問に対して、dp[i][n-i]である。0 <= i <= nであるからして全部数えたら $2^ n$ である。

これはD - Knightで学んだ記憶がある。

$\displaystyle{ \sum_{i=0}^{x}\sum_{j=0}^{y} dp[i][j] = dp[i+1][j+1] - 1 }$

よくわかりません。どうして？

まだまだ面白性質あります。よくわからんけど

数式書くのむずかしいぜ。はてな

zero’s notepad