カタラン数

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

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

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

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

となる。

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

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

() を正しく並べる方法
例えば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 である。

性質[編集]

カタラン数は

と表せる。

漸化式では

となる。

母関数

となる。

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

n = 2k − 1(メルセンヌ数)のときのみ Cn奇数となり、それ以外の n における Cn偶数となる。

関連項目[編集]

外部リンク[編集]