卡特兰数应用--n个元素的出栈顺序与从(0,0)到(n,n)不穿过对角线的方法数

1.出栈顺序方法数：

hdoj1023

求出栈序列，比如1,2,3，出栈序列为3 2 1,1 2 3,1 3 2,2 1 3,2 3 1,一共5种

第一种思路：

我们把入栈看做1，出栈看做0，那么入栈出栈看做一系列的1010。。。，但是必须保证从左往右
看的时候1必须多余0，这个是卡塔兰数的第二个应用，种数为：C(n,2n)-C(n+1,2n).
粗略这样理解：我们从2n个位置中选出n个来存放1，方法数为C(n,2n),减去不满足的情况。
不合法的情况：我们在2n个位置放n+1个0，n-1个1，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数，即C（n+1,2n）。

比如：对于数列10101001010100， 在第7个位置上首先出现了0比1多的情况，而在后面的数列中0的总计数还是比1的总计数多1（n+1个0， n-1个1）。如果把后面数列的0和1互换，那么整个数列就能够保证0和1的计数是相等的。同时对应了一种不符合要求的排列方法：10101000101011.

所以总的方案数为：h(n)=C(n,2n)-C(n+1,2n).

第二种思路：

这种方法直接来源于卡特兰数3的递推公式：h(n) = h(0) * h(n- 1) + h(1) * h(n - 2) + ... + h(n - 1) * h(0)

令f(n)为n个字符的出栈序列的方法数

假设在出栈序列中，在数1在第k个位置出栈，则之前有k-1个字符已经出栈，后面还有n-k个字符未出栈，那么在这种情况下出栈方案数为f(k-1)*f(n-k), k = 1, 2, 3, ...,n

f(0) = 1, f(1) = 1

那么f(n) = f(0) * f(n - 1) + f(1) * f(n - 2) + ... + f(n - 1) * f(0) = h(n)

第三种思路：

使用折现法，这种方法与从(0, 0)到坐标(n ,n)不通过对角线的方法数有异曲同工之妙，具体见：http://blog.sina.com.cn/s/blog_6917f47301010cno.html

2.从(0,0)到(n,n)不穿过对角线的方法数

hdoj2067

给出一个棋盘n*n，求从左下角到右上角的不经过对角线的所有走法，这个经过分析也是卡特兰数。我们把往右走看做1，把往上走看做0，那么从左向右看做一系列的101100.。。，和那个求出栈序列的就是一个问题了，即0的个数不能超过1，由于上半角和下半角一样，所以求出来卡特兰数*2就是我们的答案了。

同样可以使用对称的方法求解:

对于不能接触对角线的方法数的解法为：由于不接触对角线，那么第一步一定走向(1, 0), 倒数第二步的位置一定是(n, n - 1)。那么总的方法数为：C(n - 1, 2n-2)。之后需要减去接触对角线的方法数：如果我们从(0, 1)出发，到达(n, n -1)的路径一定会接触对角线，而这样的路径和从(1, 0)到(n, n -1)不合法的路径是一一对应的的（可以把它从最后离开对角线的点到(1, 0)做一个关于y=x的对称），那么总的方法数为2 * (C(n- 1, 2n - 2) - C(n, 2n - 2)) = 2 * h(n - 1)种方法

对于可以接触但不能穿过对角线的解法为：不能穿过y=x，等价与不能接触y=x+1，所以，从(0, 0) 到(n, n)的总方法数为C(n, 2n)，之后减去不符合要求的方法数。将(0, 0)关于y=x+1做对称可得到点(-1, 1)，从(-1, 1)到点(n, n)必定接触y=x+1，方法数为C(2n - 1, 2n)。所以符合要求的方法数为：C(n, 2n) - C(2n - 1,2n) = C(n, 2n) - C(2n + 1,2n) = h(n)

这两种问题通过卡特兰数可以很容易地解决，可以看我转的一篇文章：blog.csdn.net/u014097230/article/details/44244793