卡特兰数

2024-05-18

算法 / 数论

字数统计: 924 | 阅读时长≈ 4 分钟

性质公式

太神奇辣，卡特兰数

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862…

先放三种推导方法如下

递归推导

公式1

(n>=2)

递推公式

公式2

通项公式

公式3

公式4

如果这个数太大，那么题目可能会要求取模，那么第1种𝑛太大的时候时空太大；第2种在取模运算中万一不小心整除了就凉了；第3种是除法运算，更行不通；唯有第4种,满足取模原则（加减无所谓），且不会出现倍数出错的情况，所以第4种解为最优解；

/数论做法 卡特兰数
//公式1：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll f[20];
int main(){
    int n;
	f[0]=f[1]=1;
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<i;j++)
		{
			f[i] += f[j]*f[i-j-1];
		}
	}
	cout<<f[n];
	return 0;
}

//公式2：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll f[20];
int main(){
    int n;
	f[0]=f[1]=1;
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		f[i] = f[i-1]*(4*i-2)/(i+1);
	}
	cout<<f[n];
	return 0;
}

//公式3：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll c[50][25];
int main(){
	int n;
    cin>>n;
    scanf("%d",&n);
    for(int i = 1; i <= 2*n; i++){
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j < i; j++){
            c[i][j] = c[i-1][j] + c[i-1][j-1];
        }
    }
    cout<<c[2*n][n]/(n+1);
    return 0;
}

//公式4： 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll c[50][25];
int main(){
	int n;
    cin>>n;
    for(int i = 1; i <= 2*n; i++){
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j < i; j++){
            c[i][j] = c[i-1][j] + c[i-1][j-1];
        }
    }
    cout<<c[2*n][n] - c[2*n][n-1];
    return 0;
}

常见题目

常见的特点是：一种操作不能超过另一种，两种操作不能有交集，求这些方案合法数

括号匹配

和进出栈问题是一样的，以括号匹配为例

思路1

给n个（，n个），求有多少个2n长度的括号序列合法

无论对错总数量是即2n个里随便选n个

我们记错(为+1，）为-1

但是有一些错误匹配的情况我们需要排除掉，当错误刚出现，一定有一个特点，就是右括号目前多了一次，比如（））（）（，在遍历到第二个）就停止了，因为出错了

设映射f，f作用是翻转出错序列，每一个括号序列对应的f一定唯一。翻转后，有+1出现4次，-1出现2次的性质，即即2n个里随便选n-1个

总次数就是符合卡特兰数通项定义

思路2

我们可以这样想，假设k是最后一个出栈的数。比k早进栈且早出栈的有k-1个数，一共有h(k-1)种方案。比k晚进栈且早出栈的有n-k个数，一共有h(n-k)种方案。所以一共有h(k-1) * h(n-k)种方案。显而易见，k取不同值时，产生的出栈序列是相互独立的，所以结果可以累加。k的取值范围为1至n，所以结果就为h(n)= h(0)h(n-1)+h(1)h(n-2) + … + h(n-1)h(0)。

二叉树组成

给n个节点，问能组成多少种不同二叉树。

我们可以假设，如果采用中序遍历的话，根结点第k个被访问到，则根结点的左子树有k-1个点、根结点的右指数有n-k个点。k的取值范围为1到n。与上面思路2卡特兰数的递归推导一样