小镇的电影院门口正在排队买票，票价 5 元。队伍里来了 2n 位观众：n 人手里攥着 5 元纸币，n 人拿着 10 元纸币。售票员的零钱盒一开始是空的，规则却很简单：无论队伍怎么排，钱箱必须随时都能找开零钱——来一位 10 元的观众，就得有零钱找给他 5 元。那么，这样的合法队伍一共有多少种排法？ 把 n=1、2、3 的情况一个个穷举，你会得到一串奇妙的数字：1、2、5、14、42、132……它们像变魔法一样，隔一段时间就出现在完全不同的场合：合法的括号序列数量、二叉树的形态数量、网格对角线上方的路径数量、多边形三角剖分的数量。这串数字就是大名鼎鼎的卡特兰数（Catalan numbers）。它表面上是个排队问题，实际上是一把“万能计数钥匙”——只要问题能拆成“前后两段独立子问题”，答案往往就是卡特兰数。本文就用这场售票窗口前的排队，带你把它从递推、通项公式、生成函数到各种应用一次看透。

岗位关联

对 AI 从业者而言，卡特兰数训练的是“把离散结构拆解为独立子问题”的组合分析能力，这正是算法设计、数据结构选型与面试攻防中最实用的数学直觉。

目录
  1. 可视化演示
  2. 2.1 数列的诞生
  3. 2.2 递推关系
  4. 2.3 通项公式
  5. 2.4 生成函数
  6. 2.5 格路径计数
  7. 2.6 经典应用
  8. 2.7 算法与工程
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

卡特兰数计数多种组合结构如括号匹配、二叉树与栈序列。本文详解卡特兰数的递推关系与通项公式、生成函数推导、与格路... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

卡特兰数的基：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

2.1 数列的诞生

回到电影院售票窗口。n=1 时只有两位观众，合法的队伍只有一种：拿 5 元的先买，售票员收下零钱，随后 10 元观众才能顺利买票。n=2 时稍微一试：拿 5 元的两位记为 A、B，拿 10 元的两位记为 a、b，合法的排法有“ABab“和”ABba“两种——但”AaBb”就不行，因为第二位 10 元观众来时售票员还没有零钱。继续数下去，n=3 有 5 种，n=4 有 14 种，n=5 有 42 种。这串数最早出现在欧拉研究多边形剖分的问题中，后来比利时数学家卡特兰（Eugène Charles Catalan）系统地研究了它，于是得名卡特兰数。

把前几项摆在一起：$C_0=1,\ C_1=1,\ C_2=2,\ C_3=5,\ C_4=14,\ C_5=42$。每一项都来自一个“组合学之母”的繁殖过程：排队问题、括号序列、树结构，全都指向同一个数列。它最让人震惊的是增长速度——看似温和的前几项后面，藏着指数级的爆发：$C_{10}=16796$，$C_{20}\approx 6.56\times 10^{10}$，$C_{30}\approx 3.82\times 10^{16}$。理解这个增长速度，对判断算法复杂度非常关键。

数列的诞生，就像售票窗口前排出的第一条队伍：看似随意，却暗藏秩序。这条队伍越长，合法排法增长得越迅猛，而它背后的计数规律，马上引出卡特兰数最核心的递推关系。

Cn∼4nn3/2π\displaystyle C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}
这个符号 $\sim$ 读作“渐近等于”，意思是当 n 足够大时，左边的数除以右边会无限接近 1。它能帮我们快速估计卡特兰数的数量级。
  1. 指数主项 $4^n$每增大一个 n，卡特兰数大约翻 4 倍。这解释了为什么它爆炸得这么快——每增加一对观众，排队方案几乎以四倍速度繁衍。
    4n\displaystyle 4^n
  2. 代数衰减因子 $n^{3/2}$分母上的 $n^{3/2}$ 压制了爆炸势头，让增长稍慢于纯 $4^n$，这也是格路径问题中边界约束带来的“抑制效应”。
    1n3/2\displaystyle \frac{1}{n^{3/2}}
  3. 常数 $\sqrt{\pi}$来自斯特林公式对阶乘的逼近——$n! \approx \sqrt{2\pi n}(n/e)^n$，是组合分析中反复出现的“老朋友”。
    π\displaystyle \sqrt{\pi}

