跳转至

卡特兰数

引入

Catalan 数经常出现在各类计数问题中。比利时数学家 Eugène Charles Catalan 在 1958 年研究括号序列计数问题时发现了这一数列,它也因此得名。清朝数学家明安图早在 18 世纪 30 年代就已经发现这一数列。

Catalan 数满足如下递推关系:

(1)Cn={1,n=0,i=0n1CiCn1i,n>0.

数列的前几项为:(OEIS: A000108,下标从 0 开始)

1,1,2,5,13,42,132,429,1430,

应用

Catalan 数 Cn 的递推关系有着天然的递归结构:规模为 n 的计数问题 Cn,可以通过枚举分界点,分拆为两个规模分别为 i(n1i) 的子问题。这一递推关系使得 Catalan 数广泛出现于各类具有类似递归结构的问题中。

  • 路径计数问题:有一个大小为 n×n 的方格图,左下角为 (0,0),右上角为 (n,n)。从左下角开始,每次都只能向右或者向上走一单位,不走到对角线 y=x 上方(但可以触碰)的情况下,到达右上角的路径总数为 Cn

    证明

    设方案数为 Tn。考虑 n2 的情况。设路径 第一次 走到对角线 y=x 的点是 (k,k) (k[1,n])。考察从 (0,0)(k,k) 的除起点和终点外,中间的点 不经过对角线(不能碰到) 的路径。

    catalan2

    如图所示,这些路径的第一步一定向右,从 (0,0)(1,0);最后一步一定向上,从 (k,k1)(k,k)。因此,这些路径就是从 (1,0)(k,k1) 的不越过直线 y=x1 的路径,这样路径的数目就是 Tk1。同时,从 (k,k)(n,n) 的合法路径数就是 Tnk。根据乘法原理,第一次在 (k,k) 处触碰对角线的路径数目为 Tk1Tnk。枚举 k 的所有可能性,所有合法路径的数目为

    Tn=k=1nTk1Tnk.

    做代换 k=i+1 就可以发现,这就是 Catalan 数的递推关系。由 T0=1 可知 Tn=Cn

  • 圆内不相交弦计数问题:圆上有 2n 个点,将这些点成对连接起来且使得所得到的 n 条线段两两不交的方案数是 Cn

    证明

    2n 个点的方案数为 Tn。将 2n 个点按顺时针标号,分别为 1,2,,2n。由于弦两两不交,1 号点只能连接偶数号点;否则,两点之间的奇数个点无法在不穿过两点连线的情况下两两配对。如果连接了 12k (k[1,n]),那么左边有 2k2 个点,右边有 2n2k 个点,由乘法原理,这样的方案数为 Tk1Tnk。因此,枚举 k,有 Tn=k=1nTk1Tnk。令 k=i+1,就得到 Catalan 数的递推关系。由 T0=1 可知 Tn=Cn

  • 三角剖分计数问题:对角线不相交的情况下,将一个凸 (n+2) 边形区域分成三角形区域的方法数为 Cn

    证明

    (n+2) 边形三角剖分的方案数为 Tn。先选定一条边 (1,n+2) 作为基边,它一定属于一个三角形,记该三角形的第三个点为 k (k[2,n+1])。这样,原凸多边形变成了三个部分:

    • 三角形 (1,k,n+2)
    • k 边形,顶点 1k
    • (n+3k) 边形,顶点 k(n+2)

    后面两个部分都是子问题,所以,有递推关系

    Tn=k=2n+1Tk2Tn+1k.

    k=i+2,就得到 Catalan 数递归关系。由 T0=T1=1 可知 Tn=Cn

  • 二叉树计数问题:含有 n 个结点的形态不同的二叉树数目为 Cn。等价地,含有 n 个非叶结点的形态不同的满二叉树数目为 Cn

    证明

    n 个结点的二叉树数目为 Tn。任取一个根结点,枚举左右子树大小。设左子树大小为 i[0,n1],则右子树大小为 (n1i)。左右子树均为子问题,所以,有递推关系

    Tn=i=0n1TiTn1i.

    这就是 Catalan 数递推关系。由 T0=T1=1 可知 Tn=Cn

  • 括号序列计数问题:由 n 对括号构成的合法括号序列数为 Cn

    证明

    联系路径计数问题。将左括号视为向上走,右括号视为向右走。合法括号序列即为,在任意位置,左括号的数量不少于右括号的数量。相当于路径计数问题中,在任意时刻,向上走的次数不少于向右走的次数。因此,合法括号序列与合法路径之间存在双射。合法括号序列的数目同样为 Cn

  • 出栈序列计数问题:一个栈(无穷大)的进栈序列为 1,2,3,,n,合法出栈序列的数目为 Cn

    证明

    联系括号序列计数问题。将入栈视为左括号,出栈视为右括号。任意时刻,入栈的次数不少于出栈的次数。因此,合法出栈序列与合法括号序列之间存在双射。合法出栈序列的数目同样为 Cn

  • 数列计数问题:由 n+1n1 组成的数列 a1,a2,,a2n 中,部分和满足 a1+a2++ak0 (k=1,2,3,,2n) 的数列数目为 Cn

    证明

    联系括号序列计数问题。将 +1 视为左括号,1 视为右括号。任意时刻,+1 的数量不少于 1 的数量。因此,合法数列与合法括号序列之间存在双射。合法数列的数目同样为 Cn

尽管这一递推关系应用广泛,但是直接计算复杂度较高,需要寻找更为简单的公式。

常见形式

Catalan 数有如下常见的表达式:

(2)Cn=1n+1(2nn)=(2n)!n!(n+1)!, n0. (3)Cn=(2nn)(2nn+1), n0. (4)Cn=(4n2)n+1Cn1, n>0, C0=1.

Catalan 数的这些形式都可以高效计算:前两个形式将它转换为阶乘和组合数的计算问题,第三个形式则提供了顺次计算的递推公式。

对于这三种常见形式,本文提供两种证明方式。

代数推演

通过代数方法得出 Catalan 数的上述表达式共两步。首先,验证三个形式相互等价。

证明表达式 (2)(4) 等价

只需要证明表达式 (3) 可以转化为表达式 (2) 中阶乘形式:

Cn=(2nn)(2nn+1)=(2n)!n!n!(2n)!(n1)!(n+1)!=(2n)!n!n!(1n!(n1)!(n+1))=(2n)!n!n!(1nn+1)=(2n)!n!(n+1)!.

以及,表达式 (4) 也可以转化为表达式 (2) 中阶乘形式:

Cn=i=1n(4i2)i+1=i=1n2i(2i1)i(i+1)=(2n)!n!(n+1)!.

因此,三个表达式互相等价。

紧接着,验证这些形式确实是 Catalan 数递推公式的解。为此,考虑使用生成函数方法直接求出递推公式 (1) 的解。

利用生成函数方法求解递推公式 (1)

考虑 Catalan 数的普通生成函数 C(x)=n=0Cnxn。由于 Catalan 数的递推关系和卷积形式很相似,所以考虑用卷积构造 C(x) 的方程:

C(x)=n=0Cnxn=1+n=1(i=0n1CiCni1)xn=1+xn=1i=0n1CixiCni1xni1=1+xi=0Cixij=0Cjxj=1+xC2(x).

其中,倒数第二个等号交换了求和次序,并令 j=n1i。由此,解得:

C(x)=1±14x2x=2114x.

由初值条件 C0=1 可知,C(0)=1。代入检验可以发现唯一可行的解就是

C(x)=114x2x.

接下来,需要将它展开为幂级数的形式。利用 (1+x)a幂级数展开式 可知:

14x=n=0(12)nn!(4x)n,

其中,(12)n 是下降阶乘幂:

(12)n=k=0n1(12k)=12nk=1n1(12k)=(1)n12nk=1n1(2k1)=(1)n122n1k=1n1(2k1)2kk=(1)n122n1(2n2)!(n1)!.

代入 C(x) 的表达式,就有

C(x)=12x(1n=0(12)nn!(4x)n)=12xn=1(4x)nn!(12)n=12xn=1(4x)nn!(1)n122n1(2n2)!(n1)!=n=1(2n2)!(n1)!n!xn1=n=0(2n)!n!(n+1)!xn.

由此,就得到 Cn 的表达式 (2)

组合意义

由于 Catalan 数具有明显的组合意义,所以只使用组合计数方法同样可以证明这些形式。本节为三个表达式分别提供一个组合意义的证明。

表达式 (2) 的证明

考虑 数列计数问题。对于任意由 ±1 组成的序列 {ai}i=12n,定义它的部分和为 Si=j=1iai,并定义它的 超额量(exceedance)为 Si<0ai=1 的下标数量。超额量为 0,就等价于数列合法;超额量的取值范围是 [0,n],共 (n+1) 种可能的取值。需要证明的是,不同超额量的数列数量其实是一样的。

为此,可以构造一个从超额量为 e>0 的数列到超额量为 (e1) 的数列的映射 f。对于超额量为 e>0 的序列 {ai},取下标 k 为使得 Si=0ai=+1 成立的下标最小值。将 ak 左右两侧的序列交换,就得到如下序列 {ai}

ak+1,ak+2,,a2n,ak,a1,a2,,ak1.

由于原序列中 ak 右侧部分在交换前后对应的部分和序列不变,所以它们贡献的超额量也不变。对于原序列中 ak 左侧部分,它们对应的部分和在交换后全部增加 1,因此,它们贡献的超额量会减少,而且减少的数量恰好等于原序列 ak 左侧部分中满足 Si=1ai=1 的下标数量。因为 ak 的选取保证了这样的下标有且仅有一个,所以,序列 {ai} 的超额量就等于 (e1)。也就是说,映射 f 可以将序列的超额量恰好减少 1

映射 f 是可逆的。注意到序列 {ai} 中,ak 对应的位置恰好为满足 Sk=+1ai=+1 的下标最大值。这是因为交换后,这些部分和都比交换前对应的部分和恰好大 1,因此,现在的部分和为 +1 对应交换前部分和等于 0。但是,根据 k 的选取,交换前这一部分(即原序列 ak 左侧部分)是没有满足 Si=0ai=+1 成立的下标的。

由此,映射 f 构成了超额量为 e>0 的序列和超额量为 (e1) 的序列之间的双射。这就说明,不同超额量的数列数量其实是一样的。由于数列总数是 (2nn),合法数列(即超额量为 0 的数列)数量就等于

Cn=1n+1(2nn).

这就证明了 Catalan 数的表达式 (2)

表达式 (3) 的证明

考虑 路径计数问题。这是典型的格路计数问题,可以通过反射原理求解。具体到本问题,考虑用总路径数目减去不合法的路径数目。总路径数一共要走 2n 步,其中 n 步向右,所以方案数为 (2nn)。一条路径不合法,当且仅当它碰到了直线 y=x+1。对于任意一条非法路径,可以找到第一次碰到直线 y=x+1 的位置,并将该位置之后的路径关于直线 y=x+1 做对称。此时,可以发现,一条从 (0,0)(n,n) 的非法路径,变成了一条从 (0,0)(n1,n+1) 的路径。

catalan1

由于从 (0,0)(n1,n+1) 的路径必定要穿过直线 y=x+1,所以每条这样的路径都对应一条从 (0,0)(n,n) 的非法路径。类似总路径数的计算,非法路径数目的总数就是 (2nn+1)。因此,合法路径的总数为

Cn=(2nn)(2nn+1).

这就是 Catalan 数的表达式 (3)

表达式 (4) 的证明

考虑 三角剖分计数问题。设 P 是凸 (n+2) 边形,固定它的一个边为基边。对于多边形 P 的每一个三角剖分,都可以选择它的一个非基边(包括三角剖分时新加的边)标记,并定向。这共有 (4n+2)Cn 种剖分加标记的方案。又设 Q 是凸 (n+3) 边形,仍固定它的一个边为基边。对于多边形 Q,可以选择它的一条非基边标记,然后再做三角剖分。这共有 (n+2)Cn+1 种标记加剖分的方案。

如图所示,这两组操作得到的结果之间存在明显的双射。对于 P 剖分并标记的一个结果,可以将它的标记边扩展为三角形,定向所指向的终点扩展为一条新边,并将这条新边打上标记,这就得到对 Q 标记并剖分的一个结果;对于 Q 标记并剖分的一个结果,可以将它的标记边压缩为一个点,并将压缩得到的对角线打上标记,且指向压缩得到的顶点,这就得到对 P 剖分并标记的一个结果。因此,

(4n+2)Cn=(n+2)Cn+1.

稍作整理,并结合 C0=1,就得到 Catalan 数的表达式 (4)

例题

洛谷 P1044 栈

入栈顺序为 1,2,,n,求所有可能的出栈顺序的总数。

参考代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
using namespace std;

int n;
long long f[25];

int main() {
  f[0] = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  // 这里用的是常见形式 4
  cout << f[n] << endl;
  return 0;
}
1
2
3
4
5
6
7
f = [0] * 25
f[0] = 1
n = int(input())
for i in range(1, n + 1):
    f[i] = f[i - 1] * (4 * i - 2) // (i + 1)
    # 这里用的是常见形式 4
print(f[n])

习题

参考资料与注释