Catalan 数

一句话理解

Catalan 数：C_n = C(2n,n)/(n+1)。

为什么要学

合法括号、出栈、二叉树、凸包三角剖分。

讲解

递推 C_0=1，C_{n+1}=∑ C_i C_{n-i}。

例子

n 对括号的合法序列数。

常见错误

• 模意义下除以 n+1 要用逆元。
• 下标差 1。