補足 - カタラン数

[] [] []


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

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

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

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

 ((x0x1)x2)x3  (x0x1)(x2x3)  (x0(x1x2))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)まで行く経路と11に対応しその数は2nCn-1

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

◇◇

カタラン数は次の漸化式(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)x1だけ通っていく経路と11に対応しているから。

したがって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が得られる。


[] [] []