CC++ & Algorithm

卡特兰数的推导与应用

极难2
语言版本：通用
概述：卡特兰数是一类在多种组合结构中出现的数列，如括号匹配、二叉树计数等，可以用递推或公式计算。

卡特兰数：从数括号到解游戏的神奇数列

你有没有想过这样的问题：

  • 妈妈给你5元零花钱，你想买3元的面包和2元的牛奶，有多少种不同的付钱顺序（比如先付面包再付牛奶，或者先付牛奶再付面包）？
  • 你和同学玩“石头剪刀布”的升级版——谁先赢到2局谁获胜，比赛过程中两人的胜负记录有多少种不同的可能？
  • 用4个相同的正方形拼成“俄罗斯方块”中的某种形状，有多少种不同的拼法？

这些看似毫不相关的问题，答案竟然都指向同一个数列：卡特兰数（Catalan numbers）。它就像数学界的“隐形衣”，藏在一大堆奇妙的结构里。今天我们就来揭开它的面纱，看看它如何从括号匹配、二叉树形状这些场景中诞生，又如何用代码算出来。

1. 一列神奇的数字

先看一个数列：
1, 1, 2, 5, 14, 42, 132, 429, 1430, ...

这串数字叫卡特兰数，以比利时数学家欧仁·卡特兰的名字命名。它像魔术师一样，经常出现在你意想不到的地方：

  • 括号匹配：有n对括号，能组成多少种合法的括号序列？
    比如2对括号，只有 ()() 和 (()) 两种。n=3时是5种（后面会看到）。
  • 二叉树形状：用n个相同的节点（节点没有编号），能构造多少种不同形状的二叉树？
    比如1个节点只有1种，2个节点有2种，3个节点有5种。
  • 网格路径：在一个n×n的方格中，从左上角走到右下角，每次只能向右或向下，且不能越过对角线（沿着对角线方向可以走但不超过），有多少种走法？
    比如2×2网格，有2种合法路径。
  • 凸多边形三角剖分：一个凸n+2边形，用不相交的对角线分割成三角形，有多少种分法？
    比如四边形（4条边，n=2）有2种分法（连一条对角线即可，两种对角线选一种）。

你可能已经发现：这些问题的答案都是卡特兰数！它们就像同一个灵魂住进了不同的身体。

2. 卡特兰数的定义

卡特兰数通常记为 CnC_n（或者 Catalan(n)）。它有两种常用的定义方式：递推公式和通项公式。

递推公式（适合计算机计算）

C0=1Cn+1=∑i=0nCi⋅Cn−i(n≥0)\begin{aligned} C_0 &= 1 \\ C_{n+1} &= \sum_{i=0}^{n} C_i \cdot C_{n-i} \quad (n \ge 0) \end{aligned}

这个公式的意思：要算第n+1个卡特兰数，需要把前面所有“分解”的情况加起来。后面我们会用括号匹配来解释为什么这样加。

通项公式（适合手算和数学推导）

Cn=1n+1(2nn)=(2n)!n!(n+1)!C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{n! (n+1)!}

其中 (2nn)\binom{2n}{n} 是组合数，表示从2n个位置中选n个的方法数。这个公式可以直接算出任意n的值。

头几个卡特兰数速查表

n012345678910
C_n112514421324291430486216796

注意：C_0 = 1 很有用，比如0对括号有一种合法序列（就是空串），0个节点有一种二叉树（空树）。

3. 推导：从括号匹配说起（为什么是这些数字？）

n对括号的合法序列是什么意思？就是每个左括号（(）都有一个右括号（)）与之配对，并且从左往右看，任何时候已出现的左括号数量都要大于等于已出现的右括号数量。比如 ()) 就不合法，因为读到第三个字符时，右括号比左括号多了一个。

3.1 暴力枚举的思路

