作业帮 > 数学 > 作业

设元素入栈的顺序是1、2、3、…、n ,则所有可能的出栈序列共有( )种.

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/29 08:30:45
设元素入栈的顺序是1、2、3、…、n ,则所有可能的出栈序列共有( )种.
答案: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