卡特兰数

Xanadu132025年8月23日大约 3 分钟

卡特兰数

以下例子都属于卡特兰数问题：

有 $2n$ 个人排成一行进入剧场。入场费 5 元。其中只有 $n$ 个人有一张 5 元钞票，另外 $n$ 个人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
有一个大小为 $n\times n$ 的方格图左下角为 $(0,0)$ 右上角为 $(n,n)$ ，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 $y=x$ 上方（但可以触碰）的情况下到达右上角有多少可能的路径？
在圆上选择 $2n$ 个点，将这些点成对连接起来使得所得的 $n$ 条线段不相交的方法数？
对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
一个栈（无穷大）的进栈序列为 $1,2,3,\ldots,n$ 有多少个不同的出栈序列？
$n$ 个结点可构造多少个不同的二叉树？
由 $n$ 个 $+1$ 和 $n$ 个 $-1$ 组成的 $2n$ 个数 $a_1,a_2,\dots,a_{2n}$ ，其部分和满足 $a_1+a_2+\cdots+a_k\ge 0\ (k=1,2,3,\dots,2n)$ ，有多少个满足条件的数列？

出栈序列数量

对应(5)

洛谷 P1044

思路

对于一个指定的序列，我们能做入栈、出栈两种操作。

记 $f(x,y)$ 表示当前序列有 $x$ 个未入栈的数，栈中当前有 $y$ 个数。

入栈操作即 $f(x,y) \rightarrow f(x-1, y+1)$ ；

出栈操作即 $f(x,y) \rightarrow f(x, y-1)$ ；

边界条件： $f(0, i) = 1$

所求答案为 $f(n,0)$

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
using i64 = long long;
mt19937_64 rng(random_device{}());
void solve() {
    vector<vector<i64>> dp(20, vector<i64>(20));
    int n;
    cin >> n;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (i == 0) dp[i][j] = 1; // 只能连续pop
            else if (j == 0) dp[i][j] = dp[i-1][j+1]; // 只能入栈
            else dp[i][j] = dp[i-1][j+1] + dp[i][j-1];
        }
    }
    cout << dp[n][0];
}
int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T;
    // cin >> T;
    // while (T--) 
        solve();
    return 0;
}

欧拉括号序列

对应(1)、(2)、(6)、(7)

欧拉括号序列通过在一棵有根有序树上做 DFS（欧拉遍历）得到：

进入一个结点时输出“(”，
离开该结点时输出“)”。

得到长度为 2n 的括号串（n 为结点数）。它一定是一个平衡括号序列（任意前缀“(”不少于“)”）。

性质：

括号前缀的 $cnt['('] - cnt[')']$ =当前深度；
某个结点对应的一段从它的“入括号(”到“出括号)”的连续区间，这段正好覆盖它的整棵子树。

这个表示常用于树上区间化、RMQ/LCA 等。

但注意：按这个“入-出”括号法，只有一个孩子的二叉树无法区分“只有左孩子”和“只有右孩子”（两种都会产生同一个“(())”），所以它与“有左右次序的二叉树”不是一一对应。

可以修改匹配规则：

到一个结点先写“(”，
递归写左子树，
然后写“)”，
再递归写右子树；
叶子结点产生“()”。

例如：

一个根节点只有一个左叶子得到：(())
一个根节点只有一个右叶子得到：()()

至此，“n 个结点可构造多少个不同的二叉树”转化为欧拉括号序列问题。

Ref

https://oi-wiki.org/math/combinatorics/catalan/