卡特兰数简介

概念

卡特兰数（Catalan Number）是一个在组合数学中非常重要的数列，广泛应用于各种算法竞赛问题中，尤其是涉及递归、分治法、树结构、路径问题等领域。

卡特兰数的定义：

第n个卡特兰数可以通过递推公式或者显式公式来定义。

1. 递推公式： $C\_0 = 1$ $ C\_n = \sum\_{i=0}^{n-1} C\_i \cdot C\_{n-1-i} \quad (n \geq 1) $ 其中，$C\_n$ 表示第n个卡特兰数。

2. 显式公式： $C\_n = \frac{1}{n+1} \binom{2n}{n}$ 其中，$\binom{2n}{n}$是组合数，表示从2n个元素中选出n个元素的组合数。显式公式更加直接计算卡特兰数。

卡特兰数的应用：

卡特兰数在许多组合数学问题中都有应用，以下是一些典型的应用场景：

1. 有效的括号配对：卡特兰数可以用于计算有效括号配对的数目。例如，对于给定的n对括号，卡特兰数可以表示有多少种不同的方式来有效地配对这些括号。

2. 二叉树的数量：卡特兰数还可以表示一个具有n个节点的不同二叉树的数量。具体来说，C_n表示n个节点的二叉搜索树的个数。

3. 路径问题：在一个格子中从左下角到右上角，如何计算经过一系列合法的路径（仅能向上或向右走）的数量。卡特兰数可以解决这类路径问题。

4. 堆排序的树结构：卡特兰数还与堆排序和堆的构建有关系，特别是在处理堆的结构时，卡特兰数可以用于计算堆的不同排列。

卡特兰数的计算方法：

• 递推法：根据递推公式逐步计算。
• 动态规划：用动态规划存储每个卡特兰数的值，避免重复计算。
• 显式公式：使用组合数公式直接计算。

卡特兰数的前几个值： $ C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42, C_6 = 132, \dots $

通项公式

卡特兰数的递推式为

$$H_n=\sum_{i=0}^{n-1}H_{i}H_{n-i-1} \quad (n\ge 2)$$

其中 $H_0=1,H_1=1$。设它的普通生成函数为 $H(x)$。

我们发现卡特兰数的递推式与卷积的形式很相似，因此我们用卷积来构造关于 $H(x)$ 的方程：

$$\begin{aligned} H(x)&=\sum_{n\ge 0}H_nx^n\\ &=1+\sum_{n\ge 1}\sum_{i=0}^{n-1}H_ix^iH_{n-i-1}x^{n-i-1}x\\ &=1+x\sum_{i\ge 0}H_{i}x^i\sum_{n\ge 0}H_{n}x^{n}\\ &=1+xH^2(x) \end{aligned} $$

解得

$$H(x)=\frac{1\pm \sqrt{1-4x}}{2x}$$

那么这就产生了一个问题：我们应该取哪一个根呢？我们将其分子有理化：

$$H(x)=\frac{2}{1\mp \sqrt{1-4x}}$$

代入 $x=0$，我们得到的是 $H(x)$ 的常数项，也就是 $H_0$。当 $H(x)=\dfrac{2}{1+\sqrt{1-4x}}$ 的时候有 $H(0)=1$，满足要求。而另一个解会出现分母为 $0$ 的情况（不收敛），舍弃。

因此我们得到了卡特兰数生成函数的封闭形式：

$$H(x)=\frac{1- \sqrt{1-4x}}{2x}$$

接下来我们要将其展开。但注意到它的分母不是斐波那契数列那样的多项式形式，因此不方便套用等比数列的展开形式。在这里我们需要使用牛顿二项式定理。我们来先展开 $\sqrt{1-4x}$：

$$\begin{aligned} (1-4x)^{\frac{1}{2}} &=\sum_{n\ge 0}\binom{\frac{1}{2}}{n}(-4x)^n\\ &=1+\sum_{n\ge 1}\frac{\left(\frac{1}{2}\right)^{\underline{n}}}{n!}(-4x)^n \end{aligned} \tag{1} $$

注意到

$$\begin{aligned} \left(\frac{1}{2}\right)^{\underline{n}} &=\frac{1}{2}\frac{-1}{2}\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\\ &=\frac{(-1)^{n-1}(2n-3)!!}{2^n}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^n(2n-2)!!}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!} \end{aligned} $$

这里使用了双阶乘的化简技巧。那么带回 $(1)$ 得到

$$\begin{aligned} (1-4x)^{\frac{1}{2}} &=1+\sum_{n\ge 1}\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!n!}(-4x)^n\\ &=1-\sum_{n\ge 1}\frac{(2n-2)!}{(n-1)!n!}2x^n\\ &=1-\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n \end{aligned} $$

