已知\(n\个数的入栈序列，求一共有多少种出栈序列
解法一：
假设我们有\(4\个数\(a,b,c,d\, 我们来看\(a\的出栈顺序。
假设\(a\第二个出栈，那么\(a\的前面有\(1\个数已经出栈，后面还有\(2\个数没有出栈，因此方法数为\(f(1 * f(2\。
同理，\(a\第四个出栈的方法数为\(f(3\。
对于\(n\来推广一下，可以得到：\(f(n=\sum_{i=1}^{n}f(i - 1*f(n-i\。
解法二：
首先来限定一些条件，一个合法的序列\(0\和\(1\的数量一定是相等的。并且序列的前缀和一定是不小于\(0\的。
假设我们有一个序列\(1,-1,-1,1,-1,1\，这里在第三个下标，我们发现了它的前缀和小于\(0\，因此它不合法。再来推广一下，在这所有\(C^{\ n}_{2n}\个序列中，不合法的序列它的前缀和一定在某一处小于\(0\。
现在再来进行推广，我们截取的不合法序列段(从开头到不合法前缀和下标，这一段中的\(-1\一定比\(+1\多一个，那么将这一段取反后所得到的总序列中的\(+1\一定比\(-1\多一个。
最后，合法的序列数为：\(C^{\ n}_{2n}-C_{2n}^{n+1\ or\ n-1}\。
因为感觉这种解法非常的巧妙，因此想写篇博客来总结一下。