カタラン数

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

[math]C_n =\frac{1}{n+1}{2n\choose n} =\frac{(2n)!}{(n+1)!\,n!}[/math]

で表される。カタラン数を数列として順に列記すると

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, …（オンライン整数列大辞典の数列 A000108）

となる。

カタラン数の意味

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

() を正しく並べる方法

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

二分木

ファイル:Catalan number binary tree example.png

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

格子状の経路数え上げ

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

400px

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

平面グラフの交差

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

性質

カタラン数は

[math]C_n = {2n\choose n} - {2n\choose n-1} \quad\mbox{ for }n\ge 1[/math]

と表せる。

漸化式では

[math]\begin{align} C_0 &=1, \quad 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{align}[/math]

となる。

母関数は

[math] \frac{1-\sqrt{1-4x}}{2x}= \sum_{n=0}^\infty {2n \choose n} \frac{x^n}{n+1} [/math]

となる。

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

[math]C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}.[/math]

n = 2^k − 1（メルセンヌ数）のときのみ C_n は奇数となり、それ以外の n における C_n は偶数となる。

関連項目

• 集合の分割

外部リンク

• Stanley, R.P.Catalan addendum (PDF)
• Stanley, Richard; Weisstein, Eric W.. “Catalan Number”. MathWorld（英語）.
• Catalan numbers - PlanetMath.（英語）
• Catalan number in nLab
• テンプレート:ProofWiki