カタラン数

カタラン数（-すう、英: Catalan number）は、自然数のうち、ベルギーの数学者Eugène Charles Catalanにちなんで名付けられた数である。n番目のカタラン数C_nは以下の式で定義される。

$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!}$

1番目のカタラン数から順に列記すると

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

二項係数を用いた形でカタラン数を表現すると

$C_n = {2n\choose n} - {2n\choose n-1} \quad\mbox{ for }n\ge 1$

となる。また漸化式では

$C_0 = 1 , \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n=\sum_{i=0}^{n}C_i\,C_{n-i}$

母関数は

$\frac{1-\sqrt{1-4x}}{2x}= \sum_{n=0}^\infty {2n \choose n} \frac{x^n}{n+1}$

となる。

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

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

n=2^k-1 （メルセンヌ数）のときのみC_nは奇数となり、そのほかの場合のC_nは偶数となる。

カタラン数の意味

• 3組の()を正しく並べる方法は

((()))     ()(())     ()()()     (())()     (()())

の5通りある。これが C₃=5 の場合に対応している。())()) や )(()() といった形は()を正しく並べていないのでカウントしない。

• 二分木を使って以下の図のように説明することもできる。

C_nはn本の木で作られた二分木にn+1枚の葉をつける方法の総数にあたる。これも C₃=5 の場合に対応している。

• 次の図のように対角線を跨がずに格子点を通って、向かい合った点を最短距離でつなぐ道順の総数と説明できる。

これは C₄=14 の場合に対応している。

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

カタラン数は他にもさまざまな意味づけがなされている。

関連項目

• 集合の分割

外部リンク

• Stanley, R.P.Catalan addendum （PDF）
• Mathworld,Catalan Number