カタラン数とは？ わかりやすく解説

「カタランの定数」とは異なります。

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

${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\quad (n\geq 0)}$

C_n は、n個の分岐を持つ（n + 1枚の葉を持つ）二分木の総数である。上記の図は C₃ = 5 の場合に対応している。

格子状の経路数え上げ

C_n は、縦横 nマスずつの格子において、次の図のように対角線を跨がずに格子点を通って、向かい合った点を最短距離で繋ぐ道順の総数と説明できる。

上記の図は C₄ = 14 の場合に対応している。

多角形の三角形分割

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

詳細は「多角形の三角形分割」を参照

平面グラフの交差

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

非交差分割

集合 {1, 2, …, n} の非交差分割の数はカタラン数 C_n である。

性質

カタラン数は

${\displaystyle C_{n}={2n \choose n}-{2n \choose n-1}\quad {\mbox{ for }}n\geq 1}$

• ドイツ
• イスラエル
• アメリカ
• チェコ