ホーム > libalgo

カタラン数

説明

以下の漸化式で定まる数列をカタラン数といいます.

$$\begin{eqnarray} C_0 &=& 1 \
C_{n+1} &=& \frac{2(2n+1)}{n+2} C_n \
&=& \sum_{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{eqnarray}$$

一般項は

$$C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n-1}\binom{2n}{n}$$

となります.実装では組み合わせ係数を DP などで求めます.