栈的输出序列与卡特兰数

桜小路ルナ様です

590人浏览 · 2026-03-15 14:16:44

桜小路ルナ様です · 2026-03-15 14:16:44 发布

栈的输出序列与卡特兰数：从记忆化搜索到数学模型的深度解析

在算法竞赛中，经常会遇到关于合法操作序列计数的问题。以经典的洛谷 P1044 [NOIP 2003 普及组] 栈为例，题目要求计算 $1,2,…,n1,2,\ldots,n$ 经过栈的 push 和 pop 操作后，可能得到的输出序列总数。

本文将从基础的搜索状态空间出发，探讨如何通过操作的唯一性进行计数，并逐步引出这类问题的核心数学模型——卡特兰数（Catalan Number），同时深入解析卡特兰数在不同场景下的两种核心“面孔”。

一、基于过程的状态空间搜索与一一映射

在面对“求合法结果的总数”时，直接去枚举最终的排列并判断其合法性通常是困难且低效的。一个更底层的思维方式是：不关注最终结果，而是关注生成结果的操作过程。

因为输入序列 $\ldots, n$ 的顺序是固定的，任何一种合法的“进栈、出栈的操作序列”，必然唯一对应一种“输出序列”。这就形成了一种一一映射的关系：合法的操作序列数量，等于合法的输出排列数量。

因此，可以通过深度优先搜索（DFS）模拟这个过程。在任意时刻，状态可以由两个量唯一确定：

stknum: 当前栈内元素的个数。
numbers: 还没入栈的元素个数。

在任意状态下，面临的合法决策最多只有两种：

进栈操作：只要还有未入栈的元素（numbers > 0），就可以将一个元素压入栈中，此时 stknum + 1，numbers - 1。
出栈操作：只要栈内有元素（stknum > 0），就可以将栈顶元素弹出，此时 stknum - 1，numbers 不变。

为了避免重复计算，可以引入一个二维数组记录已经计算过的状态，这就是记忆化搜索。以下是这种思路的 C++ 代码实现：

#include <bits/stdc++.h>
using namespace std;

int n;
int mem[30][30];

int dfs(int stknum, int numbers){
    // 边界条件：如果没有未进栈的数字了，剩余的元素只能依次全部出栈，这构成 1 种确定方案
    if(numbers == 0){
        return 1;
    }
    
    int cnt = 0;
    
    // 决策1：将一个未入栈的数字压入栈中
    if(mem[stknum + 1][numbers - 1]) {
        cnt += mem[stknum + 1][numbers - 1];
    } else {
        int tmp = dfs(stknum + 1, numbers - 1);
        cnt += tmp;
        mem[stknum + 1][numbers - 1] = tmp;
    }
    
    // 决策2：将栈顶元素弹出（前提是栈不为空）
    if(stknum > 0) {
        if(mem[stknum - 1][numbers]) {
            cnt += mem[stknum - 1][numbers];
        } else {
            int tmp = dfs(stknum - 1, numbers);
            cnt += tmp;
            mem[stknum - 1][numbers] = tmp;
        }
    }
    
    return cnt;
}

int main(){
    cin >> n;
    int cnt = dfs(0, n);
    cout << cnt << '\n';
    return 0;
}

上述代码的时间复杂度为 $O(n^2)$ ，对于 $\le 18$ 的数据范围绰绰有余。但如果 $n$ 的范围扩大到 $10^5$ ，这种二维状态的递推将无法承受时间和空间的开销。

二、抽象为数学模型：卡特兰数

如果仔细观察上述搜索过程的核心限制：整个过程需要执行 $n$ 次进栈动作和 $n$ 次出栈动作，且在任何时刻，已经执行的出栈次数，绝对不能超过已经执行的进栈次数（否则就会试图从空栈中弹出元素）。

在组合数学中，满足这种“两种动作数量相等，且在任意前缀中一种动作的数量不小于另一种动作的数量”的模型，其合法方案总数构成了一个著名的数列——卡特兰数（Catalan Number）。

卡特兰数的前几项为： $\dots$ （对应 $\dots$ ）。

三、卡特兰数的两副“面孔”：经典同构问题解析

