Contents 6 sections
  1. 问题
  2. 第一步:找递推
  3. 第二步:变成一个方程
  4. 第三步:展开求系数
  5. 另一种证明:一面镜子
  6. 它长得有多快

问题

nn 对括号,有多少种「合法」的排法?合法的意思是:从左往右读,任何时刻右括号都不比左括号多。

  • n=1n = 1:(),1 种;
  • n=2n = 2:(())、()(),2 种;
  • n=3n = 3:((()))、(()())、(())()、()(())、()()(),5 种。

记答案为 CnC_n,并约定 C0=1C_0 = 1(空串)。把 ( 看成向右上走一步、) 看成向右下走一步,合法括号串就对应于从 (0,0)(0,0) 走到 (2n,0)(2n,0)、始终不低于横轴的折线,叫作 Dyck 路径。

((()))(()())(())()()(())()()()
图 1n = 3 时的 5 条 Dyck 路径,下方是对应的括号串。

这串数 1,1,2,5,14,42,132,…1, 1, 2, 5, 14, 42, 132, \dots 叫作 Catalan 数。Euler 在 1751 年研究凸多边形的三角剖分时就遇到了它,后来以 Eugène Catalan 的名字命名。它出现得极其频繁:二叉树的个数、凸 (n+2)(n+2) 边形的三角剖分数、栈排序的排列数……Stanley 的专著里收集了两百多种解释。

第一步:找递推

看一个长度为 2n+22n+2 的合法串。它的第一个字符一定是 (,设与它配对的 ) 在某个位置,于是整个串唯一地写成

(  A⏟合法,k 对  )  B⏟合法,n−k 对\texttt{(}\;\underbrace{A}_{\text{合法,}k\text{ 对}}\;\texttt{)}\;\underbrace{B}_{\text{合法,}n-k\text{ 对}}

其中 kk 可以是 0,1,…,n0, 1, \dots, n。反过来,任取这样的 AA 和 BB 都能拼出一个合法串。所以

Cn+1=∑k=0nCk Cn−k,C0=1.C_{n+1} = \sum_{k=0}^{n} C_k\, C_{n-k}, \qquad C_0 = 1.

验证一下:C3=C0C2+C1C1+C2C0=2+1+2=5C_3 = C_0C_2 + C_1C_1 + C_2C_0 = 2 + 1 + 2 = 5。

递推能算出任意一项,但看不出通项。这正是生成函数擅长的事。

第二步:变成一个方程

定义 1(生成函数)

数列 a0,a1,a2,…a_0, a_1, a_2, \dots 的(普通)生成函数是形式幂级数 A(x)=∑n≥0anxnA(x) = \sum_{n \ge 0} a_n x^n。

生成函数的威力在于:数列的卷积 ∑kakbn−k\sum_k a_k b_{n-k},恰好是两个生成函数乘积的第 nn 项系数。我们的递推右边正是一个卷积。

设 C(x)=∑n≥0CnxnC(x) = \sum_{n\ge0} C_n x^n。那么 C(x)2C(x)^2 的 xnx^n 系数是 ∑kCkCn−k=Cn+1\sum_k C_kC_{n-k} = C_{n+1},于是

C(x)=C0+∑n≥0Cn+1xn+1=1+x C(x)2.C(x) = C_0 + \sum_{n \ge 0} C_{n+1} x^{n+1} = 1 + x\,C(x)^2.

一个无穷递推,变成了关于 C(x)C(x) 的二次方程 xC2−C+1=0x C^2 - C + 1 = 0。解得

C(x)=1±1−4x2x.C(x) = \frac{1 \pm \sqrt{1-4x}}{2x}.

取哪个符号?当 x→0x \to 0 时,取正号分子趋于 22,C(x)C(x) 会趋于无穷;但 C(0)=C0=1C(0) = C_0 = 1 是有限的。所以只能取负号:

C(x)=1−1−4x2x.C(x) = \frac{1 - \sqrt{1-4x}}{2x}.

第三步:展开求系数

用广义二项式定理展开 1−4x=∑k≥0(1/2k)(−4x)k\sqrt{1-4x} = \sum_{k\ge0} \binom{1/2}{k}(-4x)^k。对 k≥1k \ge 1,直接计算可得

(1/2k)(−4)k=−2k(2k−2k−1).\binom{1/2}{k}(-4)^k = -\frac{2}{k}\binom{2k-2}{k-1}.

以 k=2k=2 为例:(1/22)=(1/2)(−1/2)2=−18\binom{1/2}{2} = \frac{(1/2)(-1/2)}{2} = -\frac18,乘以 1616 得 −2-2;右边 −22(21)=−2-\frac22\binom{2}{1} = -2。一般情形把 (1/2k)\binom{1/2}{k} 的分子 12⋅(−12)⋯(32−k)\frac12\cdot(-\frac12)\cdots(\frac32-k) 中的奇数连乘配成阶乘即可。所以

1−1−4x=∑k≥12k(2k−2k−1)xk.1 - \sqrt{1-4x} = \sum_{k\ge1} \frac{2}{k}\binom{2k-2}{k-1} x^k.

两边除以 2x2x,取 xnx^n 的系数(对应 k=n+1k = n+1):

定理 1(Catalan 数的通项)
Cn=1n+1(2nn).C_n = \frac{1}{n+1}\binom{2n}{n}.

例如 C4=15(84)=705=14C_4 = \frac15\binom84 = \frac{70}{5} = 14。

另一种证明:一面镜子

上面的推导很有力,却不太「看得见」。下面这个证明不用任何代数,只用一次反射,通常归于 Désiré André。

从 (0,0)(0,0) 到 (2n,0)(2n,0)、每步上或下的折线一共 (2nn)\binom{2n}{n} 条(在 2n2n 步里选 nn 步向上)。其中不合法的,就是某时刻碰到了直线 y=−1y = -1 的那些。

引理 2

不合法路径与「从 (0,0)(0,0) 到 (2n,−2)(2n,-2) 的全部路径」一一对应,后者共有 (2nn+1)\binom{2n}{n+1} 条。

证明.

对一条不合法路径,找到它第一次碰到 y=−1y=-1 的位置,把此后的部分关于直线 y=−1y=-1 翻转。原来终点在 y=0y=0,翻转后终点在 y=−2y=-2。反过来,任何走到 (2n,−2)(2n,-2) 的路径一定会碰到 y=−1y=-1,把第一次碰到之后的部分翻回去,就得到一条不合法路径。两种操作互逆。终点为 (2n,−2)(2n,-2) 的路径有 n−1n-1 步向上、n+1n+1 步向下,共 (2nn+1)\binom{2n}{n+1} 条。

∎

于是

Cn=(2nn)−(2nn+1)=(2nn)(1−nn+1)=1n+1(2nn),C_n = \binom{2n}{n} - \binom{2n}{n+1} = \binom{2n}{n}\left(1 - \frac{n}{n+1}\right) = \frac{1}{n+1}\binom{2n}{n},

和生成函数的结果完全一致。

它长得有多快

由 Stirling 公式 (2nn)∼4nπn\binom{2n}{n} \sim \dfrac{4^n}{\sqrt{\pi n}},得到

Cn∼4nn3/2π.C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}.

底数 44 恰好是生成函数 1−4x\sqrt{1-4x} 的奇点 x=1/4x = 1/4 的倒数。这不是巧合:生成函数离原点最近的奇点决定了系数的指数增长率,这是解析组合学的出发点。