出栈顺序个数之卡特兰数

在数据结构中有个问题：n 个元素进栈，共有多少种出栈顺序？

答案：

分析

可以利用动态规划里面的子问题来进行推导。

把 n 个元素的出栈顺序个数的记为 f(n)：

当 n = 1 时，假设元素是 a，那么出栈顺序只有 ( a )，则 f(1) = 1
当 n = 2 时，假设元素是 a b，那么出栈顺序有 ( a b ) ( b a )，则 f(2) = 2
当 n = 3 时，假设元素是 a b c，那么出栈顺序有 ( a b c ) ( a c b ) ( b a c ) ( b c a ) ( c b a )，则 f(3) = 5

当 n = 4 时, 假设元素是 a b c d，那么：元素 a 结果只可能出现在 1 号位置，2 号位置，3 号位置和 4 号位置。

分析：

如果元素 a 在 1 号位置，那么只可能 a 先进栈且马上出栈，此时还剩 3 个元素等待操作，就是子问题 f(3)
如果元素 a 在 2 号位置，那么一定有 1 个元素比 a 先出栈（只能是 b ），即有 f(1) 种可能顺序。一定有 2 个元素比 a 后出栈，即有 f(2) 种可能顺序，根据乘法原理一共的顺序个数为 f(1) * f(2)
如果元素 a 在 3 号位置，那么一定有 2 个元素比 a 先出栈，即有 f(2) 种可能顺序。一定有 1 个元素比 a 后出栈（只能是 d ），即有 f(1) 种可能顺序，根据乘法原理一共的顺序个数为 f(2) * f(1)
如果元素 a 在 4 号位置，那么在 a 最后出栈前已经有 3 个元素进行了入栈出栈操作，就是子问题 f(3)

结合所有情况，即：

我们定义。于是可以重新写为：

推广到 n，于是我们可以得到：

这就是卡特兰数的递推公式：
$且$

习题：元素 ABCDE 依次入栈，则以下（）是不可能的出栈次序。
A、ABCDE
B、EDCBA
C、BADCE
D、DBCAE
答案：D
解析：看 A 的位置 n，结果中排在 A 左边的元素一定是 A 的后 n - 1 个元素当中的。比如 D 选项：A 在结果中的位置是 4，那么结果中排在 A 左边的元素一定只能是 A 的后 3 个元素（即 B C D）当中的，此时符合。但是还要判断以 A 为界，左右两个子问题是否符合此规律。对于左边子问题 D B C ，同理要看 B 的位置，B 在子问题结果中的位置是 2，结果中排在 B 左边的元素一定只能是 B 的后 1 个元素，即出现在 B 的左边一定只能是 C，所以不符合。
总结：判断原问题是否符合规则，若符合则继续判断子问题是否符合。

通项推导

几何法

可通过折线法求得通项：

要求：有两种操作即入栈和出栈，要求每种操作的总次数一样，且进行第 k 次出栈前必须先进行至少 k 次入栈。

假设：一个人从原点出发，入栈是此人沿右上角 45° 走一个单位（一个单位长为）。出栈是此人沿右下角 45° 走一个单位。

因为有入栈和出栈操作的次数相同的限制，所以最后必将到到达点。

因为有第 k 次出栈前必须先进行至少 k 次入栈的限制，导致走出来的折线不会跨越 x 轴走到这条线上。

折线法-合法走法

如果没有限制第 k 次出栈前必须先进行至少 k 次入栈，只要求两种操作各 n 次，那么其不同折线共有种可能，其中减去不合法的可能就是要求的内容。

折线法-不合法走法

对于任意跨越 x 轴的折线情况，找出第一个与相交的点 k，将 k 点以右的折线根据对称。可以发现终点最终都会从对称到。

我们可以得出所有跨越了 x 轴的折线总数与从到的折线总数相等。

而从到的折线表示的是入栈和出栈的总数是 2n 且出栈的数量比入栈多了 2 次，则出栈 n + 1 次，入栈 n - 1 次。所以其不同折线有或者种可能。

所以合法的折线有种可能。

得证：

代数法

我还不会组合数学，看不明白生成函数！呜呜呜~

典例

汽车胡同加油问题
一个汽车队在狭窄的路面上行驶，不得超车，但可以进入一个死胡同去加油，然后再插队行驶，共有 n 辆汽车，问共有多少种不同的方式使得车队开出城去？
摞碗问题
饭后姐姐洗碗，妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞。一共有n个不同的碗，洗前也是摞成一摞的，也许因为小妹贪玩而使碗拿进碗橱不及时，姐姐则把洗过的碗摞在旁边，问：小妹摞起的碗有多少种可能的方式？
01 序列问题
给出一个 n，要求一个长度为 2n 的 01 序列，使得序列的任意前缀中 1 的个数不少于 0 的个数，有多少个不同的 01 序列?
借书还书问题
在图书馆一共 2n 个人在排队，n 个还《面试宝典》一书，n 个在借《面试宝典》一书，图书馆此时没有面试宝典了，求他们有多少种排队的情形？
高矮排队问题
2n 个高矮不同的人排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种?
单调路径问题
一位大城市的律师在他住所以北 n 个街区和以东 n 个街区处工作，每天他走 2n 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
找零问题
2n 个人要买票价为五元的电影票，每人只买一张，但是售票员没有钱找零。其中 n 个人持有五元，另外 n 个人持有十元，问在不发生找零困难的情况下，有多少种排队方法？
括号匹配问题
n 对括号有多少种合法匹配方式？
凸多边形划分
在一个 n 边形中，通过不相交于 n 边形内部的对角线，把 n 边形拆分为若干个三角形，问有多少种拆分方案？
圆上线段
在圆上选择 2n 个点，将这些点成对连接起来使得所得到的 n 条线段不相交的方法数？
填充阶梯图形
用 n 个长方形填充一个高度为 n 的阶梯状图形的方法个数？
二叉树问题
a) 由 n 个节点构成的二叉树的个数？
b) 有 n + 1 个叶子的二叉树的个数？
c) 先序序列为 a b c d 的不同二叉树个数？

参考文章

n个元素进栈，共有多少种出栈顺序？ - 止战 - 博客园

卡特兰数的证明及其应用 - _Dinosaur_Po - 博客园

卡特兰数（Catalan）公式、证明、代码、典例.-CSDN博客