Contents 6 sections
- 问题
- 第一步:找递推
- 第二步:变成一个方程
- 第三步:展开求系数
- 另一种证明:一面镜子
- 它长得有多快
问题
n 对括号,有多少种「合法」的排法?合法的意思是:从左往右读,任何时刻右括号都不比左括号多。
- n=1:
(),1 种;
- n=2:
(())、()(),2 种;
- n=3:
((()))、(()())、(())()、()(())、()()(),5 种。
记答案为 Cn,并约定 C0=1(空串)。把 ( 看成向右上走一步、) 看成向右下走一步,合法括号串就对应于从 (0,0) 走到 (2n,0)、始终不低于横轴的折线,叫作 Dyck 路径。
图 1n = 3 时的 5 条 Dyck 路径,下方是对应的括号串。
这串数 1,1,2,5,14,42,132,… 叫作 Catalan 数。Euler 在 1751 年研究凸多边形的三角剖分时就遇到了它,后来以 Eugène Catalan 的名字命名。它出现得极其频繁:二叉树的个数、凸 (n+2) 边形的三角剖分数、栈排序的排列数……Stanley 的专著里收集了两百多种解释。
第一步:找递推
看一个长度为 2n+2 的合法串。它的第一个字符一定是 (,设与它配对的 ) 在某个位置,于是整个串唯一地写成
(合法,k 对A)合法,n−k 对B
其中 k 可以是 0,1,…,n。反过来,任取这样的 A 和 B 都能拼出一个合法串。所以
Cn+1=k=0∑nCkCn−k,C0=1.
验证一下:C3=C0C2+C1C1+C2C0=2+1+2=5。
递推能算出任意一项,但看不出通项。这正是生成函数擅长的事。
第二步:变成一个方程
定义 1(生成函数)数列 a0,a1,a2,… 的(普通)生成函数是形式幂级数 A(x)=∑n≥0anxn。
生成函数的威力在于:数列的卷积 ∑kakbn−k,恰好是两个生成函数乘积的第 n 项系数。我们的递推右边正是一个卷积。
设 C(x)=∑n≥0Cnxn。那么 C(x)2 的 xn 系数是 ∑kCkCn−k=Cn+1,于是
C(x)=C0+n≥0∑Cn+1xn+1=1+xC(x)2.
一个无穷递推,变成了关于 C(x) 的二次方程 xC2−C+1=0。解得
C(x)=2x1±1−4x.
取哪个符号?当 x→0 时,取正号分子趋于 2,C(x) 会趋于无穷;但 C(0)=C0=1 是有限的。所以只能取负号:
C(x)=2x1−1−4x.
第三步:展开求系数
用广义二项式定理展开 1−4x=∑k≥0(k1/2)(−4x)k。对 k≥1,直接计算可得
(k1/2)(−4)k=−k2(k−12k−2).
以 k=2 为例:(21/2)=2(1/2)(−1/2)=−81,乘以 16 得 −2;右边 −22(12)=−2。一般情形把 (k1/2) 的分子 21⋅(−21)⋯(23−k) 中的奇数连乘配成阶乘即可。所以
1−1−4x=k≥1∑k2(k−12k−2)xk.
两边除以 2x,取 xn 的系数(对应 k=n+1):
定理 1(Catalan 数的通项)Cn=n+11(n2n).
例如 C4=51(48)=570=14。
另一种证明:一面镜子
上面的推导很有力,却不太「看得见」。下面这个证明不用任何代数,只用一次反射,通常归于 Désiré André。
从 (0,0) 到 (2n,0)、每步上或下的折线一共 (n2n) 条(在 2n 步里选 n 步向上)。其中不合法的,就是某时刻碰到了直线 y=−1 的那些。
引理 2不合法路径与「从 (0,0) 到 (2n,−2) 的全部路径」一一对应,后者共有 (n+12n) 条。
证明.对一条不合法路径,找到它第一次碰到 y=−1 的位置,把此后的部分关于直线 y=−1 翻转。原来终点在 y=0,翻转后终点在 y=−2。反过来,任何走到 (2n,−2) 的路径一定会碰到 y=−1,把第一次碰到之后的部分翻回去,就得到一条不合法路径。两种操作互逆。终点为 (2n,−2) 的路径有 n−1 步向上、n+1 步向下,共 (n+12n) 条。
∎
于是
Cn=(n2n)−(n+12n)=(n2n)(1−n+1n)=n+11(n2n),
和生成函数的结果完全一致。
它长得有多快
由 Stirling 公式 (n2n)∼πn4n,得到
Cn∼n3/2π4n.
底数 4 恰好是生成函数 1−4x 的奇点 x=1/4 的倒数。这不是巧合:生成函数离原点最近的奇点决定了系数的指数增长率,这是解析组合学的出发点。