カタラン数

カタラン数（-すう、英: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=\sum_{i=0}^{n}C_i\,C_{n-i}$

$\frac{1-\sqrt{1-4x}}{2x}= \sum_{n=0}^\infty {2n \choose n} \frac{x^n}{n+1}$

となる。

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

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

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

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

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

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

C_nはn本の木で作られた二分木にn+1枚の葉をつける方法の総数にあたる。

これは C₄=14 の場合に対応している。

カタラン数は他にもさまざまな意味づけがなされている。