カタラン数（カタランすう、）は、自然数のうち、ベルギーの数学者ウジェーヌ・カタランに因んで名付けられた数である。"n"番目のカタラン数 C は以下の式で表される。カタラン数を数列として順に列記すると二項係数を用いた形でカタラン数を表現するととなる。また漸化式では母関数はとなる。"n" が十分大きいとき、次の式でカタラン数を近似することができる。（なおこれはウォリスの公式から証明できる）"n" = 2 − 1（メルセンヌ数）のときのみ "C" は奇数となり、それ以外の "n" における "C" は偶数となる。カタラン数は様々な意味付けがなされている。以下に例を示す。

出典:wikipedia