2.2 递推关系

现在用售票员的视角重新观察队伍。假设有 $n+1$ 对观众（即 $n+1$ 个 5 元、$n+1$ 个 10 元），合法的队伍一定以一位 5 元观众开头——因为一开始零钱盒是空的，第一位绝不可能是 10 元观众。这位“开路人”买票后，零钱盒里多了 5 元。继续往后看，队伍会在某个时刻第一次回到“零钱盒清零”的状态：此时卖出的 5 元票和 10 元票数量相等，这一整段队伍在财务上“自给自足”了。

这个“第一个清零点”就是递推公式的钥匙。在它之前的 $2i$ 个位置里，除去开头的 5 元观众，剩下的 $2i-1$ 个位置构成一个规模为 $i-1$ 的合法子问题；而在它之后的 $2(n-i)$ 个位置，是另一个规模为 $n-i$ 的合法子问题。两段之间完全独立，互不干扰——就像电影院分成两个检票口，各排各的队。于是总数等于所有可能分割点下两段方案数的乘积之和：

这个递推关系不仅是计数工具，更是一种思维模板：如果一个问题能在“第一个归零点”处切成两个独立子问题，它的答案往往就是卡特兰数。售票员剪开的是队伍，数学家看到的是递归结构——这也是动态规划最原始的思想火花。

Cn+1=∑i=0nCi Cn−i,C0=1\displaystyle C_{n+1} = \sum_{i=0}^{n} C_i \, C_{n-i}, \qquad C_0 = 1
递推公式说：一个大问题的方案数，等于把它切成两段小问题后所有乘法的总和。这就像把一条长队从中间“剪开”，两段队伍各自成队后再拼接。
  1. 下标设计 $C_{n+1}$左边想求的是 $n+1$ 对观众时的合法队伍数，下标写作 $n+1$ 是为了让求和下标从 0 开始更整齐。
    Cn+1\displaystyle C_{n+1}
  2. 分割点 $i$$i$ 表示第一段子问题的大小——它从 0 一直取到 $n$，覆盖所有可能的“第一个清零点”位置。
    ∑i=0n\displaystyle \sum_{i=0}^{n}
  3. 乘法原理 $C_i\,C_{n-i}$第一段有 $C_i$ 种排法，第二段有 $C_{n-i}$ 种排法，两段组合起来就是乘积——好比左右两条队伍任意搭配。
    Ci×Cn−i\displaystyle C_i \times C_{n-i}
  4. 边界条件 $C_0=1$空队伍也是一种排法，它是整座递推大厦的地基；没有它，递推就无法启动。
    C0=1\displaystyle C_0 = 1

2.3 通项公式

有了递推关系，理论上可以一路算到任意项，但 $O(n^2)$ 的计算终究不够痛快。数学家们想知道：能不能给卡特兰数一个“一步到位”的显式公式？答案是肯定的，而且形式异常优美：把 $2n$ 个观众的每种排列都算一遍，再除以 $n+1$。为什么是 $n+1$？可以这样直观理解：在 $2n$ 个人的任意排列中，总存在某种“循环移位”把队伍变成合法队伍，而 $2n$ 个位置中恰好有 $n+1$ 个“合法起点”——于是总排列数 $\binom{2n}{n}$ 除以 $n+1$ 就得到合法排法数。

通项公式还有第二种等价形式，它揭示了一个更深刻的“反射原理”：所有排列中，非法的那部分经过一次“照镜子”式的翻转，恰好对应一类更容易计数的路径，从而可以相减消去。

通项公式就像售票窗口的“快捷通道”：不用一步一步递推，直接代入 n 就能算出答案。而减法形式的右边那一项，正是下一节生成函数和格路径要靠“镜子翻转”才能算清的部分。