卡特兰数在数学和算法中有极其广泛的应用。表面上看毫不相干的问题，背后往往隐藏着相同的数学本质。卡特兰数主要有两副核心“面孔”。

面孔一：两种操作互不超越（线性匹配匹配）

除了栈的输出序列，网格路径问题是这一面孔的经典代表：

在 $\times n$ 的网格中，从左下角坐标 $(0, 0)$ 走到右上角 $(n, n)$ ，每次只能向右或向上走，且不能越过对角线，有多少种走法？

乍一看，这与进出栈毫无关系。但细细剖析：
每次向右走一步，横坐标 $x$ 加 1；每次向上走一步，纵坐标 $y$ 加 1。
核心条件是“不能越过对角线”。对角线方程为 $y = x$ ，不能越过意味着在整个行走的任意时刻，必须满足 $\le x$ 。也就是说：向上走的步数，绝对不能超过向右走的步数。

这与栈的操作完美对应：

向右走（横坐标 +1） 等价于 进栈操作（栈内元素 +1）
向上走（纵坐标 +1） 等价于 出栈操作（栈内元素 -1）
不能越过对角线 ( $\le x$ ) 等价于 出栈的次数不能超过进栈的次数
总共走到 $(n, n)$ 等价于 总共进行了 $n$ 次进栈和 $n$ 次出栈

同理，经典的括号匹配问题（右括号数量不能超过左括号）也完全契合这一模型。

面孔二：分治与组合的二叉树结构（递归切分）

卡特兰数的另一副面孔，体现在“将一个大问题切分成两个独立的小问题”的结构中。凸多边形划分问题是最佳代表：

将一个凸 $n + 2$ 边形通过不相交的对角线划分为 $n$ 个三角形，有多少种划分方法？

这里似乎只有“画对角线”一种操作，为什么也是卡特兰数？
假设有一个凸 $n + 2$ 边形，顶点按顺时针编号为 $\ldots, n+2$ 。我们可以盯住其中一条固定的边，比如连接顶点 $1$ 和 $n + 2$ 的底边。
在任何一种合法的三角形划分中，这条底边必定属于某一个三角形。要构成这个三角形，还需要选择第三个顶点 $k$ （ $k$ 可以是 $\ldots, n+1$ 中的任意一个）。

一旦选定了这个顶点 $k$ ，大三角形 $(1, k, n + 2)$ 就像一把刀，把原来的多边形切成了两半：

左边： 由顶点 $\ldots, k$ 构成的一个凸 $k$ 边形。
右边： 由顶点 $\ldots, n+2$ 构成的一个凸 $n + 3 - k$ 边形。

这两个小多边形接下来还要各自继续划分三角形。如果定义 $H_n$ 为划分 $n + 2$ 边形的方案数，选定顶点 $k$ 时的总划法就是左边的方案数乘上右边的方案数。把所有可能的 $k$ 累加起来，就得到了卡特兰数极其重要的非线性递推公式（卷积公式）：
$Hn=H0Hn−1+H1Hn−2+H2Hn−3+…+Hn−1H0H_n = H_0 H_{n-1} + H_1 H_{n-2} + H_2 H_{n-3} + \ldots + H_{n-1} H_0$

进出栈问题同样可以用这个公式解释：如果关注“最后一次出栈的元素是哪一个”，也能将操作序列劈成左右两个互相独立的合法子序列，从而推导出完全相同的乘法递推式。两种面孔在数学上殊途同归。

四、卡特兰数的求解公式与代码

通过组合数学的反射容斥原理，可以推导出卡特兰数 $H_n$ 的通项公式与线性递推公式。

1. 组合数通项公式：
$Hn=1n+1(2nn)=(2n)!(n+1)!n!H_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$

2. 线性递推公式（最常用于编程求解）：
$Hn=Hn−1×4n−2n+1H_n = H_{n-1} \times \frac{4n - 2}{n + 1}$

利用递推公式，可以在 $O (n)$ 的时间复杂度与 $O (1)$ 的空间复杂度下解决该问题，完美突破搜索算法的瓶颈。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 使用 long long 防止乘法过程溢出
    long long h = 1; 
    for (int i = 1; i <= n; i++) {
        h = h * (4 * i - 2) / (i + 1);
    }
    
    cout << h << '\n';
    return 0;
}