先令h(0)=h(1)=1，h(n)=h(0)*h(n-1)+h(1)*h(h-2)...h(n-2)*h(1)+h(n-1)*h(0) (n>=2)
则h(2)=2, h(3)=5, h(4)=14, h(5)=42, h(6)=132, h(7)=429, h(8)=1430, h(9)=4862, h(10)=16796
综上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, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110, 812944042149730764, 3116285494907301262, 11959798385860453492, 45950804324621742364...
由于这样的推导公式太过复杂，数学家们把该公式推导出其他公式，我觉得较为好用的是
h(n+1)=2(2*n+1)/(n+2)* h(n)=(4*n+2)*h(n)/(n+2)，在码的时候用递推就好。
#include<iostream>
#define N 100000
using namespace std;
int h[N],n;
int main()
{cin>>n;h[0]=h[1]=1;for(int i=2;i<=n;++i){int m=i-1;h[i]=(4*m+2)*h[m]/(m+2);}cout<<h[n];
}
经典例题一：自然排序数1，2，3...n在入栈和出栈后共有多少种排序方法？（即出栈后的队伍种类）洛谷p1044
如当n=3时，排序有123，132，231，213，321 五种情况
我们设当前等待入栈的数是k，则前面已有k-1个数已经入栈，有f(k-1)种情况， 还剩下n-k个数未入栈，有f(n-k)种情况，则此时共有f(k-1)*f(n-k)种情况，当k=1，2，3...n时，每次情况相互独立，则n时的总情况数为f(0)*f(n-1)+f(1)*f(n-2)...f(n-1)*f(0)，该式子满足卡特兰公式。
经典例题二：有n个小朋友有5块钱的纸票，另有n个小朋友有10块钱的支票，他们一起去游乐场买5块的门票，但是售票处没有零钱，若要所有小朋友体会到社会的美好，求2*n个小朋友有多少种排队方式？
由题意可知对于在2*n的队伍中第k处的小朋友，若要前面所有小朋友都能不亏地买到票，则前k个小朋友中有5块钱的小朋友数量x比有10块钱的小朋友数量y多，做出如下示例图，则y>=x,是所有情况都在对角线以下，每个点上的数字代表到达此位置时的情况数量
综上可知n=5时，最多有42种情况，满足拉特兰数规律。
经典例题三：叶某从家去公司上班， 在不越过家和公司连线的情况下到达公司，一共有多少种路线情况？
此题类似于上面的例题二，从到达每个点的路线数推出达到最终公司的路线数，满足卡特兰数规律。
经典例题四：给定一个n边形(n>=3)，求若若干条不相交的线将n边形分成多个三角形，一共有多少种分法？
当n=6时，有如下14种情况
且当n=5时，有5种，n=4有2种，综上满足卡兰特数规律。
经典例题五：一个有n个结点的二叉树，有几种不同的二叉树？
如上当n=3时，有5种情况满足卡特兰数规律、
以上部分转载自(23条消息) 卡特兰数(Catalan)及其应用_ZkvIA的博客-CSDN博客_卡特兰数的应用
https://blog.csdn.net/doc_sgl/article/details/8880468?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164860193716782089336861%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164860193716782089336861&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-2-8880468.142%5Ev5%5Epc_search_result_cache,143%5Ev6%5Econtrol&utm_term=%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0&spm=1018.2226.3001.4187