编号为1,2,3,4,5,6的六个数，顺序压入堆栈，可能的出栈序列有多少种？

作者：kingbirg <kingbirg@163.com>

解：将所有可能的操作过程用op(1,2,...,n)表示。(n=6)

   则op(1,2,...,n)只可能是这样一个序列:

   push 1

   op(2,3,...,k)

   pop 1

   op(k+1, k+2, ..., n)

   这里，k可以是1, 2, ..., n。

   根据数学上的乘法原理，可知op(1,2,...,n)的可能性有：

   count_op(n) = for (k = 1; k <= n; ++k) count_op(k-1)*count_op(n-k);

所以：// 以下count_op简记为op

   op(0) = 1

   op(1) = 1

   op(2) = op(0)*op(1) + op(1)*op(0) = 2

   op(3) = op(0)*op(2) + op(1)*op(1) + op(2)*op(0) = 5

   op(4) = op(0)*op(3) + op(1)*op(2) + op(2)*op(1) + op(3)*op(0) = 14

   op(5) = op(0)*op(4) + op(1)*op(3) + op(2)*op(2) + op(3)*op(1) +

op(4)*op(0) = 42

   op(6) = op(0)*op(5) + op(1)*op(4) + op(2)*op(3) + op(3)*op(2) +

op(4)*op(1) + op(5)*op(0) = 132