Question

n个元素任意依次入栈出栈，共有几种出栈序列

Answer 1

正确答案应是:
2n!
-----------
(n+1)!*n!
即卡塔南数列~~~~
推导过程如下：
不同的出栈序列实际上对应着不同的入栈出栈操作，以1记为入栈，0记位出栈。
则问题实际上是求n个1和n个0构成的全排列，其中任意一个位置，它及它此前的数中，1个个数要大于等于0的个数。
n个1和n个0构成的全排列数为：
（2n）!
--------------
n!
*
n!
排除掉不符合要求的序列，即那些在某时刻出栈数大于入栈数的序列，即得结果。
不符合的序列数为：
（2n）！
----------------
(n+1)!(n-1)!
解释：求不符合要求的序列总数，用到了一个小技巧。在n个0和n个1构成的2n个数的序列中，假设第一次出现0的个数大于1个个数（即0的个数比1的个数大一）的位置为k，则k为奇数，k之前有相等数目的0和1，各为(k-1)/2.
若把这k个数，0换成1，1换成0
，则原序列唯一对应上一个n＋1个1和n－1个0的序列。反之，任意一个由n＋1个1和n－1个0构成的序列也唯一的对应一个这样不合要求的序列。由于一一对应，故这样不合要求的序列数实际上等于有n＋1个1和n－1个0构成的排列数。（关于变换的一一对应，看官可自己琢磨，不再赘言）
故符合要求的数目是：
（2n）!
(2n)!
(2n)!
--------------
－
------------------
=
--------------------
n!
*
n!
(n+1)!(n-1)!
(n+1)!(n)!