「卡特兰数」是组合数学中一个常在各种计数问题中出现的数列,其对应的序列为:
其通项公式为:
我们可以基于通项公式得出如下递推关系:
下面我们将通过一些经典的题目介绍卡特兰数的基本原理,应用场景及其变式。
我们可以通过「括号匹配」这个问题来了解卡特兰数的基本原理。该题目的描述如下:
对于 n 对括号,其共有多少种合法的匹配方式?
括号的合法匹配方式为:一个左括号对应一个右括号,且左括号必须要在右括号前面出现。为了方便说明,这里将左括号记作 +1,右括号记作 -1,则一个合法序列和一个非法序列可以表示为如下形式:
()(()) -> +1 -1 +1 +1 -1 -1
())()( -> +1 -1 -1 +1 -1 +1
我们可以证明,对于合法序列来说,其「所有前缀和」必然大于等于 0,而对于非法序列来说,其必然存在前缀和小于 0 的情况。下面我们将尝试去推导序列长度为 2n 时非法序列的数量。
对于一个非法序列,我们找到其「第一个」和小于 0 的前缀,并对其中每一位进行取反。以上面的非法序列为例,我们会得到:-1 +1 +1 +1 -1 +1
,此时该序列中共有 3+1
个 +1 和 3-1
个 -1。直观上来看,第一个小于 0 的前缀和必为 -1,即 -1 比 +1 多一个,取反后则 -1 比 + 1 少一个,这样总数上看 +1 必变为 n+1
个,-1 则变为 n-1
个(因为原来二者相等)。我们可以将该结论推广为(严格的证明省略):
对于
n
对括号的每种非法匹配序列 A,都会有一个含有n+1
个 +1 和n-1
个 -1 的序列 B 与其一一对应。
B 的数量我们可以通过
来计算(等价于
),即非法序列的数量为
。而序列的总数量为
(从 2n 个位置中选择 n 个位置放左括号,无先后顺序),因此合法的匹配序列数量为:
此即为卡特兰数的通项公式。
卡特兰数可以应用于很多有趣的组合数学问题,如:
给定
n
个数的入栈顺序,求其有多少种出栈序列?
将进栈看做 +1,出栈看做 -1,则其为一个标准的卡特兰数,对应的结果为
。
对于有
n+1
个叶子节点,其能构成多少种形状不同的满二叉树?
这里的「满二叉树」使用国际定义,即如果一棵二叉树的节点要么是叶子节点,要么有两个子节点,则其为满二叉树。
我们可以证明,包含 n+1
个叶子节点(总节点个数为 2n+1
)需要进行 2n
次扩展来形成满二叉树,如下图所示(月牙形表示叶子节点)。扩展即从父节点向左或向右添加子节点的过程,我们可以将其理解为左右括号匹配问题,则总共可以构成
种形状不同的满二叉树。
此外,上图还可以看做 n
个节点组成不同二叉树的方案数,其中圆形表示节点,月牙形表示什么都没有。我们可以基于卡特兰数的递推关系得出该方案数即为
,具体请参考 Leetcode 第 96 题。
在一个
n*n
的方格中从左下角走到右上角,不穿过对角线的单调路线有多少种?
通过下图我们可以发现,只存在向右走和向上走两种选择,两者的总数需匹配且任意时刻向上走的数量不能多于向右走。很明显这也是一个卡特兰数,对应的单调路线有
种。
将
n
边的凸多边形以不相交的对角线分成n-2
个三角形,共有多少种方法?
这个问题我们需要从递归的角度来考虑。因为凸
边形的任意一条边必定属于某一个三角形,所以我们以某一条边为基准,将这条边的两个顶点分别记作
和
,将该凸多边形的顶点依序标记为
,再在该凸多边形中选择任意一个不属于这两个顶点的顶点
(
),来构成一个三角形,用这个三角形把该凸多边形划分为两个凸多边形,其中一个凸多边形为由
构成的凸
边形,另一个则是由
构成的凸
边形。根据乘法原理,问题的解
等价于凸
边形的划分方案数乘以凸
边形的划分方案数,遍历所有的
,可以得到:
可以看到,对于一个凸
边形来说,其分割方法数即等价于
。下图给出了一个正六边形的分割方案,共有
种。
在实际编程中,这类问题通常可以通过找出递归关系,然后基于动态规划的方式求解。如果可以直接分辨出其为卡特兰数,那么使公式进行求解是一种最快的方法。
下面介绍一种卡特兰数的变式,也是编程面试中常考的一种问题:「买票」问题。
假设一张门票 5 元,售票房没有额外的零钱。现在有
m
个人持有 5 元的纸币,n
个人持有 10 元的纸币排队买票,问有多少种排队方式,可以让每个人都买到电影票。
这道题本质上就是要让持有 5 元纸币的人和持有 10 元纸币的人保持匹配,且 5 元纸币的人需要在前面,如果将持有 5 元纸币的人看做左括号,持有 10 元纸币的人看做右括号,不难理解这就是一个卡特兰数的问题。
然而,与标准卡特兰数相比,这里的求解还有两个不同之处:首先是持有 5 元纸币的人数 m
和持有 10 元纸币的人数 n
不一定相等(注意 m
需要不少于 n
),这样我们不能直接套用卡特兰数的通项公式,而应该从原理出发重新推导,基于「总序列数减去非法序列数」的思想,合法序列数为
。此外,我们还需要考虑排队的先后顺序,因此总的排队方式数为:
注:本篇文章的整体思路与部分内容参考自 LeetCode 上的一篇笔记[1],图片则来自 wiki 百科[2]。
[1]
「算法入门笔记」卡特兰数: https://leetcode-cn.com/circle/article/lWYCzv/
[2]
卡塔兰数: https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0