Cn=1n+1(2nn)=(2nn)−(2nn−1)\displaystyle C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1}
组合数 $\binom{2n}{n}$ 读作“C 2n 取 n”，表示从 $2n$ 个观众里选出 n 个 5 元观众的位置。通项公式把“递推求和”压缩成了一个组合数表达式，是计算卡特兰数的首选公式。
  1. 组合数 $\binom{2n}{n}$$2n$ 个观众中任选 n 个位置放 5 元观众，其余放 10 元观众，总共有这么多种排列——不论合法与否。
    (2nn)\displaystyle \binom{2n}{n}
  2. 除以 $n+1$在 $2n$ 个排列中，平均每 $n+1$ 个只有 1 个合法，所以用总排列数除以 $n+1$ 即可“筛”出合法队伍。
    1n+1\displaystyle \frac{1}{n+1}
  3. 等价减法形式$\binom{2n}{n-1}$ 恰好是非法排列数。它等于“从 $2n$ 个位置选 $n-1$ 个 5 元观众位”的方案数，也是反射原理的直接产物。
    (2nn)−(2nn−1)\displaystyle \binom{2n}{n} - \binom{2n}{n-1}

2.4 生成函数

如果说通项公式是“快捷通道”，那么生成函数就是“时光胶囊”——它把整个卡特兰数列压缩进一个函数里，让代数运算替我们完成所有的计数推导。定义生成函数 $C(x)$ 为把数列 $C_n$ 作为系数装进 $x^n$ 的口袋：

这里 $x$ 只是一个形式占位符，我们并不关心它的具体数值，只关心展开后 $x^n$ 前面的系数是否恰好等于 $C_n$。神奇的事情在于：递推关系 $C_{n+1}=\sum C_i C_{n-i}$ 经过代数整理，恰好等价于一个关于 $C(x)$ 的二次方程——因为两个生成函数相乘时，$x^n$ 的系数正是两个数列的卷积。解这个二次方程，就得到了生成函数的闭式：

生成函数这一章看似抽象，实际上是把售票窗口前的“排队分割”翻译成了“多项式乘法”。它把离散的递推求和变成了连续的代数方程，这也正是组合数学研究中最优雅的跳板——从“数数”上升到“算函数”。

C(x)=∑n=0∞Cnxn=1+x+2x2+5x3+14x4+⋯\displaystyle C(x) = \sum_{n=0}^{\infty} C_n x^n = 1 + x + 2x^2 + 5x^3 + 14x^4 + \cdots
C(x)=1−1−4x2x\displaystyle C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}
生成函数把“无穷多个数的求和”变成“一个函数的四则运算”。解出闭式后，再用泰勒展开把 $\sqrt{1-4x}$ 展开成幂级数，系数就又回到卡特兰数，形成漂亮的闭环。
  1. 口袋构造 $\sum C_n x^n$把数列每一项放在 $x^n$ 的系数位置上，整个数列就装进了一个幂级数口袋。
    C(x)=∑n=0∞Cnxn\displaystyle C(x) = \sum_{n=0}^{\infty} C_n x^n
  2. 二次方程 $C = 1 + xC^2$递推关系经过整理变成 $C(x)=1+xC(x)^2$，其中 $xC^2$ 对应卷积求和——也就是前面“两段队伍相乘再相加”的代数化身。
    C(x)=1+x C(x)2\displaystyle C(x) = 1 + x\,C(x)^2
  3. 求根公式取负号把 $C$ 看作未知数解一元二次方程，得到两个根 $(1\pm\sqrt{1-4x})/(2x)$。因为 $C(0)=C_0=1$，而 $x=0$ 时取加号会发散，所以必须取减号。
    C(x)=1−1−4x2x\displaystyle C(x) = \frac{1 - \sqrt{1-4x}}{2x}

2.5 格路径计数

现在换个角度来看排队：把队伍状态画在网格纸上。横坐标 x 表示“到目前为止出现的 5 元观众人数”，纵坐标 y 表示“已经出现的 10 元观众人数”。队伍每前进一位，点就向右走一步（来 5 元观众）或向上走一步（来 10 元观众）。合法队伍要求任何时候 5 元观众人数不少于 10 元观众人数，也就是路径上每一点的 y 都不超过 x——对应网格中“路径不能越过主对角线 $y=x$”。

