Catalan · C(2n,n)/(n+1)

Catalan 数

$1,\, 1,\, 2,\, 5,\, 14,\, 42,\, 132,\, 429,\, \dots$ 这列数在四类看上去无关的问题里同时冒出来： $n$ 对括号能排出多少个合法匹配串、从 $(0,0)$ 到 $(n,n)$ 且不越过对角线的单调格路有多少条、 $n$ 个节点能长出多少种二叉树形状、凸 $n+2$ 边形有多少种三角剖分。四个问题数的是同一个量，记作 Catalan 数 $C_n$ 。本页给出把它们连起来的对应、由反射法得到的闭式，以及按首个括号闭合位置分类得到的卷积递推。

1 · 数着同一列数的四类对象

四类对象之所以给出同一列数，不是巧合，而是每两类之间都能写出显式的一一对应，构造见双射证明与格路模型。

对象	参数取法	与括号串的对应
合法括号串	括号对数 $n$	$n = 3$ 的五个：`((()))`、`(()())`、`(())()`、`()(())`、`()()()`
单调格路	步数 $2n$	左括号记作一步向右，右括号记作一步向上，不越过对角线即合法
二叉树形状	节点数 $n$	前序遍历中进入一棵子树写左括号，退出时写右括号
凸多边形三角剖分	边数 $n+2$	固定一条边作根，剖分出的三角形对应二叉树的节点

第三行的对应给了 Catalan 数在解析里的位置：一个串的派生树棵数按同一列数增长，见歧义：一个串几棵树。

2 · 反射法与闭式

reflection · C(2n, n) − C(2n, n+1)

把左括号记作上升一步、右括号记作下降一步，长 $2n$ 的括号串就成了一条折线。合法等价于折线全程不低于 $0$ 且终点回到 $0$ ，这样的折线称为 Dyck 路径（Dyck path）；它与格路模型只差一次坐标旋转。放宽「不低于 $0$ 」这一条，升降各 $n$ 步的折线共 $\binom{2n}{n}$ 条，问题随即化为从中减去越界的那些。

定理 2.1 升降各 $n$ 步、且在某处跌到 $-1$ 的折线恰有 $\binom{2n}{n+1}$ 条。

证明设某条越界折线首次跌到 $-1$ 发生在第 $p$ 步之后，把第 $p$ 步之后的每一步反号，几何上即把这一段沿水平线 $y = -1$ 作镜像。前 $p$ 步升 $u$ 降 $d$ 且 $u - d = -1$ ；反号后总升 $u + (n - d)$ 步、总降 $d + (n - u)$ 步，两者之差恒为 $-2$ ，终点固定落在 $-2$ ，即升 $n-1$ 步、降 $n+1$ 步的一条折线。反过来，任何升 $n-1$ 降 $n+1$ 的折线终点在 $-2$ ，必在某处首次跌到 $-1$ ，同样的反号操作把它折回一条越界折线，且首次触碰的位置不变。两个方向互逆，映射为双射，越界折线数等于升 $n-1$ 降 $n+1$ 的折线总数 $\binom{2n}{n+1}$ 。∎

两式相减，再把阶乘展开约掉公因子，即得闭式：

C_n = \binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}

图 2-1 · 升降各

n

步的全部折线按是否越界分成两列。可调

n

观察两列条数，点选右列任一条越界折线，看它在首次触碰之后沿

-1

线镜像成的那条落点为

-2

的折线。

反射法有一处只在写代码时才浮出来的边界：镜像区间的左端是开的。首次跌到 $-1$ 的那一步本身不反号，只反号它之后的部分。把这一步也算进去， $n = 4$ 的 $56$ 条越界折线只映成 $35$ 个像，映射不再是单射， $\binom{2n}{n+1}$ 这个计数当场垮掉。核心模块的 firstDip 因此返回 1 基的步序号，reflect 从下标 $p$ 起翻转，两处的开闭必须配套。

枚举侧还有一处实测：本页的 lab 按合法性递归生成，而不是枚举全部 $2^{2n}$ 个 01 串再筛。 $n = 13$ 时筛法单次已在 1 秒上下（两次计时 964 与 1502 毫秒）， $n = 15$ 涨到 18.5 与 25.9 秒；递归生成同两档只要 325–354 毫秒与 4.7–5.0 秒（Node v26）。差距的来源是 $2^{30} \approx 1.07 \times 10^9$ 条候选里只有 $9694845$ 条合法，筛法九成九的功夫花在必然作废的分支上。lab 据此把 $n$ 限到 $7$ ，每列只渲染前 $200$ 条。

3 · 卷积递推与生成函数

C(n+1) = Σᵢ C(i)·C(n−i)

换一种分类：合法串的首个左括号总在某处闭合，于是每个非空合法串唯一地写成「左括号 $+$ 内层 $+$ 右括号 $+$ 外层」，内层与外层各自又是更短的合法串。设内层有 $i$ 对括号，外层就有 $n - i$ 对，两段互不牵连，该类共 $C_i C_{n-i}$ 个。让 $i$ 取遍 $0$ 到 $n$ ：

C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}, \qquad C_0 = 1

图 3-1 · 全部

C_n

个合法串按首个左括号在哪里闭合分成

n

类。可调

n

并点击表中任一行，只看该类的串，深色标出首个左括号与它的配对括号。

把序列装进形式幂级数 $C(x) = \sum_{n \ge 0} C_n x^n$ ，上式右端的卷积恰好是 $C(x)^2$ 的系数，整条递推就读作一个二次方程 $C(x) = 1 + x\,C(x)^2$ 。取在 $x = 0$ 处有限的那支解得 $C(x) = \dfrac{1 - \sqrt{1-4x}}{2x}$ ，再按广义二项式定理展开根式， $x^n$ 的系数正好是 $\frac{1}{n+1}\binom{2n}{n}$ ，与 §2 的闭式对上。这条路线的一般做法见生成函数。

4 · 增长量级与双精度的失效点

由 Stirling 公式可得 $C_n \sim 4^n / (n^{3/2}\sqrt{\pi})$ （推导见渐近估计）：主项按 $4^n$ 走，多项式因子只压掉一点。这个量级决定了双精度能撑到哪里。

警示 · 闭式 catalan 与卷积递推 catalanDP 在 $n \le 30$ 上逐项相同， $n = 31$ 起各错各的。精确值 $C_{31} = 14544636039226909$ 已越过 $2^{53} - 1$ ：catalanDP 实测给出 14544636039226908，catalan 走 $\binom{2n}{n}/(n+1)$ 实测给出 14544636039226906。更难察觉的是两者并不总是分头错， $n = 33$ 时它们一致给出 212336130412243100，而精确值是 212336130412243110。所以「闭式与递推相等」只在 $n \le 30$ 上算得上 oracle，本页测试正卡在这一档；再往上要换 BigInt。

5 · 参考文献

Catalan number. Wikipedia. Catalan 数的多种组合解释、闭式、递推与生成函数。https://en.wikipedia.org/wiki/Catalan_number
Dyck language. Wikipedia. Dyck 语言与合法括号串的形式定义。https://en.wikipedia.org/wiki/Dyck_language
Bijective proof. Wikipedia. 双射证明的一般套路，反射法是其中一例。https://en.wikipedia.org/wiki/Bijective_proof
Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press. 收录两百余种由 Catalan 数计数的对象及其相互对应。