如果我们用计算机枚举所有可能的由n个(和n个)组成的序列，总共有 (2nn)\binom{2n}{n} 种（从2n个位置里选n个放左括号）。比如n=2，一共有6种排列：(()), ()(), )((), ())(, ))((, )()(。其中只有前两个是合法的。
卡特兰数就是合法序列的数量。

3.2 用递推公式理解

假设我们有一对最外层的括号：第一个左括号一定存在，它匹配的右括号会把整个序列分成两部分：

  • 括号内部分（中间的东西）
  • 括号外部分（右边剩下的）

比如 ( ( ) ) ( )，最外层左括号是第一个字符，它与哪个右括号配对？如果配对的是最后一个右括号，那么里面是 ( )，外面是 ( )。如果配对的是第四个右括号（即 ( ( ) ) 中的最后一个），那么里面是 ( )，外面是空。

更一般地，设第一个左括号匹配的第k个右括号（假设左括号位置为0，右括号位置为2k+1？），那么它里面必须有k对括号，外面有n-k-1对括号。所以合法序列数满足：

Cn=∑k=0n−1Ck⋅Cn−1−kC_n = \sum_{k=0}^{n-1} C_k \cdot C_{n-1-k}

这正好是递推公式（因为定义里 C0=1C_0=1）。比如n=3，C3=C0C2+C1C1+C2C0=1×2+1×1+2×1=5C_3 = C_0C_2 + C_1C_1 + C_2C_0 = 1\times2 + 1\times1 + 2\times1 = 5。

3.3 用反射法推导通项公式（简单的数学魔法）

我们想从所有 (2nn)\binom{2n}{n} 种序列中，去掉非法的。非法序列的特征是：存在某个前缀，右括号数量比左括号多1。可以证明，非法序列的个数正好等于 (2nn−1)\binom{2n}{n-1}。
怎么证明？有一种巧妙的“反射法”：
把每个非法序列中第一次出现右括号多于左括号的位置（比如从开头到那个位置，右括号比左括号多1个），然后把这个位置之后的所有括号左右互换（左变右，右变左），会得到一个由 n+1 个左括号和 n-1 个右括号组成的序列。反过来，任何一个这样的序列也能唯一对应一个非法序列。所以非法序列数 = 从2n个位置选n-1个放左括号的方案数 = (2nn−1)\binom{2n}{n-1}。

因此：

合法序列数=(2nn)−(2nn−1)=1n+1(2nn)\text{合法序列数} = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n}

这就得到了卡特兰数的通项公式。

4. 编程实现：如何算出卡特兰数？

计算卡特兰数时，n稍微大一点（比如n=20）结果就会很大（C_20 ≈ 6.56e9 已经超int范围），所以要注意整数溢出。实际编程竞赛中常常要求取模（比如 mod 1e9+7）或者使用高精度。下面我们给出两种常用的计算方法，以及一个安全递推公式。

4.1 递推公式（动态规划法）

用数组 dp 存下前面所有值，然后递推。适合 n ≤ 1000 以内（因为结果会指数增长，但用64位整数最多到 n≈35 就溢出了）。

C++ 实现

#include <iostream>
using namespace std;

// 使用递推公式（动态规划），适合 n <= 35
long long catalan_dp(int n) {
    long long dp[100] = {0};  // 假设 n 不超过 35
    dp[0] = 1;                // C0 = 1
    for (int i = 1; i <= n; i++) {
        long long sum = 0;
        for (int j = 0; j < i; j++) {
            sum += dp[j] * dp[i - 1 - j];
        }
        dp[i] = sum;
    }
    return dp[n];
}

int main() {
    // 测试前 10 项
    for (int n = 0; n <= 10; n++) {
        cout << "C(" << n << ") = " << catalan_dp(n) << endl;
    }
    return 0;
}

Python 实现

def catalan_dp(n):
    """动态规划递推，返回第n个卡特兰数"""
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        total = 0
        for j in range(i):
            total += dp[j] * dp[i - 1 - j]
        dp[i] = total
    return dp[n]

# 测试
for n in range(11):
    print(f"C({n}) = {catalan_dp(n)}")

4.2 更高效的递推公式（推荐）

还有一个更容易计算的递推关系：

Cn=2(2n−1)n+1Cn−1C_n = \frac{2(2n-1)}{n+1} C_{n-1}

即：

Cn=Cn−1×4n−2n+1C_n = C_{n-1} \times \frac{4n-2}{n+1}

这个公式的好处是：只需要一个变量，每次迭代做一次乘法和一次除法，并且可以保证每一步都是整除（因为卡特兰数永远是整数）。我们用这个公式可以计算到 n ≈ 35（64位整数）。

C++ 安全递推

#include <iostream>
using namespace std;

// 安全递推：C_n = C_{n-1} * (4n-2) / (n+1)
long long catalan_iter(int n) {
    long long c = 1;  // C0 = 1
    for (int i = 1; i <= n; i++) {
        c = c * (4 * i - 2) / (i + 1);
    }
    return c;
}

int main() {
    for (int n = 0; n <= 10; n++) {
        cout << "C(" << n << ") = " << catalan_iter(n) << endl;
    }
    return 0;
}

Python 实现

def catalan_iter(n):
    """迭代法：C_n = C_{n-1} * (4n-2) // (n+1)"""
    c = 1
    for i in range(1, n + 1):
        c = c * (4 * i - 2) // (i + 1)
    return c

# 测试
for n in range(11):
    print(f"C({n}) = {catalan_iter(n)}")

4.3 直接使用组合数公式（注意顺序）

也可以直接用通项公式计算组合数。但要注意：先计算 (2nn)\binom{2n}{n} 再除以 n+1，中间组合数可能会很大，而且整数除法要保证整除。Python 的 math.comb 可以返回大整数，直接除法没问题。C++ 则需要用乘法再除法，但顺序容易导致分数除不尽。

C++ 组合数计算（慎重）

下面这个方法不推荐，因为 c = c * (2n - i + 1) / i 在 i 不等于1时，乘法可能溢出，且不能保证整除（但实际因为组合数一定是整数，只要按正确的顺序乘除，可以整除。不过 n 稍大就会越界。）

Python 组合数计算（推荐）

from math import comb

def catalan_comb(n):
    """使用组合数公式 C(2n, n) // (n+1)"""
    return comb(2 * n, n) // (n + 1)

# 测试
for n in range(11):
    print(f"C({n}) = {catalan_comb(n)}")

⚠ 常见错误与新手易犯的问题

  1. 递推公式写错下标
    正确：Cn=∑i=0n−1CiCn−1−iC_{n} = \sum_{i=0}^{n-1} C_i C_{n-1-i}。有人会误写成 ∑i=0nCiCn−i\sum_{i=0}^{n} C_i C_{n-i}，结果多加了项。

  2. 整数除法顺序问题
    在C++中做 c * (4*i-2) / (i+1) 时，先乘后除，因为 (4*i-2) 一定能被 (i+1) 整除，但如果你先除后乘，就会丢失精度。比如 c = c / (i+1) * (4*i-2) 在c不整除时出错。

  3. 忽略大数溢出
    int 只能存到 C_13 ≈ 742900，long long 能存到 C_35 ≈ 3.115e19。如果 n 更大，就得用高精度（Python 自带，C++ 需用大数库或取模）。

  4. 混淆下标：n从0开始还是从1开始
    很多题目里说“n个节点的二叉树”，对应卡特兰数 C_n（n≥0）。但有些教材把 C_1 对应1个节点。务必确认起点。

5. 生活应用举例：原来卡特兰数就在身边！

5.1 买冰激凌的排队问题（括号匹配变种）

你和好朋友去冰激凌店，菜单上有两种口味：草莓（S）和巧克力（C）。老板规定：任何时候，已经买草莓的人数不能少于买巧克力的人数（否则巧克力卖断了会吵架）。如果你们一共买了4个球（2个草莓，2个巧克力），有多少种购买顺序？
这就是 n=2 的括号匹配问题，合法序列有 2 种：S C S C 和 S S C C。如果4个球中草莓和巧克力各2个，但顺序自由，那总共 C_2 = 2 种。

5.2 分糖果的堆叠（二叉树计数）

假设你有 3 颗一模一样的糖果，把它们分成两堆（你可以先分一堆，再分剩下的），每次分堆可以看作一种二叉树的结构：

  • 根节点是一堆，左子树是里面的分法，右子树是外面的分法。
    所以3颗糖果的分堆方式有多少种？答案是 C_3 = 5 种。比如：
  1. 先拿一颗，剩下两颗；再分剩下两颗（有两种分法）。
  2. 先拿两颗，剩一颗；那一颗再分（只有一种）。
    所有这些不同分法对应卡特兰数。

5.3 运动会入场式（网格路径）

学校要举办运动会，每个班级从操场左下方走向右上方升旗台，只能向右或向上走，而且不能走到对角线的左边（保持“向右步数 ≥ 向上步数”），因为走偏了会挡到其他班。如果操场是 3×3 的方格，有多少种合法入场路线？答案是 C_3 = 5。你可以试着画一画，会发现和括号序列的结构一一对应。

6. 编程生成所有合法括号序列（回溯法）

学会了计算个数，我们还想看看具体有哪些序列。用回溯（backtracking）可以轻松生成所有方案，这也能帮助我们理解卡特兰数的结构。

C++ 完整代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 回溯生成所有合法括号序列
// left: 已用的左括号数, right: 已用的右括号数, cur: 当前字符串
// result: 存放所有结果
void generate_parenthesis(int n, int left, int right, string cur, vector<string>& result) {
    // 当左右括号都用了n个时，就得到了一个合法序列
    if (left == n && right == n) {
        result.push_back(cur);
        return;
    }
    // 还可以继续加左括号（只要左括号没超过n）
    if (left < n) {
        generate_parenthesis(n, left + 1, right, cur + "(", result);
    }
    // 如果当前右括号数量小于左括号，可以加右括号
    if (right < left) {
        generate_parenthesis(n, left, right + 1, cur + ")", result);
    }
}

int main() {
    int n = 3;
    vector<string> res;
    generate_parenthesis(n, 0, 0, "", res);
    cout << "n = " << n << " 的合法括号序列共 " << res.size() << " 种:" << endl;
    for (string s : res) {
        cout << s << endl;
    }
    return 0;
}

运行输出：

n = 3 的合法括号序列共 5 种:
((()))
(()())
(())()
()(())
()()()

Python 完整代码

def generate_parenthesis(n):
    """返回所有 n 对括号的合法序列列表"""
    res = []
    # 定义回溯函数，left, right 是已经使用的左右括号数
    def backtrack(left, right, cur):
        if left == n and right == n:
            res.append(cur)
            return
        if left < n:
            backtrack(left + 1, right, cur + "(")
        if right < left:
            backtrack(left, right + 1, cur + ")")
    backtrack(0, 0, "")
    return res

n = 3
res = generate_parenthesis(n)
print(f"n = {n} 的合法括号序列共 {len(res)} 种:")
for s in res:
    print(s)

小技巧：回溯的过程中，我们每次只走“合法”的下一步，所以不会生成非法序列。这正是卡特兰数在递归和动态规划中的自然体现。

7. 常见错误与注意事项（再强调一遍）

错误类型错误示例正确做法
递推时下标忘记 -1dp[i] = sum(dp[j]*dp[i-j])应写 dp[i] += dp[j] * dp[i-1-j]
计算组合数时丢了分母c = c * (2n - i) / i 而不除以 (n+1) 最后最后要除以 (n+1)，或用专用递推
回溯生成时忘记递归出口无限递归加上 if left == n and right == n 返回
递归时左右括号条件写反if right < n 而不是 if right < left右括号必须在左括号之后才可加
用 int 类型存大结果n=20 时 C_20=6564120420，超出 int 范围使用 long long 或 Python 整数

8. 练习：动手试试吧！

  1. 基础计算：用纸笔算一算 C_6 应该是多少？（跟前面表格对答案：132）
  2. 证明递推：用自己的话解释为什么卡特兰数满足 Cn=∑CiCn−1−iC_n = \sum C_i C_{n-1-i}。（提示：考虑第一个左括号匹配的右括号位置）
  3. 生成二叉树形状：请你编写一个程序，输出 n=3 时的所有不同二叉树的形状（可以用字符串表示，比如 (()()) 表示一种树形结构，或者用括号序列来编码二叉树）。
  4. 生活拓展：你和小明玩“接龙游戏”，每次你可以说一个词或者把两个已有的词组合成新词，请问如果要造出 n 个词的序列（每个词要么是一个基础词，要么是由两个词拼成），有多少种不同的造词顺序？（这是卡特兰数的另一种体现：Dyck 路径对应的表达式树）

9. 小结：卡特兰数为什么这么重要？

卡特兰数连接着组合数学中许多看上去完全不同的领域：括号匹配、二叉树、多边形剖分、网格路径、栈的出入顺序、三角剖分、表达式求值…… 它就像一个“翻译官”，能把一个问题转换成另一个问题。

掌握了卡特兰数的递推公式和通项公式，以及如何用代码生成具体方案，你就拥有了一个强大的“解题工具”。在编程竞赛（如 NOI、ACM）中，卡特兰数经常作为组合计数问题的核心出现，比如：

  • 栈的弹出顺序
  • 多边形三角剖分方案数
  • 单调路径计数
  • 不相交弦的连线

下一步你可以学习：组合数取模（模大质数），卡特兰数与斐波那契数列的关系，以及如何用生成函数推导卡特兰数。另外，和卡特兰数相似的还有 斯特林数、贝尔数，它们也常用于组合计数问题。

希望这篇文章能帮你把卡特兰数玩转！如果还有疑问，可以再去看看 组合数学 中关于 Dyck 路 和 括号序列 的章节，那里有更深入的讲解。

例题精讲

1单选题

卡特兰数列通常定义为C₀=1，C₁=1，C₂=2，那么C₃的值是多少？

A3
B4
C5
D6
2单选题

有4个不同元素按1,2,3,4顺序依次进栈，可能的出栈序列总数是多少？

A5
B10
C14
D20
3判断题

n个节点的不同形状的二叉搜索树（BST）的数量等于第n个卡特兰数（n≥0）。

4判断题

卡特兰数的通项公式为 Cₙ = (1/(n+1)) × C(2n, n)，其中C(2n,n)表示组合数。

5填空题
以下函数使用递推法计算第n个卡特兰数（n≤30）。请补全循环内的累加语句。

long long catalan(int n) {
    long long c[31] = {0};
    c[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            c[i] ___
        }
    }
    return c[n];
}