Catalan 数 | Codeboy's Blog

形式陈述

Catalan 数由二项式系数定义为

C_n=\frac1{n+1}\binom{2n}{n} =\binom{2n}{n}-\binom{2n}{n+1}, \qquad n\ge0. \tag{1}

下面证明它计数半长为 $n$ 的 Dyck 路：由 $n$ 个上步 $U=(1,1)$ 和 $n$ 个下步 $D=(1,-1)$ 组成，从 $(0,0)$ 到 $(2n,0)$ ，并且每一步之后的高度都非负。空路径计作半长零的一条路径。

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

C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i}. \tag{2}

普通生成函数 $C(z)=\sum_{n\ge0}C_nz^n$ 是常数项为一的唯一形式解

C(z)=1+zC(z)^2. \tag{3}

在有理系数形式级数中，

C(z)=\frac{1-\sqrt{1-4z}}{2z}, \tag{4}

其中平方根指常数项为一的形式平方根，除以 $z$ 表示把可被 $z$ 整除的分子向前移一阶。形式等式不预设解析收敛。

本页还从精确式推出

\boxed{ C_n=\frac{4^n}{\sqrt\pi\,n^{3/2}} \left(1-\frac9{8n}+O(n^{-2})\right) } \qquad(n\to\infty). \tag{5}

指数尺度、幂次、常数与首个相对修正项将在同一次计算中出现。

直觉

首次返回用于把合法路径拆成两个独立的合法部件；首次越界用于把不合法路径映成一类容易计数的无约束路径。两个“首次”都保证切割位置唯一，因此各自的逆操作明确。

生成函数压缩前一种分解，把两部件的卷积变成平方。反射则直接给出二项式之差。Lagrange 反演从同一个形式方程出发再次提取系数，于是递归、双射和代数三条推导可以交叉核对。

上图把半长四的合法路径按首次返回拆成 U、P、D、Q；下图保留坏路径的前三步，将首次到达负一之后的蓝色后缀反射为红色虚线，终点从零变为负二。

上图的 $P$ 在高度一处起步，整体下移后才是半长一的 Dyck 路； $Q$ 的半长为二。下图横坐标都是实际步数，实线后缀 $UUD$ 与虚线后缀 $DDU$ 关于 $y=-1$ 对称，前三步完全重合。

例子与边界

半长三的五条路径

把 $U$ 写成左括号， $D$ 写成右括号，Dyck 条件就是每个前缀的左括号数不少于右括号数。非空合法串唯一写成

(\ P\ )\ Q,

其中首个左括号与所显示的右括号匹配。半长三时，按 $P$ 的半长 $i$ 分类：

$i$	$P$ 的选择数	$Q$ 的选择数	完整括号串
$0$	$C_0=1$	$C_2=2$	`()(())`、`()()()`
$1$	$C_1=1$	$C_1=1$	`(())()`
$2$	$C_2=2$	$C_0=1$	`(()())`、`((()))`

因此 $C_3=2+1+2=5$ 。再由递推，

C_4=C_0C_3+C_1C_2+C_2C_1+C_3C_0 =5+2+2+5=14.

前十一项为

C_0,\ldots,C_{10} =1,1,2,5,14,42,132,429,1430,4862,16796.

