卡特兰数：排队、括号、出栈背后的神奇数字

小朋友们，你们有没有看过爸爸和小朋友一起排队买冰淇淋？爸爸说：“我走在前面，你要跟在我后面，不能跑到我前头。”如果一共有n个爸爸和n个小朋友，他们排成一列，要求任何时候爸爸的人数都不少于小朋友的人数（否则小朋友就会跑到前面去啦），那么一共有多少种不同的排队方式呢？这个问题的答案就是“卡特兰数”。

卡特兰数是一个很神奇的数字序列。它有许多生活中的影子，比如：用n对括号组成正确的括号表达式（左括号不能少于右括号）、n个元素进栈后有多少种出栈顺序、n个节点能组成多少种不同的二叉树……

生活中的卡特兰数——从排队到括号

先让我们把“爸爸和小朋友排队”的规则再讲清楚：
假设有n个爸爸（用“红”色积木表示）和n个小朋友（用“蓝”色积木表示），排成一列。从队伍最前面往后看，任何时候已经数过的红色积木数量都不能少于蓝色积木数量。如果蓝色比红色多，就说明小朋友跑到爸爸前面去了，这种排队方式不合格。

这样的排队方式有多少种？n=1时，只有“红蓝”一种（因为“蓝红”一开始蓝色就多了一个，不合格）。n=2时，有“红红蓝蓝”和“红蓝红蓝”两种。n=3时就有5种了。这些数字1,2,5...就是卡特兰数。

除了排队，卡特兰数还出现在这些地方：

括号匹配：n对括号，能组成多少种合法的括号序列？比如n=2时，合法的有 ()() 和 (()) 两种。左括号就像“爸爸”，右括号就像“小朋友”。
栈的出栈顺序：n个不同的元素按顺序入栈，有多少种不同的出栈顺序？比如元素1,2,3入栈，出栈顺序有5种（如1,2,3；1,3,2；2,1,3；2,3,1；3,2,1），正对应n=3的卡特兰数C(3)=5。
二叉树形态：n个节点能组成多少种不同的二叉树（左子树和右子树交换算不同）？比如n=3时，有5种形态。

这些看似不同的问题，答案都是同一个数字序列，是不是很神奇？

卡特兰数的计算公式

怎么计算卡特兰数呢？有一个简单的递推公式：

C(0) = 1
C(1) = 1
C(n) = C(0)×C(n-1) + C(1)×C(n-2) + ... + C(n-1)×C(0)

例如：
C(2) = C(0)×C(1) + C(1)×C(0) = 1×1 + 1×1 = 2
C(3) = C(0)×C(2) + C(1)×C(1) + C(2)×C(0) = 1×2 + 1×1 + 2×1 = 5

这个公式怎么理解？你可以想象把排队分成两部分：第一个“爸爸”出现，然后后面跟着一堆小朋友和爸爸的组合。更准确地说，对于n对（爸爸和小朋友），我们可以用“第一个爸爸和他匹配的小朋友”来分割队列，这样左右两边就变成了更小的子问题。

还有一个更快的组合数公式（可以查资料了解）：
C(n) = (1/(n+1)) * C(2n, n)
但用递推公式写程序更直观。

用C++计算卡特兰数——一步步来

下面我们用C++写一个小程序，输入n，输出前n个卡特兰数。注意，数字可能变大，我们用long long类型存储。

#include <iostream>
using namespace std;

int main() {
    int n;  // 输入的个数
    cout << "请输入一个数字n: ";
    cin >> n;
    
    // 注意：卡特兰数增长很快，n最好不要超过20，否则long long会溢出
    long long catalan[25] = {0};  // 用数组存储卡特兰数，最大下标24
    catalan[0] = 1;  // C(0) = 1
    
    // 递推计算：先算C(1),再算C(2),...
    for (int i = 1; i <= n; i++) {
        catalan[i] = 0;  // 初始化为0，方便累加
        // 利用递推公式：C(i) = sum_{j=0}^{i-1} C(j) * C(i-1-j)
        for (int j = 0; j < i; j++) {
            catalan[i] += catalan[j] * catalan[i - 1 - j];
        }
    }
    
    cout << "前" << n << "个卡特兰数是：" << endl;
    for (int i = 0; i <= n; i++) {
        cout << "C(" << i << ") = " << catalan[i] << endl;
    }
    
    return 0;
}

试着运行一下，输入n=5，你会得到：
C(0)=1, C(1)=1, C(2)=2, C(3)=5, C(4)=14, C(5)=42。

如果你输入n=10，能得到C(10)=16796。但如果你输入n=20，小心结果可能超过long long的范围（最大约9×10^18，C(20)大约是6.56×10^9，还好；但C(35)就超过2^63了）。

常见错误与注意事项

新手在写卡特兰数程序时，容易犯这些错误：

数组下标搞混：递推内层循环 j 从0到i-1，对应 catalan[j] * catalan[i-1-j]。有人会写成 catalan[j] * catalan[i-j]，导致结果错误。
忘记初始化：catalan[0] 必须设为1。如果忘记，所有结果会变成0。
整数溢出：卡特兰数增长极快。n=30时，C(30) ≈ 3.8×10^16，还在long long范围内（9.2×10^18），但n=35就超了。如果需要计算更大的n，要使用高精度（大数）类型，比如用字符串或使用Python。
数组大小不足：如果用户输入n=30，而数组只开了25，就会越界访问。应该根据输入动态分配或者设定足够大的固定大小。为了安全，可以让用户输入n<=20，或者使用vector<long long>。
递推顺序错误：一定要从小的i往大的i算，因为计算C(i)需要用到所有C(j) (j<i)。如果先算大的，小的还没算出来，结果会是0。

完整可运行示例（改进版）

下面是一个更健壮的版本，加入了输入范围检查和动态数组（用C++ vector），变量名都加中文注释：

#include <iostream>
#include <vector>   // 使用动态数组，可以根据输入大小灵活分配
using namespace std;

int main() {
    int n;  // 要计算的卡特兰数下标
    cout << "请输入一个数字n (n <= 30): ";
    cin >> n;

    // 检查输入范围，避免溢出
    if (n < 0 || n > 30) {
        cout << "n应该在0到30之间，否则结果可能溢出。" << endl;
        return 1;  // 返回错误码
    }

    // 定义动态数组，长度为n+1，全部初始化为0
    vector<long long> catalan(n + 1, 0);
    catalan[0] = 1;  // C(0) = 1

    // 递推计算卡特兰数
    for (int i = 1; i <= n; i++) {
        catalan[i] = 0;  // 显式清零（vector已经初始化为0，这一步可省略）
        for (int j = 0; j < i; j++) {
            // C(i) = sum_{j=0}^{i-1} C(j) * C(i-1-j)
            catalan[i] += catalan[j] * catalan[i - 1 - j];
        }
    }

    // 输出结果
    cout << "前" << n << "个卡特兰数是：" << endl;
    for (int i = 0; i <= n; i++) {
        cout << "C(" << i << ") = " << catalan[i] << endl;
    }

    return 0;
}

运行示例（输入6）：

请输入一个数字n (n <= 30): 6
前6个卡特兰数是：
C(0) = 1
C(1) = 1
C(2) = 2
C(3) = 5
C(4) = 14
C(5) = 42
C(6) = 132

想一想：如果爸爸和小朋友一共有3个爸爸和3个小朋友，按照规则排队，是不是恰好有5种排法呢？你可以用红蓝积木实际摆一摆，验证卡特兰数的神奇哦！

卡特兰数