カタラン数

説明

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

$$\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 などで求めます．