从 $(0,0)$ 出发到 $(n,n)$，总共要走 $2n$ 步，其中 n 步向右、n 步向上。没有任何限制时，路径总数是 $\binom{2n}{n}$。非法路径一定会在某个时刻第一次越过对角线（碰到 $y=x+1$）。把这条非法路径从第一次越线的点开始，对 $y=x+1$ 这条线做一次“镜面反射”，终点 $(n,n)$ 就会变成 $(n-1,n+1)$——恰好是从 $(0,0)$ 到 $(n-1,n+1)$ 的任意路径的终点。这个反射给出了非法路径与“到 $(n-1,n+1)$ 的路径”的一一对应：

格路径是卡特兰数最直观的“可视化语言”。售票窗口前的每一支合法队伍，都对应网格中一条贴着对角线安全爬行的路线；动画演示里的红色虚线，就是那条不能越过的“找零底线”。

Cn=(2nn)−(2nn−1)\displaystyle C_n = \binom{2n}{n} - \binom{2n}{n-1}
反射原理是一面神奇的镜子：它把“非法路径”整体翻折到另一类更容易数清的对象上，从而算出非法路径的数量。这也是通项公式减法形式的几何来源。
  1. 总路径数 $\binom{2n}{n}$从 $(0,0)$ 到 $(n,n)$，在 $2n$ 步中恰好选 n 步向右，其余 n 步向上，对应所有可能的队伍排列。
    (2nn)\displaystyle \binom{2n}{n}
  2. 非法路径的镜像终点非法路径第一次碰到 $y=x+1$ 后，把后续部分对这条线反射，终点从 $(n,n)$ 变成 $(n-1,n+1)$。
    (n,n)↦(n−1,n+1)\displaystyle (n,n) \mapsto (n-1,n+1)
  3. 非法路径计数从 $(0,0)$ 到 $(n-1,n+1)$ 的任意路径数为 $\binom{2n}{n-1}$（因为总共 $2n$ 步中选 $n-1$ 步向右），这就是被减掉的非法部分。
    (2nn−1)\displaystyle \binom{2n}{n-1}

2.6 经典应用

卡特兰数之所以成为组合数学的明星，是因为同一串数字反复出现在四个看似毫无关联的场景中。第一是括号匹配：把 5 元观众想象成左括号 “(“，10 元观众想象成右括号 ”)“，合法队伍恰好对应合法括号序列——比如 n=3 时有 ”((()))”、"(())()"、“(())()“ 等 5 种。第二是二叉树计数：n 个节点的不同二叉树形态数也是 $C_n$，因为一棵树可以被根节点分成左右两棵子树，左右子树大小相加为 $n-1$，恰好满足同一递推。第三是栈输出序列：n 个元素依次入栈，所有可能的合法出栈序列数为 $C_n$——入栈对应左括号，出栈对应右括号，栈空时不能出栈对应”括号不能先闭”。第四是多边形三角剖分：把一个凸 n 边形用不相交对角线切成三角形，剖分方式数也由卡特兰数给出。

这四个场景看起来天差地别，本质却都是“分割成两个独立子问题”的结构。以三角剖分为例，设 $T_n$ 为凸 n 边形的剖分数，固定一条边作为底边，它所属的三角形把多边形分成左右两块，于是又得到相同的递推。三角剖分有自己独特的通项变体：

售票窗口的队伍、编译器里的括号、数据结构里的栈、几何里的剖分——在卡特兰数的眼光下，它们是同一个故事的四个版本。识别出“能否分割成独立子问题”这个特征，就能一眼认出卡特兰数。

