形式陈述

Catalan 数定义为

$$ C_n=\frac1{n+1}\binom{2n}{n} =\binom{2n}{n}-\binom{2n}{n+1}, \qquad n\ge0. $$$$C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n+1}),n\ge 0.$$

它满足 $C_0=1$$C_0=1$ 和卷积递推

$$ C_{n+1}=\sum_{i=0}^n C_iC_{n-i}. $$$$C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i}.$$

普通生成函数 $C(x)=\sum_{n\ge0}C_nx^n$$C(x)=\sum _{n\ge 0}{C}_n{x}^n$ 满足

$$ C(x)=1+xC(x)^2, $$$$C(x)=1+xC(x{)}^2,$$

从而

$$ C(x)=\frac{1-\sqrt{1-4x}}{2x} $$$$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$

取常数项为一的分支。Catalan 数计数半长为 $n$$n$ 的 Dyck 路、$n+1$$n+1$ 个叶子的平面满二叉树、凸 $(n+2)$$(n+2)$ 边形三角剖分等。

直觉

许多递归对象都有一个唯一的最外层切分；切分左右两侧独立产生 $C_iC_{n-i}$$C_i{C}_{n-i}$，对所有切分位置求和便得到 Catalan 递推。

例子与边界

$C_0,C_1,C_2,C_3,C_4=1,1,2,5,14$$C_0,C_1,C_2,C_3,C_4=1,1,2,5,14$。长度 $2n$$2n$ 的括号序列需每个前缀左括号不少于右括号，不能只要求总数相等；反射原理从中央二项式系数中减去越界路径。并非所有“树”都由 Catalan 数计数，必须明确平面次序、根和节点度数等约定。公式中的平方根是形式幂级数分支；作为解析函数时其收敛半径为 $1/4$$1/4$。不同 Catalan 对象之间的双射通常保留递归分解。

推论与应用

Catalan 数是递归组合、语法树、栈可排序排列和随机树分析的核心序列。

参考资料

• Richard P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999，Ch. 6, especially Ex. 6.19, Catalan interpretations。
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009，Ch. I, tree specifications and Catalan generating functions。