Processing math: 50%
Home
>
libalgo
>
カタラン数
カタラン数
説明
以下の漸化式で定まる数列をカタラン数といいます.
C
0
=
1
C
n
+
1
=
2
(
2
n
+
1
)
n
+
2
C
n
=
n
∑
i
=
0
C
i
C
n
−
i
=
C
0
C
n
+
C
1
C
_
n
−
1
+
C
2
C
n
−
2
+
⋯
+
C
n
C
0
一般項は
C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n-1}\binom{2n}{n}
となります.実装では組み合わせ係数を DP などで求めます.