ABC 154 F Many Many Paths 図解解説

まず，f(r, c) を表形式で図示します．数字が大きすぎて省略されてしまっている部分がありますが，無視してください．

ところで，この値は パスカルの三角形 (のちょっと内側) と一致しています．ゆえに，f(r, c) = f(r-1, c) + f(r, c-1) と表せます．・・・①

さて，今したいのは，この表中の任意の長方形について，その和を求めることです．長方形の和は次のように，左上を直角とする 3 つの直角二等辺三角形の足し引きで表すことが出来ます．

よって，表中の任意の三角形について，その和が求められれば良いことがわかりました．

ここで，ある三角形についてその周りの値を適当に文字で置き，三角形内の各値を求めると①より次のようになります．なお，周りの値は f(r, c) = (r+c)!/(r!c!) であることを用いて求めます．

更に，a だけに着目すると，こうなります．

すると，a の係数がまたもパスカルの三角形になっています．(まあそれはそうです．)

もちろん，他の文字，例えば b に注目しても係数がパスカルの三角形になっています．

ところで，パスカルの三角形の i 段目の和は 2^i-1 になります．(二項定理を使って証明できます．) よって，1 ～ i 段目の和は 2ⁱ -1 です．

したがって，今着目している三角形の場合，その和は a×(2⁴-1) + b×(2³-1) + c×(2²-1) + d×(2¹-1) + x×(2⁴-1) + y×(2³-1) + z×(2²-1) + s×(2¹-1) となります．

まとめ