Tn=1n−1(2n−4n−2),n≥3\displaystyle T_n = \frac{1}{n-1}\binom{2n-4}{n-2}, \quad n \ge 3
这是卡特兰数通项公式的“下标平移版”：凸 n 边形的剖分数等于 $C_{n-2}$。比如三角形（n=3）剖分数为 1，四边形（n=4）剖分数为 2，五边形（n=5）剖分数为 5。
  1. 下标平移 $n-2$凸 n 边形的三角剖分数对应卡特兰数 $C_{n-2}$，因为多边形至少要 3 条边，形状比括号问题“少两个自由度”。
    Tn=Cn−2\displaystyle T_n = C_{n-2}
  2. 组合数替换把 $C_{n-2}$ 代入通项公式 $\frac{1}{(n-2)+1}\binom{2(n-2)}{n-2}$，化简得到 $\frac{1}{n-1}\binom{2n-4}{n-2}$。
    1(n−2)+1(2(n−2)n−2)\displaystyle \frac{1}{(n-2)+1}\binom{2(n-2)}{n-2}
  3. 验证小 nn=3 时 $\frac{1}{2}\binom{2}{1}=1$，三角形只有一种剖分；n=4 时 $\frac{1}{3}\binom{4}{2}=2$，四边形两条对角线对应两种剖分，完全正确。
    13(42)=2\displaystyle \frac{1}{3}\binom{4}{2} = 2

2.7 算法与工程

从数学回到工程，卡特兰数的价值在于：当我们在代码中遇到“计数合法结构”的问题时，它直接给出两条可落地的求解路线。第一条是动态规划：用数组 dp 模拟递推关系，从小到大依次计算。第二条是组合数公式：借助组合数 $\binom{2n}{n}$ 的递推定义，可以在 $O(n)$ 时间内精确算出单个卡特兰数，避开浮点误差。当 n 很大时还要配合取模运算（如模 $10^9+7$），防止整数溢出。动态规划便于理解，组合数公式适合大批量计算，两者配合即可覆盖绝大多数面试与工程场景。

伪代码视角下的动态规划递推式如下，$dp[i]$ 表示规模为 i 的问题的合法方案数：

从售票窗口的数学模型到编译器、数据库、深度学习的工程现场，卡特兰数的递推思想贯穿始终。掌握了它，你不只是记住了一串数字，而是掌握了一种“把大问题一分为二”的算法世界观。

dp[i]=∑j=0i−1dp[j]×dp[i−1−j],dp[0]=1\displaystyle dp[i] = \sum_{j=0}^{i-1} dp[j] \times dp[i-1-j], \qquad dp[0] = 1
这是全文递推公式的程序化版本：外层循环枚举规模 i，内层循环枚举分割点 j，累加所有左右子问题的乘积。时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。
  1. 数组语义 dp[i]$dp[i]$ 存放“规模为 i 的问题有多少种合法结构”，是递推公式 $C_i$ 的程序化身。
    dp[i]\displaystyle dp[i]
  2. 内层累加对每个分割点 $j$（从 0 到 $i-1$），左子问题规模为 $j$，右子问题规模为 $i-1-j$，两者方案数相乘后累加。
    ∑j=0i−1dp[j]×dp[i−1−j]\displaystyle \sum_{j=0}^{i-1} dp[j] \times dp[i-1-j]
  3. 初始化 dp[0]=1空结构算 1 种方案，作为整个递推的起点，对应卡特兰数的 $C_0=1$。
    dp[0]=1\displaystyle dp[0] = 1

AI 应用场景

场景 1：编译器与语法解析

阶段：数据预处理与语法解析

解决的问题：AI 大模型生成的代码、SQL 或逻辑表达式，必须先校验括号与作用域是否匹配。传统校验需要手写状态机，处理嵌套层级复杂且容易出错；利用卡特兰数可理解合法嵌套结构的总数，配合栈结构实现线性时间的合法性校验。

具体案例：在训练代码生成模型的评测阶段，系统需要判断模型输出的 Python 代码括号是否成对。工程师用“5 元观众=左括号、10 元观众=右括号”的映射，把括号序列校验转化为带约束的栈模拟，并与卡特兰数期望总数进行比对，快速过滤明显非法的生成结果。

场景 2：机器学习中的树结构模型

