题目
若栈初始为空,元素a,b,c,d依次入栈,且在入栈过程中可任意出栈,则共有 ________ 种不同的合法出栈序列。
若栈初始为空,元素a,b,c,d依次入栈,且在入栈过程中可任意出栈,则共有 ________ 种不同的合法出栈序列。
题目解答
答案
根据栈的特性及卡特兰数公式,对于4个元素,合法出栈序列数为:
\[
C_4 = \frac{1}{5} \binom{8}{4} = 14
\]
具体序列包括:a,b,c,d;a,b,d,c;a,c,b,d;a,c,d,b;a,d,c,b;b,a,c,d;b,a,d,c;b,c,a,d;b,c,d,a;b,d,c,a;c,b,a,d;c,b,d,a;c,d,b,a;d,c,b,a。
答案:14种。