卡特兰数列(Catalan )_综合

简述

卡特兰数又称卡塔兰数，它是组合数学中一个常出现在各种计数问题中出现的数列，其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, ......

卡特兰数表1-100

公式

1.递归公式1 $f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i-1)$

2.递归公式2 $f(n)=\frac{f(n-1)*(4*n-2)}{(n+1)}$

3.组合公式1 $f(n)=\frac{C_2_n^n}{n+1}$

4.组合公式 2 $f(n)=C_2_n^n-C_2_n^{n-1}$

5.增长趋势 $f(n)\sim \frac{4^n}{?{n^{\frac{3}{2}}}\sqrt{\pi }}$

应用

二叉树的计数：已知二叉树有 n 个结点，求能构成多少种不同的二叉树
括号化问题：一个合法的表达式由()包围，()可以嵌套和连接，如：(())()也是合法表达式，现给出 n 对括号，求可以组成的合法表达式的个数
划分问题：将一个凸 n+2 多边形区域分成三角形区域的方法数
出栈问题：一个栈的进栈序列为1,2,3,..n，求不同的出栈序列有多少种
路径问题：在 n*n 的方格地图中，从一个角到另外一个角，求不跨越对角线的路径数有多少种
握手问题：2n 个人均匀坐在一个圆桌边上，某个时刻所有人同时与另一个人握手，要求手之间不能交叉，求共有多少种握手方法

详细应用解释：This is the link

This is the code

$f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i-1)$

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long cat[50];
long long Cat1(int n)
{memset(cat,0,sizeof(cat));cat[0]=cat[1]=1;for(int i=2;i<=n;++i){for(int j=0;j<i;++j)cat[i]+=cat[j]*cat[i-j-1];}return cat[n];
}
int main()
{int n;scanf("%d",&n);printf("%lld\n",Cat1(n));return 0;
}

$f(n)=\frac{f(n-1)*(4*n-2)}{(n+1)}$

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long cat[50];
long long Cat2(int n)
{memset(cat,0,sizeof(cat));cat[0]=1;for(int i=1;i<=n;++i){cat[i]=((cat[i-1])*(i*4-2))/(i+1);}return cat[n];
}
int main()
{int n;scanf("%d",&n);printf("%lld\n",Cat2(n));return 0;
}

$f(n)=\frac{C_2_n^n}{n+1}$

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long cat[50];
long long tatal;
void Cat3(int n)
{tatal=1;for(int i=0;i<n;++i)//求c(2n,n);tatal=tatal*(2*n-i)/(i+1);tatal/=(n+1);
}
int main()
{int n;scanf("%d",&n);Cat3(n);printf("%lld\n",tatal);return 0;
}

$f(n)=C_2_n^n-C_2_n^{n-1}$

两个公式相当于一个，第一个是用第二个化简来的

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long cat[50];
long long tatal;
void Cat4(int n)
{tatal=1;for(int i=0;i<n;++i)//求c(2n,n);tatal=tatal*(2*n-i)/(i+1);tatal=tatal-tatal*n/(n+1);
}
int main()
{int n;scanf("%d",&n);Cat4(n);printf("%lld\n",tatal);return 0;
}