卡特兰数（计算顺序进栈的出栈情况）

原题链接：牛客网
原题：

该题为组合数学问题，有一段解释我觉得说得很好:

首先，我们设 f(n)=序列个数为n的出栈序列种数。（我们假定，最后出栈的元素为k，显然，k取不同值时的情况是相互独立的，也就是求出每种k最后出栈的情况数后可用加法原则，由于k最后出栈，因此，在k入栈之前，比k小的值均出栈，此处情况有f(k-1)种，而之后比k大的值入栈，且都在k之前出栈，因此有f(n-k)种方式，由于比k小和比k大的值入栈出栈情况是相互独立的，此处可用乘法原则, f(n-k)*f(k-1)种，求和便是Catalan递归式，得到的结果便是卡特兰数。

设h(n)为catalan数的第n项，令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(2)=h(0)h(1)+h(1)h(0)=11+11=2
h(3)=h(0)h(2)+h(1)h(1)+h(2)h(0)=12+11+21=5

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796
题目对应n=5的卡特兰数，为42