卡特兰数

公式

通项：

$$catalan(n)=\frac{(2n)!}{n!(n+1)!}$$

递推形式：

$$C(n)=\sum _{k=0}^{n-1}C(k)C(n-k-1)=\sum _{k=1}^{n}C(k-1)C(n-k)$$

含义

$n$ 种 A 操作，$n$ 种 B 操作，其中任意时刻 A 操作次数大于 B 操作次数