阶段：模型结构搜索与复杂度分析

解决的问题：决策树、随机森林、表达式树等树形结构的规模估算直接影响训练预算。传统做法是暴力枚举所有树形，计算量爆炸；利用卡特兰数可精确估计 n 个节点的树形态总数，帮助科学家判断是否值得做结构搜索。

具体案例：某团队在设计符号回归模型时，需要评估“最多 10 个内部节点的二叉树表达式有多少种可能结构”。他们用 $C_{10}=16796$ 快速估算搜索空间，发现完全可以穷举所有形态并做并行评估，从而放弃了遗传算法的复杂方案。

场景 3：算法竞赛与精准计数

阶段：算法设计与评测

解决的问题：在 AI 系统的排序、调度、路径规划评测中，常出现“输出序列必须满足某种先后约束”的计数问题。传统做法是回溯枚举，指数级超时；识别出问题的卡特兰数结构后，可直接用组合数公式 $O(n)$ 计算总数。

具体案例：某推荐系统需要统计所有满足“先入先处理”约束的任务调度方案数。工程师发现任务入队与出队恰好构成栈模型，直接套用卡特兰数公式计算总数，并与蒙特卡洛模拟结果交叉验证，将耗时从分钟级降到毫秒级。

Python 演示

python47 行
# -*- coding: utf-8 -*-"""卡特兰数三种计算方法与括号序列生成""" def catalan_dp(n):    """动态规划: O(n^2), 返回 C_0..C_n 列表"""    dp = [0] * (n + 1)    dp[0] = 1    for i in range(1, n + 1):        for j in range(i):            dp[i] += dp[j] * dp[i - 1 - j]    return dp def catalan_comb(n):    """组合数通项公式: O(n), 返回单个 C_n(int)"""    res = 1    for k in range(1, n + 1):        res = res * (n + k) // k    return res // (n + 1) def catalan_comb_all(N):    """用公式逐个计算 C_0..C_N"""    return [catalan_comb(i) for i in range(N + 1)] def gen_brackets(n):    """回溯生成 n 对括号的全部合法序列"""    out = []    def dfs(s, left, right):        if len(s) == 2 * n:            out.append(s)            return        if left < n:            dfs(s + '(', left + 1, right)        if right < left:            dfs(s + ')', left, right + 1)    dfs('', 0, 0)    return out if __name__ == '__main__':    N = 8    vals_dp = catalan_dp(N)    vals_cb = catalan_comb_all(N)    assert vals_dp == vals_cb, '两种方法结果不一致!'    print('C_0..C_%d:' % N)    print(vals_dp)    print('C_4 =', vals_dp[4], ' 合法括号序列:')    for b in gen_brackets(4):        print(b)
目的：用三种独立方法——递推 DP、组合数公式、回溯枚举——计算并验证卡特兰数，同时输出 n=4 时的全部 14 个合法括号序列，直观对照数学结论。
  1. dp[0] = 1初始化空问题方案数为 1，这是整个递推的地基；没有它，内层循环无从累加。
  2. dp[i] += dp[j] * dp[i - 1 - j]内层循环枚举分割点 j，左子问题规模 j、右子问题规模 i-1-j，乘积累加，对应“队伍从中间剪开”的乘法原理。
  3. res = res * (n + k) // k用连乘计算组合数 $\binom{2n}{n}$，每一步先乘后除保证精确整除，避免浮点误差。
  4. return res // (n + 1)组合数算出后再除以 n+1，得到通项公式 $C_n = \frac{1}{n+1}\binom{2n}{n}$。
  5. if right < left:回溯生成括号时，只有右括号数小于左括号数才能加右括号，对应“10 元观众必须有零钱可找”的约束。
  6. assert vals_dp == vals_cb用断言验证递推与通项公式两种方法结果一致，这是工程中交叉验证的典型手法。

常见误区

误区我背过卡特兰数前几项，看到括号题就套答案。但换到二叉树、多边形上完全想不到它，觉得那是另一套知识体系太复杂了。

