出栈序列计数 – 大牛是如何长成的

　　现有一个数列 $S = \{1,2,3,\ldots,n\}$ ，另有一个栈Stack和一个队列Queue，Stack与Queue初始为空。现对S中元素依次进行如下操作：

若Stack为空，则从S中取出一个元素入栈；
若Stack非空，则有两种选择：将栈顶元素弹出并入队，或者从S中取出一个元素入栈；
若S元素已经取完则操作结束，否则执行操作1或2。

　　问最终队列Queue有多少种排列情况？聪明且见识广博的你或许一下子就可以说出答案： $\120dpi \color{red}\frac{C_{2n}^{n}}{n+1}\quad\textbf{or}\quad\frac{\binom{2n}{n}}{n+1}$
　　现在对这个结果进行证明。
　　设1表示入栈操作，0表示出栈操作。那么上面对n个元素的入栈和出栈操作就构成了长度为2n的由0和1组成的序列，其中1和0的个数均为n个，在没有任何限制的情况下，一共有 $C_{2n}^n$ 个这样的序列。但是，这里的01序列是建立在一些列的入栈出栈操作的基础上的，因此就会受到入栈、出栈操作的限制。这里，唯一的限制就是栈为空时，无法进行出栈操作。反映到这个01序列中就是，任意位置之前，0的个数都能比1的个数多。因为有了01序列的总数 $C_{2n}^n$ ，所以为了找出满足条件的序列的个数，只需要找出不符合条件的序列的个数。
　　假设我们现在找到这样一个不符合条件的序列，那么这个序列中一定存在这样一个最小的位置k，k之前1的个数为m，0的个数为m+1。那么k之后1的个数就是n-m，0的个数为n-m-1。现在我们把k后面的01序列进行取反操作，即0变成1、1变成0。此时整个序列中有n-1个1，n+1个0。由构造过程可知，每一个不满足条件的01序列都唯一地对应一个长度为2n、含有n-1个1、n+1个0的序列。有上述变换的逆操作易知，每一个长度为2n、含有n-1个1、n+1个0的序列都唯一地对应一个不满足条件的01序列。而长度为2n、含有n-1个1、n+1个0的序列得个数为 $C_{2n}^{n-1}$ 。最后我们就证明了，满足条件的01序列的个数为：
$\120dpi \color{red} C_n = C_{2n}^{n}-C_{2n}^{n-1} = C_{2n}^{n}-C_{2n}^{n+1} = \frac{1}{n+1}C_{2n}^{n}$
　　这个式子所表示的数列（设为h）叫做卡特兰数（catalan），它具有这样一个特性：
$\begin{array}{rcl}h[0]&=&1 \\h[1]&=&1 \\h[n+1]&=&\sum_{i=0}^n h[i]\cdot h[n-i]\end{array}$
　　还有很多经典问题都可以用卡特兰数来表示，比如矩阵乘法、二叉计数、单调路径等，关于这些问题的原型，请Google之。