カタラン数の一般項は

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

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

あるいは

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

と表されるが，この公式は母関数を用いると簡明に得ることができる．

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

【１】カタラン数の母関数

　カタラン数の母関数を

　　Ｃ（ｘ）＝ｃ（０）＋ｃ（１）ｘ＋ｃ（２）ｘ^2＋・・・＋ｃ（ｎ）ｘ^n＋・・・

とおく．これを２乗すると

　　Ｃ（ｘ）^2＝ｃ（０）ｃ（０）＋（ｃ（０）ｃ（１）＋ｃ（１）ｃ（０））ｘ＋ （ｃ（０）ｃ（２）＋ｃ（１）ｃ（１）＋ｃ（２）ｃ（０））ｘ^2＋・・・

　ここで，

　　ｃ（０）ｃ（０）＝ｃ（１）

　　ｃ（０）ｃ（１）＋ｃ（１）ｃ（０）＝ｃ（２）

　　ｃ（０）ｃ（２）＋ｃ（１）ｃ（１）＋ｃ（２）ｃ（０）＝ｃ（３）

であるから，

　　Ｃ（ｘ）^2＝ｃ（１）＋ｃ（２）ｘ＋ ｃ（３）ｘ^2＋・・・

次数を揃えるために，両辺にｘをかけて

　　ｘＣ（ｘ）^2＝ｃ（１）ｘ＋ｃ（２）ｘ^2＋ ｃ（３）ｘ^3＋・・・

　　ｘＣ（ｘ）^2＝Ｃ（ｘ）−ｃ（０）＝Ｃ（ｘ）−１

　Ｃ（ｘ）に関する２次方程式を解いて，Ｃ（０）＝１を満足させなければならないので，複号は負号をとると，母関数は

　　Ｃ（ｘ）＝｛１−（１−４ｘ）^1/2｝／２ｘ

　ここでニュートンの二項展開

　　ｄ^n／ｄｘ^n（１−４ｘ）^1/2＝−２^n（２ｎ−３）！！（１−４ｘ）^(1/2-n)

により，一般項

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

　　　　　　＝（２ｎ−２）！／ｎ！（ｎ−１）！

　　　　　　＝（２ｎ−１）！／ｎ！（ｎ−１）！／（２ｎ−１）

が得られる．

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

【２】カタラン数

　カタラン数

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

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

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

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

あるいは

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

と表されます．

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

【３】カタラン数の漸近挙動

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

に対して，スターリングの漸近公式

　　ｋ！＝√２π・ｋ^(k+1/2)・exp（−ｋ）＝√（２πｋ）・（ｋ／ｅ）^k

を適用すると，

　　Ｃn〜２^2n／√（ｎπ）（ｎ＋１）〜４^nｎ^(-3/2)／√π

　　Ｃn／４^nｎ^(-3/2)→１／√π

に収束することがわかる．

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