カタラン数

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

C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\quad (n\geq 0)

で表される。 $n = 0, 1, 2, \dots$ に対してカタラン数は

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, \dots

となる

カタラン数の意味

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

() を正しく並べる方法: 例えば3組の () を正しく（つまり「開き」と「閉じ」が一対一に対応するように）並べる方法は、「((()))」「()(())」「()()()」「(())()」「(()())」の5通りある。これが $C 3 = 5$ に対応している。())()) や )(()() といった形は () を正しく並べていないのでカウントしない。

$C n$ は、 $n$ 個の分岐を持つ（ $n + 1$ 枚の葉を持つ）二分木の総数である。上記の図は $C 3 = 5$ の場合に対応している。

格子状の経路数え上げ: $C n$ は、縦横 $n$ マスずつの格子において、次の図のように対角線を跨がずに格子点を通って、向かい合った点を最短距離で繋ぐ道順の総数と説明できる。

上記の図は $C 4 = 14$ の場合に対応している。

多角形の三角形分割: $n + 2$ 個の辺からなる凸多角形を、頂点どうしを結ぶ線を互いに交差しないように引いて、 $n$ 個の三角形に切り分けることを考える。この分け方の場合の数は、カタラン数 $C n$ である。以下の図は $n = 4$ の場合である。

カタラン数は

C_{n}={2n \choose n}-{2n \choose n-1}\quad {\mbox{ for }}n\geq 1

と表せる。

{\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}}

となる。

{\frac {1-{\sqrt {1-4x}}}{2x}}=\textstyle \sum \limits _{n=0}^{\infty }\displaystyle {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$ は奇数となり、それ以外の $n$ における $C n$ は偶数となる。

ウィキペディア	ランダム
毎日	カテゴリ