若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为多少

Question

若进栈序列为a,b,c,则 通过入出栈操作可能得到的a,b,c的不同排列个数为多少

Answer 1

n个整数依次进栈C(2n)(n)-C(2n)(n-1)
当 n = 5 时
N个元素进栈和出栈,共有n次进栈(记为0)和n次出栈(记为1),结果为一个01串.题目意思就是求有多少种长度为2n的合法01串.这里合法的意思是当前1的累计个数不能超过0的累计个数.答案是从C(2n, n)中减去不合法的数目.不合法的必然在某一奇数位2m + 1上首次出现m + 1个1的累计数和m个0的累计数.此后的2(n - m) - 1位有n - m - 1个1和n - m个0.若把后面这2(n - m) - 1位,01互换,结果为由n + 1个1和n - 1个0组成的01串,即不合法01串对应于一个由n + 1个1和n - 1个0组成的01串.反之,任何一个由n + 1个1和n - 1个0组成的01串,由于1的个数比0的个数多2个,2n为偶数,故必在某一奇数为上出现1的累计个数超过0的累计个数,同样地,在后面把01互换,使之成为n个0和n个1的01串,即n＋1个1和n－1个