Question

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

若进栈序列为a,b,c,d,e则通过入出栈操作可能得到的a,b,c,d,e的不同排列个数为
A40 B41 C42 D44
求高手详细解

Answer 1

n个整数依次进栈
C(2n)(n)-C(2n)(n-1)
当 n = 5 时
答案是： C
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个0组成的01串对应于一个不合法01串。故两者是一一对应的。故不合法的数目为C(2n, n – 1)