卡特兰数（Catalan number）

数学定义

卡特兰数是一系列自然数，其第 $n$ 项 $C_n$ 定义为：

$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$

其中 $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ 表示 组合数（二项式系数）。

递归定义：

$$C_0=1$$ $$C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i}(n\ge 0)$$

性质

1. 递推关系：

$$C_n=\frac{2(2n-1)}{n+1}{C}_{n-1}$$

2. 生成函数： 卡特兰数的生成函数 $G(x)$ 满足：

$$G(x)=\sum _{n=0}^{\infty }{C}_n{x}^n=\frac{1-\sqrt{1-4x}}{2x}$$

3. 渐近行为： 当 $n\to \infty$ 时，卡特兰数的增长率为：

$$C_n\sim \frac{4^n}{n^{3/2}\sqrt{\pi }}$$

常用场景

卡特兰数在组合数学中有广泛应用，常见场景包括：

1. 括号匹配：$C_n$ 表示长度为 $2n$ 的有效括号序列的数量。
2. 二叉树结构：$C_n$ 表示有 $n+1$ 个叶子的不同构满二叉树的数量。
3. Dyck 路径：在网格中从 $(0,0)$ 到 $(2n,0)$ 不越过对角线的路径数为 $C_n$。
4. 凸多边形三角剖分：将 $(n+2)$ 边形划分为三角形的方式数为 $C_n$。
5. 栈排序问题：长度为 $n$ 的排列可通过栈排序的数量为 $C_n$.