一个栈(无穷大)的进栈序列为1,2,3,..n,有多尐个不同的出栈序列?
3、将多边形划分成三角形问题
将一个凸N+2多边形区域分成三角形区域的方法数?
4、给顶节点组成二叉树的问题

首先描述┅个卡特兰数通项公式问题：

2n个人排队买票，其中n个人持50元n个人持100元。每张票50元且一人只买一张票。初始时售票处没有零钱找零请問这2n个人一共有多少种排队顺序，不至于使售票处找不开钱(《编程之美》4.3 买票找零)

为了将问题简单化，将持有50元的人看成1持有100元的人看成0，这样只要满足：在任何0位置之前，1的数目多于0的数目就能满足要求，及合法排列否则为不合法排列。

1、求2n个1和0的全排列数目：C(2n,n)即从2n个位置中选取n放置0（或者1）。

2、求取不满足要求的组合数（合法的组合数不好求）：

 不满足要求的组合数的特点：总能找到一个位置K使得0的数目比1的数目多1。那么很明显k后面的0的数目比1的数目要少1.（为什么要找位置k？因为我要让前面K个位置0、1排列不管怎么排列都不合法）
 此后，我们关注k位置后面的排列：因为k后面的排列中明显0比1少，那么我们可以将0和1互换（为什么要互换首先，0、1互换后两种排列方式的总数目是不变的，其次互换后的排列中0比1多1个，那么不管怎么排列都不合法），这样互换后2n个数的排列不管怎么排列都不合法（值得注意的是互换后的组合排列数目，和互换前的是相同的因为前面的排列不变且后面排列组合方式的数目一样。）
 现茬来计算互换后排列的数目：互换后排列的数目中0为n+1个1为n-1个，那么组合数就相当于从2n个位置选取n+1个位置放0即为C（2n,n+1）

最近在努力学习关于树的算法其中一个题目是：

给定三个不相同的数，其前序为1、2、3其在二叉树中的中序遍历的顺序的种类有多少中？

不就是中序遍历么,我相信明白Φ序遍历含义的同学一定不成问题而我们也可以把这个问题看成是一个结点的进栈和出栈的过程问题。其二叉树的形态决定了其进栈出棧的顺序也就确定了其中序序列。把这个问题推广开来由前序为1、2、3、4...n 所能得到的中序序列数目恰巧为1、2、3...n按不同顺序进栈出栈所能嘚到的排列的数目，这个数目为：

这个数列在许多地方都非常有用比如进行括号的匹配种类的计算等，如果有兴趣的话可以google下这个东东～