カタラン数 - 暇つぶしWikipedia

カタラン数

.mw-parser-output .hatnote{margin:0.5em 0;padding:3px 2em;background-color:transparent;border-bottom:1px solid #a2a9b1;font-size:90%}

「カタランの定数」とは異なります。

初等組合せ論におけるカタラン数（カタランすう、英: Catalan number）は、ベルギーの数学者ウジェーヌ・カタランに因んで名付けられた自然数のクラスである。n番目のカタラン数 Cn は C n = 1 n + 1 ( 2 n n ) = ( 2 n ) ! ( n + 1 ) ! n ! ( n ≥ 0 ) {\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\quad (n\geq 0)}

で表される [1]。

n = 0, 1, 2, … に対してカタラン数は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 である。
性質

カタラン数は C n = ( 2 n n ) − ( 2 n n − 1 ) for n ≥ 1 {\displaystyle C_{n}={2n \choose n}-{2n \choose n-1}\quad {\mbox{ for }}n\geq 1}

と表せる。

漸化式では C 0 = 1 , C 1 = 1 , C n + 1 = 2 ( 2 n + 1 ) n + 2 C n = ∑ 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 {\displaystyle {\begin{aligned}C_{0}&=1,\quad C_{1}=1,\\C_{n+1}&={\frac {2(2n+1)}{n+2}}\,C_{n}=\textstyle \sum \limits _{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{aligned}}}

となる。

母関数は 1 − 1 − 4 x 2 x = ∑ n = 0 ∞ ( 2 n n ) x n n + 1 {\displaystyle {\frac {1-{\sqrt {1-4x}}}{2x}}=\textstyle \sum \limits _{n=0}^{\infty }\displaystyle {2n \choose n}{\frac {x^{n}}{n+1}}}

となる。

n が十分大きいとき、次の式でカタラン数を近似することができる（なおこれはウォリスの公式から証明できる）： C n ∼ 4 n n 3 / 2 π . {\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}.}

Size:14 KB
出典: フリー百科事典『ウィキペディア（Wikipedia）』
担当:undef