正解卡特兰数的本质不是“括号”，而是“把一个问题在第一个平衡点切成两个独立子问题”的递归结构。括号、二叉树、栈序列、三角剖分全是这个结构的化身。遇到新问题时，应该问“能否在某个点分割成两个独立子问题”，而不是问“它像不像括号”。

为何常见：教材通常先讲括号匹配，因为它最直观；但学习者只记住了表面形式，没有提炼出背后的递推结构，所以无法迁移到其他场景。

误区我用 `math.factorial(2*n) // math.factorial(n)2` 算组合数，再除以 n+1，有时结果差 1 或者直接报错，以为是库的问题。

正解Python 的整数除法在整除时是精确的，问题出在把中间量转成浮点数或使用 math.comb 后忘记用整数除法。正确做法是全程保持整数运算：先算出组合数，再用 // (n+1) 整除，或直接用连乘递推保证每一步都能整除。

为何常见：许多语言里除法默认产生浮点数，初学者从 C/Java 带来的习惯让中间结果失去精度；而卡特兰数的组合数公式涉及大量整除关系，必须全程整数运算。

误区我认为合法路径不能碰到 $y=x$ 这条线，所以画路径时绕开对角线，结果发现合法的队列明明可以在某个时刻 5 元、10 元人数相等（比如队伍第一人后零钱清零），我就懵了。

正解“不越过”（$y \le x$）和“不碰”（$y < x$）是不同约束。卡特兰数对应的是允许触碰但不允许越过——队伍在平衡点就是“碰线”。如果要求严格不碰，那对应的是另一个数列。反射原理中的镜像线是 $y=x+1$ 而不是 $y=x$，正是为了区分这两种情况。

为何常见：中文里“不越过”容易被口语化理解为“不碰”，再加上图示中常用红色虚线强调对角线，学习者就容易把约束条件记反。

误区我觉得递推公式 $C_{n+1}=\sum C_iC_{n-i}$ 只是数学玩具，算到 n=20 就慢得不行，实际项目根本不会用到这么“笨”的方法。

正解递推的价值不只是“算数字”，而是提供了一种问题建模方式。工程里很多结构（如神经网络表达式树、编译器 AST）的计数需要逐项构造，递推配合记忆化天然适合；而且 $O(n^2)$ 的复杂度在 n 不大时完全可用，配合取模运算还能扩展到极大 n。真正要注意的是根据场景选择 DP 还是组合数公式，而不是一味否定递推。

为何常见：学习者只看到递推算法逐层求和的笨拙，忽略了递推本身就是动态规划的核心思想，更没有意识到精度与溢出问题才是工程中的主要矛盾。

面试题

Q1. 卡特兰数 $C_3$ 的值是多少？

单选题 · easy

  • A.3
  • B.4
  • C.5← 正确答案
  • D.6

答案：C。卡特兰数前几项为 $1,1,2,5,14,42$，所以 $C_3=5$。它对应 3 对括号的合法序列数，也对应 3 个节点的二叉树形态数。可以用递推 $C_3=C_0C_2+C_1C_1+C_2C_0=2+1+2=5$ 验证。

Q2. 卡特兰数的通项公式是以下哪一个？

单选题 · easy

  • A.$\displaystyle \frac{1}{n+1}\binom{2n}{n}$← 正确答案
  • B.$\displaystyle \frac{1}{n}\binom{2n}{n}$
  • C.$\displaystyle \binom{2n}{n+1}$
  • D.$\displaystyle \frac{2^n}{n+1}$

答案：A。通项公式为 $C_n = \frac{1}{n+1}\binom{2n}{n}$。B 错在分母应为 n+1 而非 n；C 是另一类组合数；D 的 $2^n$ 不满足 n=3 时结果为 5。

Q3. 3 对括号能组成多少种合法括号序列？

单选题 · easy

  • A.3
  • B.4
  • C.5← 正确答案
  • D.6

答案：C。合法括号序列数就是卡特兰数 $C_3=5$，即：((()))、(()())、(())()、()(())、()()()。每一种都对应一条不越过对角线的格路径。

