カタラン数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

カタラン数(カタランすう、: Catalan number)は、自然数のうち、ベルギー数学者ウジェーヌ・カタランにちなんで名付けられた数である。n番目のカタラン数 Cn は以下の式で定義される。

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, ...(オンライン整数列大辞典の数列 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}= C_0 \, C_n + C_1 \, C_{n-1} + C_2 \, C_{n-2} + ... + C_n \, C_0

母関数

 \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 = 2k - 1(メルセンヌ数)のときのみ Cn奇数となり、それ以外の n における Cn偶数となる。

カタラン数の意味[編集]

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

()を正しく並べる方法
例えば3組の()を正しく並べる方法は、「((()))」「()(())」「()()()」「(())()」「(()())」の5通りある。これが C3=5 の場合に対応している。())()) や )(()() といった形は()を正しく並べていないのでカウントしない。
二分木
Catalan number binary tree example.png
Cnは、n個の分岐を持つ(n+1枚の葉を持つ)二分木の総数である。上記の図は C3=5 の場合に対応している。
格子状の経路数え上げ
Cnは、縦横nマスずつの格子において、次の図のように対角線を跨がずに格子点を通って、向かい合った点を最短距離でつなぐ道順の総数と説明できる。
Catalan number 4x4 grid example.svg
上記の図は C4=14 の場合に対応している。
平面グラフの交差
2n人が円になって手を交差させないで握手をする場合の数はカタラン数Cnである。

関連項目[編集]

外部リンク[編集]