カタラン数計算機
組み合わせ論や二分木に応用されるカタラン数を計算します
非負整数を入力してください（0から30まで）
結果
値を入力して、計算をクリックすると結果が表示されます。
理論と公式
カタラン数
カタラン数は、再帰的に定義された対象を含むさまざまな計数問題に現れる自然数の数列を形成します。n番目のカタラン数は、n組の括弧が正しく対応している式の数を数えます。
公式
\(C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\)
\(C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}\)
最初の公式は二項係数を用い、二番目は再帰的定義です
応用
- n組の括弧を正しく対応させる方法の数
- 葉がn+1個ある異なる二分木の数
- (0,0) から (n,n) までの、対角線を越えない経路の数
- n+2 辺の凸多角形を三角分割する方法の数
- 円周上の 2n 点を n 本の交差しない弦で結ぶ方法の数
最初のカタラン数
最初のいくつかのカタラン数は: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796...
例
C₃（3 組の括弧の組み合わせ数）を計算する：
\(C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \cdot 20 = 5\)