Catalan number

ウィキペディア

カタラン数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/02/10 04:31 UTC 版)

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

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

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

格子状の経路数え上げ

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

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

多角形の三角形分割

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

平面グラフの交差

2n人が円になって手を交差させないで握手をする場合の数はカタラン数 C_n である。

非交差分割

集合 {1, 2, …, n} の非交差分割の数はカタラン数 C_n である。

性質

カタラン数は

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

• ドイツ
• イスラエル
• アメリカ
• チェコ

Weblio日本語例文用例辞書

「Catalan number」の例文・使い方・用例・文例

• 話し中です (《主に英国で用いられる》 The number's engaged.).