卡特兰数

卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名，其前几项为 : 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, ...——来自百度百科

　　这并不是我第一次接触到卡特兰数，这些看起来毫无规律的数其实都有起源

这里公式附上

令h(0)=1,h(1)=1，catalan数满足递推式:

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

另类递推式:

h(n)=h(n-1)*(4*n-2)/(n+1);

递推关系的解为:

h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

递推关系的另类解为:

h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)

关于卡特兰的应用，最概括的来讲就是统计出栈顺序的可能性，当然它的变形有很多很多，有一篇博文写的比较详细——http://blog.csdn.net/duanruibupt/article/details/6869431

最后，是最近刚刚AC的一个题，权当例题了

================================================================================================

华丽丽的分割线

================================================================================================

题目描述 Description

竞赛班的师弟们都很懒，每个人都不喜欢倒垃圾，结果垃圾就会跟师兄的RP一样越堆越多，当然，老师时不时就会叫他们去倒垃圾。由于他们真的很懒，他们只会直接将垃圾桶最上面袋拿去扔。师弟们扔垃圾的时候，会先把垃圾装成袋，然后将垃圾编号，第一袋扔到垃圾桶的垃圾编为①号……掏垃圾的阿伯会清点一下编号的顺序，然后反馈给老师，让老师知道竞赛班高一师弟到底有多懒……【比如：当师弟们扔了3袋垃圾时，得到的编号有可能是123（每一袋扔进垃圾桶时他们就拿去扔，这个编号说明还是有人挺勤劳的），132（第一袋拿出去扔，然后垃圾桶里多扔了第2，3袋之后，他们再从上往下一袋一袋拿去扔）……】而竞赛班某师弟对阿伯倾慕已久，想知道阿伯最后收到的垃圾的顺序有多少种可能，由于他不好好学习科学文化知识，智商有点捉鸡，于是想让你帮他算出来，但你又觉得亲身实践简直蠢到爆，于是，你决定让计算机去做这件事。

如果1s内计算机算不出，那少年，倒垃圾去吧，你太懒了……

输入描述 Input Description

只有一个整数n，表示师弟们总共扔了多少袋垃圾。

输出描述 Output Description

只有一个整数m，表示阿伯掏出垃圾的顺序的总可能结果。

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

时间限制

每个测试点1s

数据范围

对于50%的数据，1≤n≤15

对于100%的数据，1≤n≤35

Hint

垃圾要按时倒啊，没听说过倒垃圾的男人最性感吗？【哪听来的这句话= =】……

35袋垃圾……姚老叫你们不要在机房吃东西听到没有

解题思路

刚开始，我比较懒，用的是h(n)=h(n-1)(n*4-2)/(n+1) 这个公式，但就是有一个点不过

后来我老老实实的敲了第一个公式，就过了。这是为什么呢？因为第二个公式中涉及乘法运算，先乘再除，很有可能会爆掉（什么？你说用实型边除边乘？精度不够）

所以，第二个公式仅适用于n<=34

第二个公式仅适用于n<=34

(重要的事情说三遍)

 1 program tt;
 2 var h:array[0..35] of qword;
 3    n,i,j:Longint;
 4 begin
 5     read(n);
 6     h[0]:=1;
 7     h[1]:=1;
 8     for i:=2 to n do
 9     for j:=0 to i-1 do
10     h[i]:=h[i]+h[j]*h[i-j-1];
11     writeln(h[n]);
12 end.