只要求括号总数相等不够。())(() 对应 $UDDUUD$ ，高度依次为

0,1,0,-1,0,1,0.

它在第三步首次跌到 $-1$ 。反射此后的后缀，将最后三个步 $UUD$ 换成 $DDU$ ，得到 $UDDDDU$ ，高度为

0,1,0,-1,-2,-3,-2.

新路径终点为 $-2$ ，其两个上步、四个下步正好属于反射证明中要计数的路径族。再次在第一次到达 $-1$ 后反射，就恢复原坏路径。

树和多边形的规模约定

$C_n$ 也计数有根、无标号、左右次序固定的平面满二叉树，规模为 $n$ 个内部节点。每个内部节点恰有两个孩子，所以总边数既为 $2n$ ，也为“内部节点数加叶子数减一”；叶子数因而为 $n+1$ 。

空规模对应一片叶子。非叶根的左右子树各有 $i$ 和 $n-1-i$ 个内部节点，重新得到同一递推。去掉左右次序或加入标号会改变计数对象，不能继续套用同一 $C_n$ 。

对于凸 $(n+2)$ 边形的三角剖分， $n\ge1$ ，固定一条边，考察唯一贴着这条边的三角形；其第三个顶点把其余部分分成左右两个更小区域，同样给出卷积。空区域按一计数，从而得到 $C_n$ 。例如六边形有 $C_4=14$ 种三角剖分。其他 Catalan 解释也须明确保持规模与递归分解的双射，不能仅凭前几项相同就认定为同一计数。

推论与应用

首次返回证明卷积

先用 $D_n$ 表示半长为 $n$ 的 Dyck 路数量，暂不假设其闭式。 $D_0=1$ 。一条半长为 $n+1$ 的非空路径，首步必为 $U$ 。设它第一次回到高度零发生在第 $2i+2$ 步。

在首个 $U$ 与这次返回的 $D$ 之间，路径高度始终至少为一。把中间部分整体下移一格，就得到半长 $i$ 的 Dyck 路 $P$ ；返回之后的部分是半长 $n-i$ 的 Dyck 路 $Q$ 。因此原路径唯一写成

U\,P\,D\,Q.

这里 $P$ 在原图中从高度一开始。反过来，任选这样的 $P,Q$ ，把 $P$ 上移一格再加上外层 $U,D$ ，其高度在闭合前严格为正，所以第一次返回恰在指定位置。拆分与重组互为逆，故

D_{n+1}=\sum_{i=0}^{n}D_iD_{n-i}.

下面的反射证明将识别 $D_n=C_n$ ，从而完成 (2)。

首次越界反射证明闭式

先计数所有从 $(0,0)$ 到 $(2n,0)$ 的上、下步路径：选择 $n$ 个上步位置，共有 $\binom{2n}{n}$ 条。

若路径不是 Dyck 路，它一定首次到达高度 $-1$ 。保留此前的路径及该首次到达点，把此后整个后缀关于直线 $y=-1$ 反射。这等价于交换后缀中的每个 $U,D$ ，使原终点高度零变成 $-2$ 。因此新路径有 $n-1$ 个上步和 $n+1$ 个下步。

反之，任何从高度零到高度 $-2$ 的这种路径都必先经过 $-1$ 。在它首次到达 $-1$ 后反射后缀，得到一条终点为零、但曾到达 $-1$ 的坏路径。第一次到达点之前的部分不变，所以两次反射的切割位置相同，确实互为逆。

坏路径数故为 $\binom{2n}{n-1}$ ，于是

D_n=\binom{2n}{n}-\binom{2n}{n-1} =\left(1-\frac{n}{n+1}\right)\binom{2n}{n} =C_n.

当 $n=0$ 时单独数空路径即得一；也可约定超出范围的二项式系数为零。整数性由这份实际计数直接保证，不需要先解释为何除以 $n+1$ 一定整除。

唯一形式解与反演核对

由递推逐系数求和，(2) 等价于 $C=1+zC^2$ 。反过来，在任意交换含幺环中，方程先强制常数项为一，再由次数 $n$ 的方程唯一决定下一项；右侧只用此前系数。故形式解的存在唯一性不依赖除法，整系数解也可映入任意这样的系数环。

在 $\mathbb Q\llbracket z\rrbracket$ 中，令 $S^2=1-4z$ 、 $S(0)=1$ 。逐项求 $S$ 时，新系数前的系数为二，因而可逆，给出唯一形式平方根。 $1-S$ 的常数项为零，式 (4) 是合法形式级数，并满足原方程。另一代数表达式 $(1+S)/(2z)$ 含有 $z^{-1}$ 项，不是所求幂级数。

应用Lagrange 反演时，先令

T=C-1,\qquad T=z(1+T)^2.

对 $n\ge1$ ，

[z^n]C=[z^n]T =\frac1n[u^{n-1}](1+u)^{2n} =\frac1n\binom{2n}{n-1} =\frac1{n+1}\binom{2n}{n}.

$T=C-1$ 只删去常数项，正次系数的下标没有移动。例如 $[z^4]T=14$ 。进一步取平方，

[z^4]T^2=\frac24[u^2](1+u)^8 =\frac12\binom82=14,

也与 $T=z+2z^2+5z^3+14z^4+\cdots$ 的卷积系数 $1\cdot5+2\cdot2+5\cdot1=14$ 一致。

渐近修正中的两个来源

使用带余项的对数 Stirling 展开，

\log n! =\left(n+\frac12\right)\log n-n +\frac12\log(2\pi)+\frac1{12n}+O(n^{-3}).

对正整数 $n$ ，截断余项的绝对值可由下一项 $1/(360n^3)$ 控制。把 $(2n)!$ 与两个 $n!$ 的展开相减，得到

\log\binom{2n}{n} =n\log4-\frac12\log(\pi n) -\frac1{8n}+O(n^{-3}).

其中 $1/(24n)-2/(12n)=-1/(8n)$ 。取指数时，二阶项贡献至多 $O(n^{-2})$ ，故

\binom{2n}{n} =\frac{4^n}{\sqrt{\pi n}} \left(1-\frac1{8n}+O(n^{-2})\right).

再用

\frac1{n+1} =\frac1n\left(1-\frac1n+O(n^{-2})\right),

便得到 (5)。修正系数 $-9/8$ 由中央二项式系数的 $-1/8$ 与除数 $n+1$ 的 $-1$ 相加而来。只用最粗的 Stirling 等价式无法恢复它。 Euler–Maclaurin公式解释这些对数求和修正及积分余项的来源；其中的 $\sqrt{2\pi}$ 常数仍需独立确定，不能仅靠形式端点修正猜出。

公式还给出 $C_n^{1/n}\to4$ ，所以解析生成函数的收敛半径恰为 $1/4$ 。奇点分析从式 (4) 的平方根奇点独立解释同一个 $4^n n^{-3/2}/\sqrt\pi$ 主项；本页从精确阶乘比出发，进一步计算首个相对修正。

参考资料

Alexander Postnikov 课程、Andrew Lin 记录，MIT 18.212，2019：Lecture 1, p. 3, Proposition 8 与 Lecture 2, p. 2, Theorem 4 的反射证明。
Ira M. Gessel, “Lagrange inversion”, 2016, §2.3, pp. 5–6：从 $C-1$ 的隐式方程提取 Catalan 系数。
NIST Digital Library of Mathematical Functions, §5.11(i), Eq. 5.11.1 与 §5.11(ii)：对数 Gamma 的 Stirling 展开及正实轴余项界；本页据此展开阶乘比。

形式陈述 ​

半长三的五条路径 ​

树和多边形的规模约定 ​

首次返回证明卷积 ​

首次越界反射证明闭式 ​

唯一形式解与反演核对 ​

渐近修正中的两个来源 ​

反向链接