カタラン数

初等組合せ論におけるカタラン数（カタランすう、）は、ベルギーの数学者ウジェーヌ・カタランに因んで名付けられた自然数のクラスである。番目のカタラン数  は

で表されるここではCombinationすなわちのことである。。

 に対してカタラン数は
 （）
となる。カタランの名を冠するが、清の数学者明安図が先行して発見している。

 カタラン数の意味 
カタラン数は様々な意味付けがなされている。以下に例を示す。

 () を正しく並べる方法
 例えば3組の () を正しく（つまり「開き」と「閉じ」が一対一に対応するように）並べる方法は、「」「」「」「」「」の5通りある。これが  に対応している。 や  といった形は () を正しく並べていないのでカウントしない。

 二分木
center
 は、個の分岐を持つ（枚の葉を持つ）二分木の総数である。上記の図は  の場合に対応している。

 格子状の経路数え上げ
  は、縦横 マスずつの格子において、次の図のように対角線を跨がずに格子点を通って、向かい合った点を最短距離で繋ぐ道順の総数と説明できる。
400px|center
上記の図は  の場合に対応している。

 多角形の三角形分割
 個の辺からなる凸多角形を、頂点どうしを結ぶ線を互いに交差しないように引いて、個の三角形に切り分けることを考える。この分け方の場合の数は、カタラン数  である。以下の図は  の場合である。

400px|center

 平面グラフの交差
 人が円になって手を交差させないで握手をする場合の数はカタラン数  である。

 非交差分割
 集合  の非交差分割の数はカタラン数  である。

 性質 
カタラン数は

と表せる。

漸化式では

となる。

母関数は

となる。

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

（メルセンヌ数）のときのみ  は奇数となり、それ以外の  における  は偶数となる。

 脚注 

 関連項目 
集合の分割

 外部リンク 

寺尾宏明「カタラン数の語る数学の世界-Enumerrative Combinatorics入門」（『高校生のための数学口座』、北海道大学　2006.7.31）
 Stanley, R.P.Catalan addendum (PDF)





Category:数論
Category:整数の類
Category:数学に関する記事
Category:数学のエポニム