カタラン数のソースを表示

{{混同|カタランの定数}}
[[初等組合せ論]]における'''カタラン数'''（カタランすう、{{lang-en-short|Catalan number}}）は、[[ベルギー]]の[[数学者]][[ウジェーヌ・カタラン]]に因んで名付けられた[[自然数]]のクラスである。{{mvar|n}}番目のカタラン数 {{mvar|C{{sub|n}}}} は
:<math>C_n =\frac{1}{n+1}{2n\choose n} =\frac{(2n)!}{(n+1)!\,n!} \quad (n \ge 0)</math>
で表される<ref>ここで<math>\textstyle\binom{2n}{2}</math>は[[組合せ (数学)|Combination]]すなわち{{mvar|{{msub|2n}}C{{msub|n}}}}のことである。</ref>。

{{math2|1=''n'' = 0, 1, 2, …}} に対してカタラン数は
: {{math|[[1]], [[1]], [[2]], [[5]], [[14]], [[42]], [[132]], [[429]], [[1430]], 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, …}}（{{OEIS|id=A000108}}）
となる

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

; [[ダイク言語|() を正しく並べる方法]]
: 例えば3組の () を正しく（つまり「開き」と「閉じ」が一対一に対応するように）並べる方法は、「{{nowrap|((()))}}」「{{nowrap|()(())}}」「{{nowrap|()()()}}」「{{nowrap|(())()}}」「{{nowrap|(()())}}」の5通りある。これが {{math2|1=''C''{{sub|3}} = 5}} に対応している。{{nowrap|())())}} や {{nowrap|)(()()}} といった形は () を正しく並べていないのでカウントしない。

; [[二分木]]
[[画像:Catalan number binary tree example.png|center]]
{{mvar|C{{sub|n}}}} は、{{mvar|n}}個の分岐を持つ（{{math2|''n'' + 1}}枚の葉を持つ）二分木の総数である。上記の図は {{math2|1=''C''{{sub|3}} = 5}} の場合に対応している。

; 格子状の経路数え上げ
: {{mvar|C{{sub|n}}}} は、縦横 {{mvar|n}}マスずつの格子において、次の図のように[[対角線]]を跨がずに[[格子点]]を通って、向かい合った点を最短距離で繋ぐ道順の総数と説明できる。
[[画像:Catalan number 4x4 grid example.svg|400px|center]]
上記の図は {{math2|1=''C''{{sub|4}} = 14}} の場合に対応している。

; 多角形の三角形分割
: {{math2|''n'' + 2}}個の辺からなる[[凸多角形]]を、頂点どうしを結ぶ線を互いに交差しないように引いて、{{mvar|n}}個の三角形に切り分けることを考える。この分け方の場合の数は、カタラン数 {{mvar|C{{sub|n}}}} である。以下の図は {{math2|1=''n'' = 4}} の場合である。
{{main|多角形の三角形分割}}
[[画像:Catalan-Hexagons-example.svg|400px|center]]

; 平面グラフの交差
: {{math|2''n''}}人が円になって手を交差させないで握手をする場合の数はカタラン数 {{mvar|C{{sub|n}}}} である。

; [[非交差分割]]
: 集合 {{math|{{mset|1, 2, …, ''n''}}}} の非交差分割の数はカタラン数 {{mvar|C{{sub|n}}}} である。

== 性質 ==
カタラン数は
:<math>C_n = {2n\choose n} - {2n\choose n-1} \quad\mbox{ for }n\ge 1</math>
と表せる。

[[漸化式]]では
:<math>\begin{align}
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{align}</math>
となる。

[[母関数]]は
:<math>\frac{1-\sqrt{1-4x}}{2x}= \textstyle\sum\limits_{n=0}^\infty \displaystyle{2n \choose n} \frac{x^n}{n+1}</math>
となる。

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

{{math2|1=''n'' = 2{{sup|''k''}} &minus; 1}}（[[メルセンヌ数]]）のときのみ {{mvar|C{{sub|n}}}} は[[奇数]]となり、それ以外の {{mvar|n}} における {{mvar|C{{sub|n}}}} は[[偶数]]となる。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
*[[集合の分割]]

== 外部リンク ==
* {{高校数学の美しい物語|657|カタラン数の意味と漸化式}}
*寺尾宏明「カタラン数の語る数学の世界-Enumerrative Combinatorics入門」（『高校生のための数学口座』、北海道大学　2006.7.31）[https://www.math.sci.hokudai.ac.jp/~terao/hokudaihs.pdf]
* Stanley, R.P.[http://www-math.mit.edu/~rstan/ec/catadd.pdf Catalan addendum (PDF)]
* {{MathWorld|urlname=CatalanNumber|title=Catalan Number|author=Stanley, Richard; Weisstein, Eric W.}}
* {{PlanetMath|urlname=CatalanNumbers|title=Catalan numbers}}
* {{nlab|urlname=Catalan+number|title=Catalan number}}
* {{ProofWiki|urlname=Definition:Catalan_Number|title=Catalan Number}}

{{Normdaten}}
{{DEFAULTSORT:かたらんすう}}
[[Category:数論]]
[[Category:整数の類]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]