题目

栈的基本操作有出栈和入栈。将序列 1,2,3,…,n 依次入栈，回答下列问题：

(1) 当 n=9 时，可以得到出栈序列 {2,3,1,6,4,7,5,9,8} 吗？可以得到出栈序列 {2,3,1,5,6,7,4,9,8} 吗？（2 分）

(2) 假设 1,2,…,n 组成任意序列的出栈序列 P1,P2,…,P**n ，在序列中有 P**i 、 P**j 、 P**k （ i<j<k ），若该出栈序列不能由栈得到，则 P**i 、 P**j 、 P**k 的大小关系是？（2 分）

(3) 若 n=4 ，则以 2 开头的序列个数有多少个？（2 分）

(4) 若 n=k−1 时，出栈序列总共共有 M 个，如果 n=k ，那么以 1 开头的出栈序列个数有多少个？以 2 开头的出栈序列有多少个？总共的出栈序列有多少个？（4 分）