卡特兰数学习笔记

发布时间：2026/7/19 19:03:42

前言

msjing要学卡特兰数了
msjing：555窝补药学数学

卡特兰数

卡特兰数是组合数学中一种常出现于各种计数问题中的数列，以比利时数学家欧仁·查理·卡特兰的名字命名。$1730$ 年，清代蒙古族数学家明安图在对三角函数幂级数的推导过程中首次发现，其学生在 $1774$ 年将成果发表在《割圜密率捷法》。比利时数学家欧仁·查理·卡特兰在 $1958$ 年研究括号序列时独立发现了该数列。
——百度百科

卡特兰数前几项为 $1, 1, 2, 5, 14, 42, 132, 429, \dots$（可以去 $OEIS$ 那里看）
接下来我们用通俗的语言介绍
卡特兰数就是一个数列，那有什么用呢
~~没什么鸾用打标看得出来就行~~
还是非常有用的，比如求合法括号序列个数，合法出栈顺序等，后面会说
令卡特兰数为 $C$，有一个递推式

$C_n = \left\{ \begin{array} &1 & n = 0\\ \sum\limits_{i=0}^{n-1}{C_i \times C_{n-1-i}} & n > 0 \end{array} \right.$

这个柿子非常吊，几乎所有问题都可以用这个解决
卡特兰数还有其他表示，一并给出

$C_n = \frac 1{n+1} \binom {2n}{n} = \frac {(2n)!}{(n)! \times (n+1)!} , n\ge 0$ $C_n = \binom{2n}{n} - \binom{2n}{n+1} , n \ge 0$ $C_n = \frac {4n - 2}{n + 1} \times C_{n - 1} , n > 0 , C_0 = 1$

解决问题

卡特兰数可以解决什么问题呢？

路径问题

有一个大小为 n$ \times n$ 的方格图，左下角为 $(0,0)$，右上角为 $(n,n)$。从左下角开始，每次都只能向右或者向上走一单位，不走到对角线 $y=x$ 上方（但可以触碰）的情况下，到达右上角的路径总数为 $C_n$

证明

我们考虑这个问题，第一次只能向右（向上就过线了），同理，最后一次只能向上，那么问题就变成了从 $(1,0)$ 到 $(k,k-1)$ 不过 $y = x - 1$ 的所有路径（$k$ 随便选），令此时路径数是 $T_{k-1}$，同理，从 $(k,k)$ 到 $(n,n)$ 的路径总数是 $T_{n-k}$，乘法原理有：

$T_n = \sum\limits_{k=1}^{n}{T_{k-1} \times T_{n-k}}$

我们发现这个长得好像上面的柿子，所以就有 $C_n = T_n$
得证

多边形三角划分问题

对角线不相交的情况下，将一个凸 $(n+2)$ 边形区域分成三角形区域的方法数为 $C_n$

证明

证明和上面差不多，e，懒了，咕咕咕
其他的就都不证了，太难搞了

圆内不相交弦问题

圆上有 $2n$ 个点，将这些点成对连接起来且使得所得到的 $n$ 条线段两两不交的方案数是 $C_n$。

二叉树问题

含有 $n$ 个结点的形态不同的二叉树数目为 $C_n$。

括号序列问题

由 $n$ 对括号构成的合法括号序列数为 $C_n$。

证明

这个玩意太经典了证一下吧
其实我们要是在 OI 就直接上栈了
考虑把这个问题转化，我们结合栈的做法，发现如果没有左括号，右括号有就是非法的，所以左括号数量必须大于等于右括号，我们就转化成路径问题了
得证

出栈序列问题

一个栈（无穷大）的进栈序列为 $1,2,3, \ldots ,n$，合法出栈序列的数目为 $C_n$。

重要结论证明即应用

我们要证的是 $C_n = \binom{2n}{n} - \binom{2n}{n+1}$ 这个柿子
我们去考虑总方案，由于是 $n \times n$，所以一共走 $2 \times n$ 步，需要向右走 $n$ 步，方案数为 $\binom{2n}{n}$。
这是总方案数，我们要求合法的，所以我们接下来求不合法的方案数
考虑转化，一个方案不合法，当且仅当它碰到线 $y = x + 1$，我们将这个点后面位置关于 $y = x + 1$ 做对称，那么从 $(0,0)$ 到 $(n,n)$ 的路径就变成了从 $(0,0)$ 到 $(n-1,n+1)$ 的路径，给张图

批注 2026-07-19 175518

鼠标低敏画这个图太费劲了
我们发现从 $(0,0)$ 到 $(n-1,n+1)$ 的路径是必过 $y = x + 1$ 的，所以每条路径都与从 $(0,0)$ 到 $(n,n)$ 的非法路径一一对应，所以总数为 $2 \times n$，方案数为 $\binom{2n}{n + 1}$。
所以 $C_n = \binom{2n}{n} - \binom{2n}{n+1}$ 成立，得证
提一嘴这个证明，用到了反射原理
证这个有什么用吗
欸，我们来一道例题

例题：BZOJ 3907

鉴于 $BZOJ$ 起飞了，所以跳转到 $LibreOJ$ 了
我们发现这道题并不是基本的 $n \times n$ 网格，所以我们利用上面的证明方法，可以推断出非法的序列到达的点是 $(m-1,n+1)$，所以非法方案数就是 $\binom{n+m}{n+1}$

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn=1e6+10,p=998244353;
int read()
{int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch == '-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
int n,m;
struct Combinatorics
{int f[maxn],g[maxn];int ksm(int x,int y,int mo){int cnt=1;while(y){if (y&1) cnt=(cnt*x)%mo;x=(x*x)%mo;y>>=1;}return cnt;}int inv(int a,int p) {return ksm(a,p-2,p);}void getfg(int n){f[0]=g[0]=1;for (int i=1;i<=n;i++) (f[i]=i*f[i-1])%=p,g[i]=inv(f[i],p);}int getC(int x,int y) {return ((f[x]*g[x-y])%p*g[y])%p;}
}c;
signed main()
{n=read(),m=read();c.getfg(2*n+1);printf("%lld\n",(c.getC(m+n,n)-c.getC(n+m,n+1)+p)%p);return 0;
}