知识库
Catalan 数
LaTeX
$$C_n=\frac1{n+1}\binom{2n}{n},\qquad C_0=1:\quad 1,1,2,5,14,42,\ldots$$
递推
一个非空的合法括号串可以唯一地拆成 $(A)B$,$A,B$ 都是合法括号串。于是
LaTeX
$$C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}.$$
生成函数
右边是卷积,生成函数 把它变成乘法:$C(x)=\sum C_nx^n$ 满足
LaTeX
$$C(x)=1+xC(x)^2.$$
取在 $x=0$ 处解析的那个根:
LaTeX
$$C(x)=\frac{1-\sqrt{1-4x}}{2x}.$$
把 $\sqrt{1-4x}$ 按二项式级数展开就得到通项。奇点在 $x=1/4$,决定了增长率:
LaTeX
$$C_n\sim\frac{4^n}{\sqrt{\pi}\,n^{3/2}}.$$
在哪出现
合法括号串、满二叉树的形状、$n$ 个节点的二叉搜索树、用一个栈能实现的排列、凸多边形的三角剖分……都是 Catalan 数。算法题里很常见。
用到它的地方
- 知识库 生成函数
核对
这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。