简介
卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为（从第零项开始） :
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, …
卡特兰数 Cn 满足以下递推关系
h(n) = h(0)*h(n-1) + h(1)*h(n-2) + … + h(n-1)*h(0) (n>=2)
来自百度百科.
代码
#include<bits/stdc++.h>
using namespace std;long long Catalan(int n)
{long long a[100];a[0]=1;for(int i=1;i<=n;i++){a[i]=a[i-1]*(4*i-2)/(i+1);}return a[n];
}int main()
{int n;while(1){long long ans;scanf("%d",&n);ans=Catalan(n);cout<<ans<<endl;}return 0;
}例题
Catalan数实际上用在很多个问题上，它的应用很巧妙，并且大都是成对出现的
-
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
f ( 2n ) =h ( n ) -
n对括号正确匹配数目
给定n对括号，求括号正确配对的字符串数
f ( 2n ) =h ( n ) -
2 n 个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？
f ( 2n ) =h ( n ) -
门票找钱问题
有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？
f ( 2n ) =h ( n ) -
对于集合{1,2,3…2n}的不交叉划分的数目为多少？
我们将每个子集中较小的数用左括号代替，较大的用右括号代替，那么带入原来的1至2n的序列中就形成了合法括号问题
f ( 2n ) = h ( n ) -
一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
或者说在n*n的格子中，只在下三角行走，每次横或竖走一格，有多少中走法？
f ( 2n ) = h ( n )
-
n个长方形填充一个高度为n的阶梯状图形的方法个数？
f ( n ) =h ( n )
-
在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？
f ( 2 n ) = h ( n )
-
给定节点组成二叉搜索树
给定N个节点，能构成多少种不同的二叉搜索树？
或者说有n+1个叶子的满二叉树的个数？
（能构成h（N）个）（这个公式的下标是从h(0)=1开始的）
f ( n ) = h ( n )
-
凸多边形三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f（6）=14 = h ( 4 )
即 ,f ( n ) = h ( n-2 )
-
乘积重组问题
矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
f ( n ) =h ( n - 1 )
