補足 - カタラン数

[←]　[↑]　[→]

1次元ランダムウォークにおいて、座標O(t=0,x=0)からP(t=2n,x=0)まで正側x≧0だけ通って行く経路の数cnはカタラン数と呼ばれる数である。

同様に、次の例もカタラン数である。

(例1) n×nの碁盤目を、対角線より下だけ通って(↑の数が→の数を超えないようにして)行く経路の数

(例2) n回のかけ算に、順序を示す括弧（）をつける方法の数

　((x0・x1)・x2)・x3  (x0・x1)・(x2・x3)  (x0・(x1・x2))・x3  ...

◇

カタラン数cnは図形的な対称性を利用すると簡単に求められる。なお、以下の説明は「数え上げ理論」(野崎昭弘)によっている。

座標O(t=0,x=0)からP(t=2n,x=0)まで行く経路は全部で 2nCn個

このうち負側x<0を通る経路は必ずx=-1に到達するから、最初にx=-1に到達した以降の経路を直線x=-1で折り返すと、OからQ(t=2n,x=-2)まで行く経路と1対1に対応しその数は 2nCn-1個

したがってOからPまで負側x<0を通らずに、すなわち正側x≧0だけ通って行く経路の数は

◇◇

カタラン数は次の漸化式(n-1以前の自分自身とのたたみ込みがnの値になる)の解である。

一般に、O(t=0,x=0)からP(t=2n,x=0)まで純粋に正側x>0(x≧0でなく)だけを通って行く経路の数もカタラン数cn-1になる。なぜなら(t=1,x=1)から(t=2n-1,x=1)へx≧1だけ通っていく経路と1対1に対応しているから。

したがって、Oから中間点Mまではx≧0を通って行き、MからPまではx>0だけ通って行く経路に場合分けすると

OからMまではckとおり、MからPまではcn-1-kだから上記の漸化式が得られる。

このたたみ込みの漸化式からcnの閉じた式はとても求められそうにないのだが、たたみ込みの数列の母関数は元の数列の母関数どうしの積になることを使うと何と解けてしまう。以下の計算は「コンピュータの数学」(クﾇｰス)によっている。

cnの母関数は、

漸化式を使うと

とC(z)の2次方程式が得られる。条件C(0)=1を満たす方の解をとると

この平方根をnを実数に拡張した2項定理を使ってべき級数に直すと

と、上記で図形的に求めたのと同じcnが得られる。

[←]　[↑]　[→]