Catalan number(卡特兰数)详解,超详细!!!

发布时间:2023年12月25日

卡特兰数的应用

C a t a l a n n Catalan_n Catalann? 可以表示:

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

卡特兰数

卡特兰数为(从零项开始): 1 , 1 , 2 , 5 , 14 , 42 , 132 , 429 , 1430 , 4862 , ? 1,1,2,5,14,42,132,429,1430,4862,\cdots 1,1,2,5,14,42,132,429,1430,4862,?

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

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

就拿 5 5 5 对括号来说,可以分为 5 5 5 个类型:

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

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

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

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

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

0 0 0 对括号的合法括号序列的个数是 C a t a l a n 0 Catalan_0 Catalan0? 4 4 4 对括号的合法括号序列的个数是 C a t a l a n 4 Catalan_4 Catalan4?

根据乘法原理,这种情况的序列数量为 C a t a n l a n 0 ? C a t a n l a n 4 Catanlan_0\cdot Catanlan_4 Catanlan0??Catanlan4?

同理,最左边的左括号和第 k k k 个右括号匹配,序列数量为 C a t a n l a n k ? 1 ? C a t a n l a n n ? k Catanlan_{k-1}\cdot Catanlan_{n-k} Catanlank?1??Catanlann?k?

根据加法原理, 5 5 5 对括号的合法括号序列的个数为 C a t a n l a n 0 ? C a t a n l a n 4 + C a t a n l a n 1 ? C a t a n l a n 3 + … + C a t a n l a n 4 ? C a t a n l a n 0 Catanlan_0\cdot Catanlan_4+Catanlan_1\cdot Catanlan_3+\ldots +Catanlan_4\cdot Catanlan_0 Catanlan0??Catanlan4?+Catanlan1??Catanlan3?++Catanlan4??Catanlan0?

因此,我们推出 n n n 对括号的合法括号序列的个数为 C a t a n l a n 0 ? C a t a n l a n n ? 1 + C a t a n l a n 1 ? C a t a n l a n n ? 2 + … + C a t a n l a n n ? 1 ? C a t a n l a n 0 Catanlan_0\cdot Catanlan_{n-1}+Catanlan_1\cdot Catanlan_{n-2}+\ldots +Catanlan_{n-1}\cdot Catanlan_0 Catanlan0??Catanlann?1?+Catanlan1??Catanlann?2?++Catanlann?1??Catanlan0?

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

有一道洛谷上的题:P1044 [NOIP2003 普及组] 栈,因为卡特兰数的第 n n n 项可以应用于长度为 n 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~

文章来源:https://blog.csdn.net/pyc0705/article/details/135184723
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。