Question

一个栈的输入序列是12345，则输出序列有多少种，这类题型有什么规律？

Answer 1

可以把这个问题描述为一个二元组表示进栈出栈的状态，(n,
0)
表示有n个元素等待进栈,
0
个元素已进栈,
这相当于问题最初的状况.
接着问题转化为(n-1,1).
可以这么说(n,0)
=
(n-1,1).
而对于(n-1,1)则相当于(n-1,0)+(n-2,2).
其中(n-1,0)表示栈中的一个元素出栈,
(n-2,
2)表示又有一个元素入栈.也就是说，对于(n-1,1)，已经有1个进栈的情况，这时候有两种可能：①把栈里面的这个元素出掉，②继续把一个元素进栈，这两种选择导致的序列是不同的，这个是理解的难点和关键点。
这样我们得到了转化公式，把问题一般化，则(n,m)的排列问题可以转化为(n,m-1)+(n-1,m+1)
此时m>=1,
因为必须栈中有元素才可以出栈.
当m=0则(n,0)的问题只能转化为(n-1,1).
当问题为(0,
m)时得到递归边界,这个问题的解是只有一种排列.
最终推导的结果是：P2n
＝
C（n
2n）—
C（n＋1
2n）=C（n
2n)/(n+1)
这个结果是一个“卡塔兰数”Catalan，在组合数学中有介绍，可以参阅有关资料。
结果=C(5,10)/6=
42
3个元素的情况参考下这个输入ABC的例子，可能比较直观。