Question

N个数依次进栈，出栈共有多少种？

Answer 1

答案:2n!/((n+1)n!n!)
设Bn表示n个元素出栈序列的种数，显然B1=1，
B2=2,如下2种:
1，2
2，1
B3=5,如下5种:
1，2，3
1，3，2
2，1，3
2，3，1
3，2，1
一般地Bn=2n!/((n+1)n!n!)，并满足递推关系
Bn= B0*Bn-1+ B0*Bn-1+…+ Bn-1*B0,其中B0=1

4

Answer 2

结果就是Catalan数，具体怎么算，你baidu一下Catalan数就出来了。