带回原式得到

$$\begin{aligned} H(x)&=\frac{1- \sqrt{1-4x}}{2x}\\ &=\frac{1}{2x}\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n\\ &=\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}x^{n-1}\\ &=\sum_{n\ge 0}\binom{2n+1}{n+1}\frac{1}{(2n+1)}x^{n}\\ &=\sum_{n\ge 0}\binom{2n}{n}\frac{1}{n+1}x^{n}\\ \end{aligned} $$

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

相关例子

1. 有 2n 个人排成一行进入剧场：

问题描述：有 $2n$ 个人排成一行进入剧场，其中只有 $n$ 个人有 5 元钞票，另 $n$ 人只有 10 元钞票，且售票处没有其他钞票。要求的是如何安排这 $2n$ 个人的顺序，使得每个拥有 10 元钞票的人都能在售票员处找到 5 元的零钱。

解法： 这个问题可以转化为一个“有效括号配对”问题。每个有 5 元钞票的人可以视为一个“开括号”（表示增加 5 元），而每个有 10 元钞票的人可以视为一个“闭括号”（表示减少 5 元）。我们要求的是一个有效的括号序列，其中每个闭括号都必须在一个开括号之前出现。

这个问题的解法就是求卡特兰数 $C_n$，它表示 $n$ 对括号的有效配对方式。

公式： $C\_n = \frac{1}{n+1} \binom{2n}{n}$

2. 大小为 n×n 的方格图，走到右上角不越过对角线：

问题描述：在一个 $n \times n$ 的方格中，从左下角 (0,0) 到右上角 (n,n)，每步只能向右或向上走，且不能越过对角线 $y = x$。

解法： 这个问题可以通过卡特兰数来解决。具体来说，在每个路径中，我们可以将向右和向上的步骤视为 "右" 和 "上" 的动作，且要求路径从不越过对角线。这样的路径数目正好等于第 $n$ 个卡特兰数。

答案： $C_n$

3. 在圆上选择 2n 个点，连接成不相交的线段：

问题描述：在圆上选择 $2n$ 个点，并将这些点成对连接，要求得到的 $n$ 条线段不相交。

解法： 这个问题对应的是卡特兰数的经典应用，涉及无交叉的配对。通过连线将圆上的 $2n$ 个点成对连接，并且要求这些线段不相交，实际上是一个经典的卡特兰数问题。

答案： $C_n$

4. 将凸多边形分成不相交的三角形：

问题描述：将一个 $n$ 边形的凸多边形分成不相交的三角形区域。

解法： 这正是一个卡特兰数的经典应用问题，表示将一个凸多边形分解为不相交三角形的方式数。具体地，给定一个 $n$-边形，分割成三角形的方式数是 $C\_{n-2}$，因为分割的三角形数目是 $n-2$。

答案： $C_{n-2}$

5. 栈的不同出栈序列：

问题描述：对于一个无穷大的栈，入栈序列为 1, 2, 3, ..., n，问有多少个不同的出栈序列。

解法： 这个问题也可以通过卡特兰数来解决。它的数学意义是：对于一个给定的入栈序列，求出栈顺序不违反栈的顺序规则的不同方式数。此问题的解法就是第 $n$ 个卡特兰数。

答案： $C_n$

6. n 个结点的不同二叉树：

问题描述：给定 $n$ 个节点，问能构造多少个不同的二叉树。

解法： 卡特兰数也可以表示构造不同二叉树的数量。给定 $n$ 个节点，构造二叉树的不同方式数是第 $n$ 个卡特兰数。

答案： $C_n$

7. 由 n 个 +1 和 n 个 -1 组成的数列，部分和不小于 0：

问题描述：给定一个由 $n$ 个 $+1$ 和 $n$ 个 $-1$ 组成的数列，求满足部分和 $a_1 + a_2 + \dots + a_k \geq 0$ 对于所有 $k = 1, 2, \dots, 2n$ 的数列的数量。

解法： 这个问题可以通过卡特兰数来描述，因其本质上要求部分和始终不小于零。这是典型的“有效括号问题”，其中每个 $+1$ 对应一个“开括号”，每个 $-1$ 对应一个“闭括号”，而我们需要保证每个闭括号都在一个开括号之后。

答案： $C_n$

8.路径计数问题

