卡特兰数(CatalanNumber)

在栈混洗的计数中我们得到了以下公式：

$$SP(n)=\sum_{k=1}^{n}{SP(k-1) \times SP(n-k)}$$

它的结果是著名的卡特兰数，以下选择一种方法求解其通项。

先忽略是否合法,考虑所有情况，即在次操作中任选次入栈，共计种情形。
画一个直角坐标系，轴代表入栈次数，轴代表出栈次数，根据任意前缀中入栈次数不小于出栈次数这一前提，合法序列所得图像应该在直线的下方。

做这样的等价转换：非法折线段唯一对应于终点为(n-1,n+1)的一条连续折线
充分性：
考虑非法的情况，第一次的点落在了直线上，将该点以后所有线段关于该直线对称，那么终点坐标为
必要性：
可以从正反两方面说明，
对于一条终点为(n-1,n+1)的连续折线，必然与有交点，将此后的图像对称即可得到对应的非法序列。
另外，对于任意合法序列，无论怎样对称，保证起点为且终点为的前提下，图像不可能是连续的。
经过以上分析，合法序列数=序列总数-非法序列数，即。
所以，卡特兰数：

$$SP(n)=\sum_{k=1}^{n}{SP(k-1) \times SP(n-k)} \\=C_{2n}^{n}-C_{2n}^{n-1} \\= \frac{(2n)!}{(n+1)!\cdot n!}$$