设元素入栈的顺序是1、2、3、…、n ,则所有可能的出栈序列共有几种,求详细解析啊!

来源：学生作业帮编辑：搜搜做题作业网作业帮分类：数学作业时间：2024/04/19 13:09:08

设元素入栈的顺序是1、2、3、…、n ,则所有可能的出栈序列共有几种,求详细解析啊!
我做了一天了,还是没有头绪,那位高手能够指点指点,感激不近啊!

这个递归公式很难推导,不过用计算机却很容易计算.做一个有效映射就可以了.
画一个坐标,然后允许的走法是向上或者向右,（向上对应出栈,向右对应入栈）这样就保证了y总是小于等于x,
然后(0,0)代表没有元素,有一种,（n,0)肯定也是一种,就是全部入栈,也就对应全部出栈.
对于任意一点(n,n),其走法应该是来自于(n,n-1) 没有左边过来的走法,对于其他的,总有左边过来的走法和下面过来的走法.
所以最终我得到的序列（从0个元素开始)是 1,1,2,5,14,42,132,429,...
这个就是卡特兰数,计算公式是C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!)
当然,对于计算机来说,直接用递推法也可以,递归需要注意子问题的重复求解,需要采用记忆法.否则时间复杂度会很大

设元素入栈的顺序是1、2、3、…、n ,则所有可能的出栈序列共有几种,求详细解析啊! 若已知一个栈的入栈顺序是1,2,3,...,n,其输出序列为P1,P2,P3,...,Pn,若P1是n,则Pi是若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i,则第j个输出元素是_____. 若一个栈的入栈序列是1,2,3,…n,其输出序列为P1,P2,P3,…Pn,若P1是n,则Pi是（）设已将元素a1,a2,a3依次入栈,元素a4正等待进栈.那么下列4个序列中不可能出现的出栈序列是（）有5个元素5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列? 有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?（）请问:有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列? 已知一个栈的进栈序列是1,2,3……n;其出栈序列是p1,p2,p3,……pn;若p1=n,则pi是若已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,p3,…,pn,若p1=3则p2为什么可能是2,而不设有n个元素进栈的序列为1,2,3.,n,其输出序列是p1,p2,p3.pn,若p1=3,则p2的值是? 1.设集合序列{1},{2,3}, {4,5,6}, {7,8,9,10}……设SN是第N个集合的元素总合,则S21=