Question

有n个入栈元素依次进栈，则有多少种出栈序列

Answer 1

你的问题的答案为2的n-1次方个。
根据你的问题可以转换为：1,2,3,4，n。这n个数字依次按从小到大的顺序入栈，那出来的序列有多少种。
已经验证
当n=1时，有1种，
当n=2时，有2种，
当n=3时，有4种，
当n=4时，有8种,

根据规律可以推算出：y（n）=2^(n-1)。
证明：当n≥1时
通过观察可以得到
式1：y(n)=y（n-1）+y（n-2）+y（n-3）+.+Y（1）+1
式2：y(n-1)=y（n-2）+y（n-3）+.+Y（1）+1
那么y(n)-y(n-1)=y（n-1）
也就是y(n)=2*y（n-1）
那么y（n）=2^(n-1)*y(1),
因为y（1）=1，那么y（n）=2^(n-1)。