コインゲーム（5）

元に戻って、
直線が、y = x + N のときの経路数を数える。

(x, x + N) ではじめてぶち当たる経路数の母関数を G_N、
当たってもいいが抜けないで (x, x + N) を通る経路数の母関数を F_N とする。

経路を考えるのに、まず最初に直線に当たる経路とそこから先と分けて考える。
そうすると、

F_N = G_NF
(F = F₀ とする)

となることが分かる。
（この辺は母関数に慣れていないと分かりにくいかもしれないが、
とにかく展開してみるとわかる）
また、

G_N+1 = F_N

だから、

G_N = F^N

よって、

P(X=2k+N) = p^k(1-p)^k+Na_k

ただし、

F(x)^N = a₀ + a₁x + a₂x² + ...

例によって確率を全部足すと1になることを確かめる。
a_k をまともに計算するのは難しそうなので、
母関数のまま考えてみるのが常套手段。

この項、つづく。