1. 从 $(0,0)$ 到 $(m,n)$ 的非降路径数：

   非降路径是指只能向上或向右走的路径。假设我们从 $(0,0)$ 出发，目标是到达 $(m,n)$，路径只能由 $m$ 个向右的步伐（x）和 $n$ 个向上的步伐（y）组成。

   解法： 这个问题的关键是计算所有可能的路径。可以看作是一个排列问题，即从 $m + n$ 个步骤中选择 $m$ 个步骤是向右走的，其余的都是向上的。这个数量就是排列数 $\binom{m+n}{m}$，即从 $m + n$ 个位置中选取 $m$ 个位置来放置 x 的步伐。

   公式： $ \text{路径数} = \binom{m+n}{m} = \frac{(m+n)!}{m!n!} $

2. 从 $(0,0)$ 到 $(n,n)$ 的除端点外不接触直线 $y=x$ 的非降路径数：

   在这个问题中，我们要求的是从 $(0,0)$ 到 $(n,n)$ 的路径，并且这些路径在途中不能接触直线 $y = x$ 除了端点 $(0,0)$ 和 $(n,n)$。我们可以通过反演法和对称性来解决这个问题。

   解法：

   • 第一步是计算所有的非降路径数，忽略任何限制条件。可以通过选择 $n$ 次向右走和 $n$ 次向上走的步骤来计算路径数，即 $\binom{2n}{n}$。

   • 第二步是计算与直线 $y = x$ 接触的路径。我们可以通过反演法来计算这一类路径。具体地，假设一条路径接触了直线 $y = x$，我们可以通过将最后一个接触点到 $(1,0)$ 的路径部分进行对称变换，得到从 $(0,1)$ 到 $(n,n-1)$ 的路径数。这可以通过减去 $\binom{2n-2}{n}$ 来得到。

   • 第三步是计算不接触 $y = x$ 直线的路径数。通过对称性，结果可以表示为： $2 \binom{2n-2}{n-1} - 2 \binom{2n-2}{n}$

3. 从 $(0,0)$ 到 $(n,n)$ 的除端点外不穿过直线 $y=x$ 的非降路径数：

   类似于第二步的推导，我们也可以通过反演和对称性得到不穿越直线 $y = x$ 的路径数。具体的处理方法依然是计算所有路径数，再通过对称性和反演法减去那些穿越 $y = x$ 的路径。

   总结：

   • 所有的非降路径数：$\binom{2n}{n}$
   • 接触 $y = x$ 直线的路径数：可以通过反演方法计算
   • 不接触 $y = x$ 直线的路径数：使用对称性和反演法得出

例题luogu

P1044 [NOIP 2003 普及组] 栈

题目背景

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

题目描述

宁宁考虑的是这样一个问题：一个操作数序列，$1,2,\ldots ,n$（图示为 1 到 3 的情况），栈 A 的深度大于 $n$。

现在可以进行两种操作，

1. 将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）
2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1 的过程。

（原始状态如上图所示）

你的程序将对给定的 $n$，计算并输出由操作数序列 $1,2,\ldots,n$ 经过操作可能得到的输出序列的总数。

输入格式

输入文件只含一个整数 $n$（$1 \leq n \leq 18$）。

输出格式

输出文件只有一行，即可能输出序列的总数目。

输入输出样例 #1

输入 #1

3

输出 #1

5

说明/提示

【题目来源】

NOIP 2003 普及组第三题

参考代码

#include <bits/stdc++.h>
using namespace std; 
int main()
{
	long long a; cin>>a;
	
	long long c=1;
	for(int i=0;i<a;++i)
	{
		c=c*2*(2*i+1)/(i+2);
	}
	cout<<c;
	return 0;
}

P1754 球迷购票问题

题目描述

盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。

按售票处规定，每位购票者限购一张门票，且每张票售价为 $50$ 元。在排成长龙的球迷中有 $n$ 个人手持面值 $50$ 元的钱币，另有 $n$ 个人手持面值 $100$ 元的钱币。假设售票处在开始售票时没有零钱。试问这 $2n$ 个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。

例如当 $n=2$ 时，用 A 表示手持 $50$ 元面值的球迷，用 $B$ 表示手持 $100$ 元钱的球迷。则最多可以得到以下两组不同的排队方式，使售票员不至于找不出钱。

• 第一种：$\mathtt{[A,A,B,B]}$；
• 第二种：$\mathtt{[A,B,A,B]}$。

对于给定的 $n$，计算 $2n$ 个球迷有多少种排队方式，可以使售票处不至于找不出钱。

输入格式

一个整数，代表 $n$ 的值。

输出格式

一个整数，表示方案数。

输入输出样例 #1

输入 #1

2

输出 #1

2

说明/提示

数据范围及约定

对于全部数据，$0 \le n \le 20$。

参考代码

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

long long n, h[50];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    h[0] = h[1] = 1;

    for (long long i = 2; i <= n; i++) {
        h[i] = (h[i - 1] * (4 * i - 2)) / (i + 1);
    }

    cout << h[n] << endl;

    return 0;
}