六个不同元素依次进栈，能得到 种不同的出栈序列。（北京邮电大学2007年） A．42 B．82 C．132 D．192

这道题可以用卡特兰数的公式解决。

首先，我们可以得到一个结论：对于 $n$ 个元素的栈，它的出栈序列个数为卡特兰数 $C_n$。

证明可以参考以下思路：

我们考虑对于 $n$ 个元素的栈，任选一个元素 $x$，那么 $x$ 要么先被弹出，要么后被弹出。如果 $x$ 先被弹出，那么剩下的 $n-1$ 个元素构成的栈有 $C_{n-1}$ 种出栈序列；如果 $x$ 后被弹出，那么弹出顺序与 $x$ 无关，剩下的 $n-1$ 个元素构成的栈有 $C_{n-1}$ 种出栈序列。所以，对于 $n$ 个元素的栈，它的出栈序列个数为 $C_n=C_{n-1}\times C_{n-1}$。

另外，$C_0=1$，因为空栈也算一种出栈序列。

所以，对于本题，有 $n=6$，根据卡特兰数的公式 $C_n=\frac{(2n)!}{n!(n+1)!}$，我们可以得到答案为：

$$
C_6=\frac{(2\times6)!}{6!(6+1)!}=\frac{12\times11\times10\times9\times8\times7}{6\times5\times4\times3\times2}=132
$$

所以，答案选 C。