Aritalab:Lecture/NetworkBiology/Catalan

カタラン数

カタラン数は n 番目のカタラン数 C_n は以下で定義される。

$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{2n!}{(n+1)! n!} = \binom{2n}{n} - \binom{2n}{n-1}$

正方格子において (0,0) から (n, n) にいく最短の道筋 (2 n ステップ) のうち、 y = x の対角線より上に出ないものの総数はカタラン数になる。

1番目のカタラン数から順に列記すると

1, 2, 5, 14, 42, 132, 429, ...

となる。