カタラン数

カタラン数（-すう、英:Catalan number）は自然数で、ベルギーの数学者 Eugène Charles Catalanによって名付けられた数である。n番目のカタラン数C_nは以下の式で定義される。

$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!}$

1番目のカタラン数から順に列記すると

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, …

二項係数を用いた形でカタラン数を表現すると

$C_n = {2n\choose n} - {2n\choose n-1} \quad\mbox{ for }n\ge 1$

となる。また漸化式では

$C_0 = 1 , \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n$

nが十分大きいとき、次の式でカタラン数を近似することができる。（なおこれはスターリングの公式から証明できる）

$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$

n=2^k-1 のときのみC_nは奇数となり、そのほかの場合のC_nは偶数となる。

[編集] カタラン数の意味

3組の()を正しく並べる方法は

((())) ()(()) ()()() (())() (()())

の5通りある。これが C₃=5 の場合に対応している。())()) や )(()() といった形は()を正しく並べていないのでカウントしない。

二分木を使って以下の図のように説明することもできる。
C_nはn本の木で作られた二分木にn+1枚の葉をつける方法の総数にあたる。

次の図のように対角線を跨がずに向かい合った点をつなぐ道順の総数と説明できる。
これは C₄=14 の場合に対応している。カタラン数は他にもさまざまな意味づけがなされている。

この項目「カタラン数」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。（ポータル数学／ウィキプロジェクト数学）