カタラン数と経路の数と漸化式

原点と(n,n)を結ぶ最短経路は ${}_{2n}{\rm C}^{}_{n}$ だが、このうち領域 $y\leq x$ に含まれるものの個数はカタラン数になる。鏡像を使う方法が簡単だが思いつきにくい。ここでは漸化式を考える。

上記の場合の数をA(n)と書くことにする。これらの経路を、直線y=x上(ただし原点を除く)に初めて到着する点(k,k)で分類する。ただし、 $1\leq k \leq n$ である。すると、原点→(1,0)→(k,k-1)→(k,k)→(n,n)となる。(1,0)→(k,k-1)の経路はA(k-1)通りであり、(k,k)→(n,n)の経路はA(n-k)通りである。ただし、k=1の場合は前者は１通りなので、A(0)=1 と約束しておく。すると、全体では
$A(n)=\sum_{k=1}^{n}A(k-1)A(n-k)$
となる。右辺はいわゆる合成積(Convolution)であり、この漸化式を解くには、母関数 $f(x)=\sum_{k=1}^{\infty}A(k)x^k$ を考えるのだが、長くなるので今日はここまで。