【题意】

Catalan数列： $1,1,2,5,14,42,132 \dots$（前面几个要背）

即 $h_0=1,h_1=1,h_2=2,h_3=5 \dots$

公式：$h_n=\frac{C_{2n}^n}{n+1}$ （注：$C_5^3$ 表示组合数 5 个数选 3 个的方案数）。

递推公式：$h_n = \frac{h_{(n-1)} * (4 * n-2) } { (n+1) }$

另一种：$h_n = h_{(n-1)} * h_0 + h_{(n-2)} * h_1 + \dots + h_1 * h_{(n-2)} + h_0 * h_{(n-1)}$ ;

【输入格式】

一行一个整数 $n \ (0 \le n \le 50)$ 。

【输出格式】

一行一个整数，即 $h_n$ 。

【样例输入】

5

【样例输出】

42

是不是很简单呀？下面的题也是Catalan数：

1：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票， 剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？

2：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？

3：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?

4：对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数?

5：一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?

6：n个结点可够造多少个不同的二叉树?

7：n个不同的数依次进栈，求不同的出栈结果的种数？

8：n个+1和n个-1构成2n项 a1,a2,...,a2n 其部分和满足a1+a2+...+ak>=0(k=1,2,3,..,2n)的数列的个数等于第n个Catnlan数。

有一次某同学推不出规律，暴力了前面的数据，看着眼熟，于是~~~~知道为什么要背了吧—_—!