将序列 $a_1,a_2,\ldots a_n$ 入栈、出栈, 共有多少种可能方式?
将序列 $a_1,a_2,\ldots a_n$ 入栈、出栈, 共有多少种可能方式?
实验: 对于输入的序列, 比如 $1,2,3,\ldots,n$, 输出所有入栈、出栈的可能序列.
我们列出出栈的序列.
例如:
当一个数时, 只有一种方式. $a_1$
当 $n=2$ 时, 有 $a_1,a_2$ 和 $a_2,a_1$ 两种出栈序列.
当 $n=3$ 时, 有 5 种.
\[
\begin{array}{ccc}
a_1 & a_2 & a_3,\\
a_1 & a_3 & a_2,\\
a_2 & a_1 & a_3,\\
a_2 & a_3 & a_1,\\
a_3 & a_2 & a_1,\\
\end{array}
\]
当 $n=4$ 时, 有 14 种.
按一次进入的个数来进行分类
至少有14种。
(1) 全进之后再出情况，只有 1 种：$a_4,a_3,a_2,a_1$.
(2) 进3个之后再出的情况，有 3 种: $a_3,a_4,a_2,a_1$, $a_3,a_2,a_4,a_1$, $a_3,a_2,a_1,a_4$.
(3) 进2个之后再出的情况，有 5 种: $a_2,a_4,a_3,a_1$, $a_2,a_3,a_4,a_1$, $a_2,a_1,a_3,a_4$, $a_2,a_1,a_4,a_3$, $a_2,a_3,a_1,a_4$.
(4) 进1个之后再出的情况，有 5 种: $a_1,a_4,a_3,a_2$, $a_1,a_3,a_2,a_4$, $a_1,a_3,a_4,a_2$, $a_1,a_2,a_3,a_4$, $a_1,a_2,a_4,a_3$.
当 $n=5$ 时,
(1) 全进之后再出情况，只有 1 种
(2) 进4个之后再出的情况，有 4 种:
(3) 进3个之后再出的情况，有 9 种:
(4) 进2个之后再出的情况，有 14 种
(5) 进1个之后再出的情况，有 14 种
总共有 42 种.
一般的, 证明有 $\frac{1}{n+1}\binom{2n}{n}$ 种可能. (这个数实际上就是 Catalan 数)
Hint. 不过上述思路对于证明并没太大有帮助, 应该考虑第 1 个入栈元素第 $i$ 个出栈的种类数.