是组合数学中一种常出现于各种计数问题中的数列。

一、简单介绍

卡特兰数是一个数列，其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …
卡特兰数满足如下递推关系：

第二个推导式用于编程实现卡特兰数。

二、应用

代码实现：

#include <iostream>
#include <string>
using namespace std;

int n;
int maxn = 20;

long long f1[20];

long long solve1()
{
	f1[0] = f1[1] = 1;
	cin >> n;
	for (int i = 2; i <= n; ++i)
	{
		for (int j = 0; j < i; ++j)
		{
			f1[i] = f1[i] + (f1[j] * f1[i - j - 1]); // f(n)=f(0)f(n-1)+f(1)f(n-2)+...+f(n-1)f(0)  
		}
	}
	return f1[n];
}