GESP 八级 · GESP 202512 C++ 八级 第 22 题

$ n $ 个不同元素依次入栈的出栈序列数与将 $ n $ 个不同元素划分成若干非空子集的方案数相等。

栈是后进先出（LIFO）结构。入栈push，出栈pop。常用于括号匹配、表达式求值、函数调用栈。

注意栈空时执行pop操作会导致下溢（underflow）。C++ STL stack 的 top() 在栈空时行为未定义。

【考点】栈的合法出栈序列（卡特兰数）｜集合划分计数（贝尔数）｜组合恒等式辨析

解题思维：先分别写出 n=1,2,3 时的两个数量——出栈序列数 C_n = 1,2,5，划分方案数 B_n = 1,2,5,15……看到 n=4 时 C_4=14 而 B_4=15，立刻知道两者不可能恒等。命题人故意把两个经典计数公式“偷梁换柱”，让只背结论的学生误以为“都是组合数就相等”。卡特兰数 C_n = 1/(n+1)·C(2n,n)，本质是“括号匹配”或“二叉树”计数；贝尔数 B_n = Σ_{k=1}^{n} S(n,k)，本质是“集合划分”计数。两者增长阶数相差巨大：C_n≈4^n/(n√π)，B_n≈n!/(e log n)。

陷阱拆解：选项 A 把“相等”写成绝对成立，却忽略了卡特兰数与贝尔数的增长阶数不同（C_n≈4^n/(n√π)，B_n≈n!/ (e log n)）。如果只背“n 个元素出栈序列数是卡特兰数”和“划分方案数是贝尔数”就选 A，就是掉进命题人设计的“概念混淆”坑里。即使 n=5 时 C_5=42 而 B_5=52，继续背离，命题人就是要你从 n=1,2,3 的小规模计算中识破“恒等”的假象。

反命题思维：若把“非空子集”改成“有序子集”（即排列），则划分方案数变成 n!，仍与 C_n 不等；若把入栈顺序改成“任意顺序入栈”，合法出栈序列数会变成 2^{n-1}，此时与贝尔数仍不相等。刷到类似题先问“命题人想让你比较哪两种计数模型”。比如把题目改成“n 个不同元素依次入栈，出栈序列数与以 n 个节点为叶子结点的不同二叉树个数是否相等？”答案就是 A 正确——因为两者都是卡特兰数。可见命题人常通过“偷换概念”制造陷阱，解题时务必先拆解计数对象的结构。