浅谈卡特兰数 (Catalan数)
卡特兰数的定义
卡特兰数是组合数学中一个常在各种计数问题中出现的数列。
卡特兰数的一般项公式为
Cn=1n+1(2nn)=(2n)!n!(n+1)!(n∈N)还有以下常见公式 (n∈N)
C0=1, C1=1Cn=n∑i=1Ci−1Cn−i,n≥2Cn=(4n−2)Cn−1n+1Cn=(2nn)−(2nn−1)这张表很重要。因为有时候想不出来可以手推前几项猜卡特兰数。
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ⋯ |
---|---|---|---|---|---|---|---|---|
Cn | 1 | 1 | 2 | 5 | 14 | 42 | 132 | ⋯ |
我们可以用如下代码计算卡特兰数的第 n 项(改不了C++行末分号的习惯了)
n = int(input());
if(n == 0 or n == 1): print(1); exit(0);
fac = [0 for i in range(2*n+5)]; fac[0]=1;
for i in range(1, 2*n+1): fac[i] = fac[i-1] * i;
print(fac[2*n] // (fac[n] * fac[n+1]))
卡特兰数的应用
有好多,这里就列举几个常见的。
1. 合法括号序列(Dyck word)
Cn 表示长度为 2n 的合法括号序列的个数。
注:a Dyck word is a balanced string of square brackets
[
and]
.Dyck word是一个有 n 个
X
和 n 个Y
组成的字串,且所有的前缀字串皆满足X
的个数大于等于Y
的个数。以下为长度为 6 的 Dyck words
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
2. n×n 的格点中不越过对角线的单调路径
Cn 表示所有 n×n 的格点中不越过对角线的单调路径的个数。
一个单调路径从格点左下角出发,在格点右上角结束,每一步均为向上或向右。
计算这种路径的个数等价于计算Dyck word的个数:X
代表“向右”,Y
代表“向上”。
以下为 n=4 的情况
3. n 个结点的不同构二叉树
Cn 表示 n 个结点的不同构有根二叉树(无标号)的个数。
以下为 n=3 时的情况:
Cn 也能表示 2n+1 个结点的不同构有根满二叉树(无标号)的个数。
以下为 n=3 时的情况。
这里的满二叉树采用国外的定义。
国外定义:树上任何结点,如果不是叶子结点,则一定有 2 个儿子。
国内定义:2k−1 个结点,第 i(i≥1) 层有 2i−1 个结点。
4. 分割凸多边形
Cn 表示通过连结顶点而将 n+2 条边的凸多边形分成三角形的方法个数
下图为 n=4 的情况
5. 高度为 n 的阶梯状图
Cn 表示用 n 个长方形填充一个高度为 n 的阶梯状图形的方法个数
下图为 n=4 的情况
参考文献:
[1] https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
[2] https://en.wikipedia.org/wiki/Dyck_language
[3] https://en.wikipedia.org/wiki/Catalan_number