カタラン数

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

$C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n+1)!n!}(n\ge 0)$

で表される。

テンプレート:Math2 に対してカタラン数は

テンプレート:Math（テンプレート:OEIS）

となる

カタラン数の意味

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

() を正しく並べる方法

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

二分木

テンプレート:Mvar は、テンプレート:Mvar個の分岐を持つ（テンプレート:Math2枚の葉を持つ）二分木の総数である。上記の図は テンプレート:Math2 の場合に対応している。

格子状の経路数え上げ

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

上記の図は テンプレート:Math2 の場合に対応している。

多角形の三角形分割

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

平面グラフの交差

テンプレート:Math人が円になって手を交差させないで握手をする場合の数はカタラン数 テンプレート:Mvar である。

非交差分割

集合 テンプレート:Math の非交差分割の数はカタラン数 テンプレート:Mvar である。

性質

カタラン数は

$C_n=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n-1})\text{ for }n\ge 1$

と表せる。

漸化式では

$\begin{array}{cc}{C}_0& =1,C_1=1,\\ C_{n+1}& =\frac{2(2n+1)}{n+2}{C}_n=\sum _{i=0}^n{C}_i{C}_{n-i}=C_0{C}_n+C_1{C}_{n-1}+C_2{C}_{n-2}+\cdots +C_n{C}_0\end{array}$

となる。

母関数は

$\frac{1-\sqrt{1-4x}}{2x}=\sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{2n}{n})\frac{x^n}{n+1}$

となる。

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

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

テンプレート:Math2（メルセンヌ数）のときのみ テンプレート:Mvar は奇数となり、それ以外の テンプレート:Mvar における テンプレート:Mvar は偶数となる。

関連項目

• 集合の分割

外部リンク

• テンプレート:高校数学の美しい物語
• 寺尾宏明「カタラン数の語る数学の世界-Enumerrative Combinatorics入門」（『高校生のための数学口座』、北海道大学　2006.7.31）[1]
• Stanley, R.P.Catalan addendum (PDF)
• テンプレート:MathWorld
• テンプレート:PlanetMath
• テンプレート:Nlab
• テンプレート:ProofWiki