题目

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

(1) 当 n=9 时，可以得到出栈序列 {2,3,1,6,4,7,5,8} 吗？可以得到出栈序列 {2,3,1,4,6,5,7,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 分）

解析

(1) 出栈序列判定

答案：第一个 {2, 3, 1, 6, 4, 7, 5, 8} 不可以；第二个 {2, 3, 1, 4, 6, 5, 7, 8} 可以。

判定方法：模拟"按 1, 2, 3, ... 顺序入栈，按目标序列要求出栈"的过程，若某一步出栈要的元素不在栈顶就判失败。

序列 1 模拟（输入 1..n 依次入栈）：

操作	栈状态（右为顶）	已出栈
push 1	[1]	—
push 2	[1, 2]	—
pop → 2 ✓	[1]	2
push 3	[1, 3]	2
pop → 3 ✓	[1]	2,3
pop → 1 ✓	[]	2,3,1
push 4	[4]	2,3,1
push 5	[4, 5]	2,3,1
push 6	[4, 5, 6]	2,3,1
pop → 6 ✓	[4, 5]	2,3,1,6
要 pop → 4，但栈顶是 5 ✗	—	—

结论：序列 1 不可由栈得到。

序列 2 模拟——按相同方法逐步推，可以走通至最后 P_8 = 8 出栈，全程无矛盾。具体过程可由读者自行验证（关键点：4 直接出后再 push 5,6，先 pop 6 再 pop 5）。结论：序列 2 可以由栈得到。

(2) 不能由栈得到的序列中 P_i, P_j, P_k 的大小关系

答案：存在 i < j < k 满足 （即 P_i 最大、P_j 最小、P_k 居中），下标递增但值呈"大-小-中"模式。

证明（反证）：若出栈序列出现 i<j<k 满足 （即 ），考察 P_i 出栈那一刻——

• ？不，。所以 P_j 在 1..n 中比 P_i 小，P_j 入栈在 P_i 之前（按 1..n 顺序入栈，小数先入）；
• 既然 P_j 入栈在 P_i 之前，且 P_j 在 P_i 之后才出（因为 i < j），P_i 出栈时 P_j 必在栈中且在 P_i 下方；
• 同样地，，P_k 也是入栈在 P_i 之前。但 ，且 P_k 比 P_j 后出（j < k），所以 P_i 出栈时 P_k 在栈中且在 P_j 上方、P_i 下方。

P_i 出栈后，栈顶是 P_k（不是 P_j，因为 P_k 在 P_j 上方）。要让 P_j 在 P_k 之前出（j < k 意味着 P_j 先出）就违反栈 LIFO——栈顶必先出，即 P_k 应先于 P_j 出栈。矛盾。

用序列 1 验证：{2, 3, 1, 6, 4, 7, 5, 8}。取 i=4, j=5, k=7（1-indexed）：。（4 < 5 < 6）✓——刚好是不可由栈得到的关键三元组。

(3) n = 4 时以 2 开头的出栈序列个数

答案：5 个，分别是 {2,1,3,4}, {2,1,4,3}, {2,3,1,4}, {2,3,4,1}, {2,4,3,1}。

推导：P_1 = 2 意味着已 push 1、push 2、pop 2，当前栈 = [1]，待入 = [3, 4]。从此状态出发的所有合法栈操作：

                [1] | 待入 [3,4]
               /                \
        pop 1 (→ 21..)        push 3 (→ 23..)
        |                     |
       [] | [3,4]            [1,3] | [4]
      /        \             /          \
   ...2,1,3,4  ...2,1,4,3  pop 3      push 4
                             |          |
                           [1] | [4]   [1,3,4] | []
                           /     \      |
                       pop 1   push 4   pop 4,3,1 → 2,4,3,1
                         |       |
                  ..2,3,1,4  ..2,3,4,1

共 5 条到达终点的路径，对应 5 个序列：

#	序列
1	2, 1, 3, 4
2	2, 1, 4, 3
3	2, 3, 1, 4
4	2, 3, 4, 1
5	2, 4, 3, 1

(4) 用 M（n=k−1 时的总数）表达 n=k 的几个数量

设 n 个数依次入栈出栈的合法出栈序列总数为 （恰好是卡特兰数 Catalan number）。题面给定 。

以 1 开头的出栈序列数

答案：M 个。

P_1 = 1 意味着 push 1 后立刻 pop 1，状态变为"栈空 + 待入 2..k"——这正是 n = k − 1 个数（2, 3, ..., k）的独立栈操作问题，序列数 = 。

以 2 开头的出栈序列数

答案：M 个。

P_1 = 2 意味着 push 1、push 2、pop 2，状态：栈 = [1]，待入 = [3, ..., k]，还要再出 k−1 个数。

记 1 在 P_t 位置出栈（）。在 P_1 与 P_t 之间出栈的 t−2 个数必为 {3, ..., t} 中元素（因为 1 在栈底，能出栈的"上层"必是 3..t）；P_t 之后出栈的 k−t 个数是 t+1..k。这两段彼此独立，分别对应 和 种组合。求和：

由卡特兰数卷积恒等式 ，把 代入即得右式 = 。

与 (3) 验证：n = 4 时以 2 开头 = = 5 ✓。

n = k 时的总出栈序列数

答案：。

推导——卡特兰数的递推 与 的比值：

所以 。

直观验证（k=4，M=5）： ✓（卡特兰数 1, 1, 2, 5, 14, 42 ...）。

编者注（生僻术语）：n 个数依次入栈所有合法出栈序列数 = 第 n 个卡特兰数 。这一结果有多种等价模型——括号匹配、不相交弦、二叉树形态、网格路径等。考研只考"出栈序列计数"这一种，记住 、 这几个常用值就能秒应对小 n 题；大 n 用递推 。