【２】カタラン数

　カタラン数

　　｛Ｃn｝＝｛１，２，５，１４，４２，１３２，４２９，１４３０，４８６２，１６７９６，・・・｝

は，凸ｎ角形を対角線で三角形分割する仕方は何通りあるかとか，ｎ対のかみ合い括弧の種類数などいろいろな場面で登場する数なのですが，

　　Ｃn＝2nＣn／（ｎ＋１）＝（２ｎ）！／ｎ！（ｎ＋１）！，

　　Ｃn＝2n+1Ｃn／（２ｎ＋１），

あるいは

　　Ｃn＝2nＣn−2nＣn-1＝１，２，５，１４，４２，・・・

と表されます．

　カタラン数から一般項が何かを予想するのは難しいのですが，ここでは

　　Ｃn＝2nＣn／（ｎ＋１）　　　（Ｃ0＝１）

がわかっているものとして，母関数

　　Ｆ（ｔ）＝ΣＣnｔ^n

を求めてみます．

　この級数は，第０項：Ｃ0＝１から始まるので，そのまま項比をとると

　　ａn+1ｘn+1/ａnｘn=(n+1/2)(n+1)/(n+2)*4x/(n+1)

したがって，

　　Ｆ（ｘ）＝2Ｆ1(1/2,1,2,4x)=2/{1+(1-4x)^(1/2)}

　　　　　　＝{1-(1-4x)^(1/2)}/2x

　　(1-4x)^(1/2)＝Σ(-4)^k1/2Ck･ｘ^k

より

　　Ｃn＝-1/2(-4)^(n+1)1/2C(n+1)

これをさらに式変形すれば，

　　Ｃn＝2nＣn／（ｎ＋１）

になる．この結果，二項展開を丹念に使えば

　　{1-(1-4x)^(1/2)}/2x=Σ2nCnx^n/(n+1)

が得られるはず・・・．

　この方法は試してはいないのですが，かなり面倒そうです．実はカタラン数に対しては，漸化式

　　Ｃn＝ΣＣkＣn-k-1＝Ｃ0Ｃn-1＋Ｃ1Ｃn-2＋・・・＋Ｃn-1Ｃ0

が成り立つので，母関数は

　　Ｆ（ｔ）＝ΣＣnｔ^n＝ΣＣkｔ^kΣＣn-k-1ｔ^n-k＋１

　　　　　　＝Ｆ（ｔ）・ｔＦ（ｔ）＋１

すなわち，

　　ｔＦ（ｔ）^2−Ｆ（ｔ）−１＝０

なる２次方程式を満たすことが知られています．

　Ｃ0＝１を満足させなければならないので，複号は負号をとると，

　　Ｆ（ｔ）＝{1-(1-4x)^(1/2)}/2x

がでてきます．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