卡特兰数列是组合数学中在各种计数问题中常出现的数列，其前几项为1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012……
卡特兰数首先是由欧拉在计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，即在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数用Hn表示，Hn即卡特兰数。
01、卡特兰数的公式
- 递归公式1
- 递归公式2
- 组合公式1
- 组合公式2
02、卡特兰数的应用
(1)二叉树的计数:已知二叉树有 n 个结点,求能构成多少种不同的二叉树?
(2)括号化问题:一个合法的表达式由()包围,()可以嵌套和连接,如(())()也是合法的表达式,现给出 n 对括号,求可以组成的合法表达式的个数。
(3)划分问题:将一个凸 n +2 多边形区域分成三角形区域的方法数。
(4)出栈问题:一个栈的进栈序列为 1 , 2 , 3 ,…, n ,求不同的出栈序列有多少种?
(5)路径问题:在 n*n 的方格地图中,从一个角到另外一个角,求不跨越对角线的路径数有多少种?
(6)握手问题: 2n个人均匀坐在一个圆桌边上,某个时刻所有人同时与另一个人握手,要求手之间不能交叉,求共有多少种握手方法?
03、卡特兰数的实现
- n≤35的卡特兰数的实现
- n<100的卡特兰数的实现
04、实例解析：小涛叔叔的礼物
小涛的叔叔旅游回来给他带回一个礼物，小涛高兴地跑回自己的房间，拆开礼物一看是一个棋盘，小涛有所失望。不过，没过几天小涛就发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小涛想知道如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?请帮助小涛解决一下这个问题。
输入:
每次输入一个整数n(1≤n≤35)，当n=-1时结束输入。
输出:
对于每个输入数据,输出路径数，具体格式看样例输出。
输入样例:
1
3
12
-1
输出样例:
1 1 2
2 3 10
3 12 416024
思路: 满足卡特兰数列递推公式，打表即可。
参考程序:
