メインメニューを開く

初等組合せ論におけるカタラン数(カタランすう、: 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 に対応している。())()))(()() といった形は () を正しく並べていないのでカウントしない。
二分木
Cn は、n 個の分岐を持つ(n + 1 枚の葉を持つ)二分木の総数である。上記の図は C3 = 5 の場合に対応している。
格子状の経路数え上げ
Cn は、縦横 n マスずつの格子において、次の図のように対角線を跨がずに格子点を通って、向かい合った点を最短距離で繋ぐ道順の総数と説明できる。:上記の図は C4 = 14 の場合に対応している。
多角形の三角形分割
n + 2 個の辺からなる凸多角形を、頂点どうしを結ぶ線を互いに交差しないように引いて、n 個の三角形に切り分けることを考える。この分け方の場合の数は、カタラン数 Cn である。以下の図は n = 4 の場合である。詳しくは多角形の三角形分割を参照。
平面グラフの交差
2n 人が円になって手を交差させないで握手をする場合の数はカタラン数 Cn である。
非交差分割
集合{1, 2, ..., n}の非交差分割の数はカタラン数 Cn である。

性質編集

カタラン数は

 

と表せる。

漸化式では

 

となる。

母関数

 

となる。

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

 

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

関連項目編集

外部リンク編集

  • Stanley, R.P.Catalan addendum (PDF)
  • Stanley, Richard; Weisstein, Eric W.. "Catalan Number". MathWorld(英語).
  • Catalan numbers - PlanetMath.(英語)
  • Catalan number in nLab
  • Catalan Number at ProofWiki