Q4. 有 4 个节点的不同二叉树共有多少种形态？

单选题 · mid

  • A.5
  • B.8
  • C.12
  • D.14← 正确答案

答案：D。n 个节点的二叉树形态数为 $C_n$，所以 4 个节点对应 $C_4=14$。根节点把树分成左子树（0~3 个节点）和右子树（3~0 个节点），各项乘积之和即递推公式。

Q5. 关于卡特兰数的递推关系 $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$，下列说法正确的有？

多选题 · mid

  • A.边界条件 $C_0=1$← 正确答案
  • B.它来自“第一个平衡点分割成两个独立子问题”← 正确答案
  • C.它与通项公式计算出的结果完全一致← 正确答案
  • D.它只能用于 n=3 以内的计算

答案：ABC。递推公式要求 $C_0=1$ 作为地基（A 对）；它的推导核心就是把问题在第一个归零点切成前后两段独立子问题（B 对）；递推与通项公式是同一数列的两种表达，结果必然一致（C 对）。D 显然错误，递推对任意非负整数 n 都成立。

Q6. 以下哪些结构的计数与卡特兰数有关？

多选题 · mid

  • A.n 对合法括号序列← 正确答案
  • B.凸多边形的三角剖分← 正确答案
  • C.n 个元素通过一个栈得到的合法输出序列← 正确答案
  • D.斐波那契数列的第 n 项

答案：ABC。括号匹配（A）、三角剖分（B）、栈输出序列（C）都满足“分割成独立子问题”的递归结构，计数均为卡特兰数。斐波那契数列是另一类递推，与卡特兰数无关。

Q7. 在格路径反射原理中，一条非法路径从首次越过 $y=x+1$ 的点开始反射后，其终点 $(n,n)$ 会变成什么？

单选题 · hard

  • A.$(n-1, n+1)$← 正确答案
  • B.$(n+1, n-1)$
  • C.$(n, n-1)$
  • D.$(2n, 0)$

答案：A。非法路径首次触到 $y=x+1$ 后，把后续路径对该直线做镜像翻转，终点从 $(n,n)$ 变为 $(n-1,n+1)$。从 $(0,0)$ 到 $(n-1,n+1)$ 的路径数为 $\binom{2n}{n-1}$，这正是非法路径数，也是通项公式中被减掉的部分。

Q8. 凸七边形的三角剖分共有多少种？

单选题 · hard

  • A.14
  • B.42← 正确答案
  • C.132
  • D.429

答案：B。凸 n 边形的三角剖分数为 $C_{n-2}$，所以凸七边形对应 $C_5=42$。用平移版通项公式 $\frac{1}{n-1}\binom{2n-4}{n-2}$ 代入 $n=7$：$\frac{1}{6}\binom{10}{5}=42$。

Q9. 关于生成函数 $C(x)=1+xC(x)^2$，下列说法正确的有？

多选题 · hard

  • A.它的解为 $\displaystyle \frac{1-\sqrt{1-4x}}{2x}$← 正确答案
  • B.展开后 $x^n$ 的系数是卡特兰数← 正确答案
  • C.它来源于递推关系的卷积结构← 正确答案
  • D.$x=0$ 时该函数取加号的根也满足 $C(0)=1$

答案：ABC。解二次方程得到两个根，取减号才满足 $C(0)=1$，所以 A 对、D 错；生成函数展开系数正是卡特兰数列（B 对）；$xC^2$ 来自两个数列的卷积，对应递推中的乘积求和（C 对）。

Q10. $C_{10}$（卡特兰数第 10 项）等于多少？

单选题 · extreme

  • A.4862
  • B.16796← 正确答案
  • C.58786
  • D.429

答案：B。用通项公式计算：$C_{10}=\frac{1}{11}\binom{20}{10}=\frac{184756}{11}=16796$。也可以用渐进公式 $\frac{4^{10}}{10^{3/2}\sqrt{\pi}} \approx 16796$ 验证。A 是 $C_8$，C 是 $C_{11}$，D 是 $C_7$。