Catalan number（卡特兰数）详解，超详细！！！

卡特兰数的应用

$Catala{n}_n$ 可以表示：

• $n$ 个结点的不同形态的二叉树的个数
• $n$ 对括号的合法括号序列的个数
• 长度为 $n$ 的入栈序列对应的合法出栈序列个数
• 通过链接顶点而将 $n+2$ 边的凸多边形分成三角形的方法个数
• $n+1$ 个叶子的满二叉树个数

卡特兰数

卡特兰数为（从零项开始）：$1,1,2,5,14,42,132,429,1430,4862,?$

卡特兰数的递推公式的推导过程

我们从 n 对括号的合法括号序列的个数 入手

就拿 $5$ 对括号来说，可以分为 $5$ 个类型：

1. 最左边的左括号和第 $1$ 个右括号匹配
2. 最左边的左括号和第 $2$ 个右括号匹配
3. 最左边的左括号和第 $3$ 个右括号匹配
4. 最左边的左括号和第 $4$ 个右括号匹配
5. 最左边的左括号和第 $5$ 个右括号匹配

既然这 $5$ 对括号是合法的，就说明最左边的左括号就是第一位

也就是说，这对括号是最外层的

那么整个括号序列就被它分成了两部分

就拿 最左边的左括号和第 1 个右括号匹配 来说，这对括号里边有 $0$ 对括号，外边有 $4$ 对括号

$0$ 对括号的合法括号序列的个数是 $Catala{n}_0$，$4$ 对括号的合法括号序列的个数是 $Catala{n}_4$

根据乘法原理，这种情况的序列数量为 $Catanla{n}_0?Catanla{n}_4$

同理，最左边的左括号和第 $k$ 个右括号匹配，序列数量为 $Catanla{n}_{k?1}?Catanla{n}_{n?k}$

根据加法原理，$5$ 对括号的合法括号序列的个数为 $Catanla{n}_0?Catanla{n}_4+Catanla{n}_1?Catanla{n}_3+\dots +Catanla{n}_4?Catanla{n}_0$

因此，我们推出 $n$ 对括号的合法括号序列的个数为 $Catanla{n}_0?Catanla{n}_{n?1}+Catanla{n}_1?Catanla{n}_{n?2}+\dots +Catanla{n}_{n?1}?Catanla{n}_0$

代码实现卡特兰数的第 n 项

有一道洛谷上的题：P1044 [NOIP2003 普及组] 栈，因为卡特兰数的第 $n$ 项可以应用于长度为 $n$ 的入栈序列对应的合法出栈序列个数，所以这道题就是一道卡特兰数的模版题

这是注释版的代码：

#include <cstdio>
#define N 105
using namespace std;

typedef long long ll;

int n;
ll C[N];

int main() {
	scanf("%d", &n);
	
	C[0] = 1;
	
	for(int i = 1; i <= n; ++i)				// 枚举卡特兰数的第 i 项
		for(int k = 1; k <= i; ++k)			// 最左边的左括号和第 k 个有括号匹配
			C[i] += C[k - 1] * C[i - k];	// 根据递推公式写出
	
	printf("%lld\n", C[n]);
	
	return 0;
}

我的提交结果

尾声

如果这篇题解对您（或您的团队）有帮助的话，就帮忙点个赞，加个关注！

最后，祝您（或您的团队）在 OI 的路上一路顺风！！！

┬┴┬┴┤?ω?)ノ Bye~Bye~