卡特兰数

卡塔兰数（Catalan number）是组合数学中非常重要的数列，广泛应用于多种结构的计数问题。第 n 项用 $C_n$ 表示。

定义

递推公式：

$$C_0 = 1, \quad C_n = \sum_{i=0}^{n-1} C_i C_{n-i-1} \quad (n \geq 1)$$

闭式公式：

$$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!\, n!}$$

应用场景

• 不同二叉树个数：n 个节点构成不同二叉树的个数为 $C_n$
• 合法括号序列数：n 对括号的合法组合数
• 二叉搜索树个数：n 个不同元素形成的不同 BST 个数
• 多边形三角剖分数

典型例题

四个节点的不同二叉树个数：

$$C_4 = \frac{1}{5} \binom{8}{4} = \frac{1}{5} \times 70 = 14$$