カタラン数

初等組合せ論におけるカタラン数（カタランすう、）は、ベルギーの数学者に因んで名付けられた自然数のクラスである。番目のカタラン数 は
で表される。 に対してカタラン数は
となる
カタラン数の意味.
カタラン数は様々な意味付けがなされている。以下に例を示す。
 は、個の分岐を持つ（枚の葉を持つ）二分木の総数である。上記の図は の場合に対応している。
上記の図は の場合に対応している。
性質.
カタラン数は
と表せる。
漸化式では
となる。
母関数は
となる。
"n" が十分大きいとき、次の式でカタラン数を近似することができる（なおこれはウォリスの公式から証明できる）：
（メルセンヌ数）のときのみ は奇数となり、それ以外の における は偶数となる。