Processing math: 50%
Home > libalgo > カタラン数

カタラン数

説明

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

C0=1Cn+1=2(2n+1)n+2Cn=ni=0CiCni=C0Cn+C1C_n1+C2Cn2++CnC0

一般項は

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

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