カタラン数の意味
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/11 16:34 UTC 版)
カタラン数は様々な意味付けがなされている。以下に例を示す。 () を正しく並べる方法 例えば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 である。
※この「カタラン数の意味」の解説は、「カタラン数」の解説の一部です。
「カタラン数の意味」を含む「カタラン数」の記事については、「カタラン数」の概要を参照ください。
ウィキペディア小見出し辞書の「カタラン数の意味」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- カタラン数の意味のページへのリンク
