1.卡特兰数
C0 = 1,
C1 = 1, C2 = 2, C3 = 5, C4 = 14, C5 = 42,
C6 = 132, C7 = 429, C8 = 1430
递推式1:
f[n]=f[0]∗f[n−1]+f[1]∗f[n−2]+…+f[n−1]∗f0

递推式2：
h[n]=h[n−1]∗(4∗n−2)/(n+1)

递推式3：也叫组合数公式
h[n]=C[2n,n]/(n+1)(n=0,1,2,…),C是组合数
PS:C[m,n]=C[m−1,n−1]+C[m−1,n] 且规定：C[n,0]=1 C[n,n]=1 C[0,0]=1

递推式4：也叫组合数公式
h[n]=C[2n,n]−C2n,n−1

应用：
‘3.1044 [NOIP2003 普及组] 栈’ 出栈的顺序个数

建立数组f。f[i]表示i个数的全部可能性。
f[0] = 1, f[1] = 1; //当然只有一个
设 x 为当前出栈序列的最后一个，则x有n种取值 （总共有n个数，每个数都有可能最后出栈）

由于x是最后一个出栈的，所以可以将已经出栈的数分成两部分
比x小 比x大

比x小的数有x-1个，所以这些数的全部出栈可能为f[x-1]（因为入栈序列是1，2，3…n）
比x大的数有n-x个，所以这些数的全部出栈可能为f[n-x]

这两部分互相影响，所以一个x的取值能够得到的所有可能性为f[x-1] * f[n-x]
另外，由于x有n个取值，所以

ans = f[0]f[n-1] + f[1]f[n-2] + … + f[n-1]*f[0];