Chap21 递推方程与生成函数

返回：0100 离散数学课程总目录 · 上一章：0120 计数原则、排列组合与组合恒等式 · 下一章：0122 包含排斥、Burnside 引理与 Polya 定理

1、学习目标

本章继续组合计数。上一章偏“直接数”，这一章偏“把数量关系变成工具”：递推方程描述规模变化，生成函数把序列打包成幂级数，Catalan 数、Stirling 数、Bell 数则是常见组合结构的标准模型。

主线：

递推方程：从 a_n 与前面若干项的关系求通项。
生成函数：把序列 {a_n} 变成 A(x)=sum a_n x^n。
指数生成函数：处理有标号对象与排列型计数。
Catalan 数：处理不越界路径、括号、配对、树形等结构。
Stirling 数：处理排列循环、集合划分和放球模型。
Bell 数：处理集合的所有划分。

本站页面编号是 0121，但课件与习题内部称为“第二十二章/习题二十二”。下面答案按教材题号写成 22.1-22.36。

2、递推方程

递推方程用较小规模的项表示较大规模的项：

1	a_n = F(n,a_0,a_1,...,a_(n-1))

解题第一步不是套公式，而是先写清楚：

1. a_n 表示什么。
2. 初值是什么。
3. 从 n-1 到 n 新增了什么。
4. 是否需要分类讨论最后一步。

常系数线性齐次递推

形如：

1	a_n = c1a_(n-1)+c2a_(n-2)+...+ck*a_(n-k)

对应特征方程：

1	x^k-c1x^(k-1)-c2x^(k-2)-...-ck=0

若特征根 q 的重数为 e，对应通解项为：

1	q^n, nq^n, n^2q^n, ..., n^(e-1)*q^n

常系数线性非齐次递推

非齐次递推的通解为：

1	原方程通解 = 齐次方程通解 + 一个非齐次特解

常见右端项与特解猜法：

右端项	若不撞特征根，可设特解
常数	`P`
多项式 `p(n)`	同次数多项式
指数 `beta^n`	`P*beta^n`
多项式乘指数 `p(n)beta^n`	同次数多项式乘 `beta^n`

如果猜出的特解形式撞上特征根，要乘上足够次的 n。例如右端是常数，而 1 是特征根，就不能设 P，通常要从 P*n 开始试。

3、递推方程的其他解法

方法	适用场景	记忆点
公式法	常系数线性递推	列特征方程
换元法	变量系数可被吸收	先令 `b_n` 简化递推
迭代法	一阶递推或可连续展开	展开到初值
归纳法	已经猜到闭式	验证初值与递推步
差消法	相邻项相减后消掉复杂项	先求差，再累加
递归树	算法复杂度	看每层代价与层数
生成函数法	卷积、分拆、组合计数	转成 `A(x)` 的代数式

建模习惯：能从“最后一个元素/最后一步/是否包含某元素”分类的题，常常能直接写出递推。

4、生成函数

普通生成函数：

1 2	A(x)=a_0+a_1x+a_2x^2+... =sum_{n>=0} a_n*x^n

指数生成函数：

1	E(x)=sum_{n>=0} a_n*x^n/n!

普通生成函数适合处理无标号组合、整数解、无序分拆；指数生成函数适合处理有标号对象、排列、把不同类对象交错放置的计数。

常用基本式

1/(1-x) = sum_{n>=0} x^n
1/(1-x)^2 = sum_{n>=0} (n+1)x^n
x/(1-x)^2 = sum_{n>=0} n*x^n
x(1+x)/(1-x)^3 = sum_{n>=0} n^2*x^n
x^k/(1-x)^(k+1) = sum_{n>=0} C(n,k)x^n
e^x = sum_{n>=0} x^n/n!

生成函数操作

数列操作	生成函数操作
`c_n=a_n+b_n`	`C(x)=A(x)+B(x)`
`c_n=alpha*a_n`	`C(x)=alpha*A(x)`
`b_n=a_(n+l)`	`B(x)=(A(x)-a_0-a_1*x-...-a_(l-1)x^(l-1))/x^l`
`b_n=alpha^n*a_n`	`B(x)=A(alpha*x)`
`c_n=sum_{k=0}^n a_k*b_(n-k)`	`C(x)=A(x)B(x)`

生成函数解递推的套路：

1. 设 A(x)=sum a_n x^n。
2. 将递推式两边乘 x^n。
3. 对 n 的有效范围求和。
4. 用初值补齐缺项，整理出 A(x)。
5. 展开 A(x)，读出 x^n 的系数。

5、整数剖分与生成函数

整数 N 的剖分常转成生成函数中 x^N 的系数。

例如每个正整数部件可重复使用：

1	1/[(1-x)(1-x^2)(1-x^3)...]

若每个部件最多出现 3 次：

1	prod_{i>=1} (1+x^i+x^(2i)+x^(3i))

若只允许小于等于 m 的正整数作部件：

1	1/[(1-x)(1-x^2)...(1-x^m)]

若把 N 有序剖分成 n 个正整数，且每个不超过 m，方案数是：

1	(x+x^2+...+x^m)^n 中 x^N 的系数

6、Catalan 数

记 Catalan 数为：

1	C_n = 1/(n+1) * C(2n,n)

递推：

1 2	C_0=1 C_n=sum_{k=0}^{n-1} C_k*C_(n-1-k)

生成函数：

1
2
3

C(x)=sum_{n>=0} C_n*x^n
C(x)=1+x*C(x)^2
C(x)=(1-sqrt(1-4x))/(2x)

典型模型：

1. 长度 2n 的合法括号序列。
2. 从 (0,0) 到 (n,n) 且不越过对角线的路径。
3. n+2 边形的三角剖分。
4. n 个节点二叉树形态。
5. 2n 个圆周点用 n 条不相交弦配对。

7、Stirling 数与 Bell 数

第一类 Stirling 数，记作：

[n r]

含义：n 元排列分解成 r 个循环的排列数，也等于下降阶乘展开中系数的绝对值。

递推：

1
2
3

[n r]=[n-1 r-1]+(n-1)[n-1 r]
[n 1]=(n-1)!
[n n]=1

第二类 Stirling 数，记作：

{n r}

含义：把 n 元集合划分成 r 个非空无标号块的方法数。

递推：

1
2
3

{n r}={n-1 r-1}+r*{n-1 r}
{n 1}=1
{n n}=1

若把 n 元集划分成 r 个非空有序块，则方案数为：

r!*{n r}

Bell 数：

1	B_n=sum_{r=1}^n {n r}

表示 n 元集合的所有划分数。

8、习题二十二答案速查

22.1、Fibonacci 交错和

答案：

1 2	f(0)-f(1)+f(2)-...+(-1)^n f(n) = 1+(-1)^n f(n-1)

证明方法：对 n 归纳，利用 f(n)-f(n-2)=f(n-1)。

22.2、Fibonacci 恒等式

先证通用式：

1	f(n+m)=f(m-1)f(n+1)+f(m-2)f(n)

再取合适的 m，得到：

1
2
3

(1) f(n-1)^2+f(n)^2=f(2n)
(2) f(n)f(n+1)-f(n-1)f(n-2)=f(2n)
(3) f(n)^3+f(n+1)^3-f(n-1)^3=f(3n+2)

22.3、Cassini 型恒等式

结论：

1	f(n)f(n+2)-f(n+1)^2 = (-1)^n

所以：

1 2	n 为偶数时，右边为 1。 n 为奇数时，右边为 -1。

22.4、类 Fibonacci 数列

已知：

1	H_1=a, H_2=b, H_(n+2)=H_(n+1)+H_n

若用标准 Fibonacci 数 F_0=0,F_1=1，则：

1	H_n=F_(n-2)a+F_(n-1)b, n>=2

并且 H_1=a。

22.5、求 c1 和 c2

已知：

1 2	a_0=0, a_1=1, a_2=4, a_3=12 a_n+c1a_(n-1)+c2a_(n-2)=0

代入 n=2,3：

1 2	4+c1=0 12+4c1+c2=0

答案：

1	c1=-4, c2=4

22.6、求解递推方程

答案：

(1) a_n-7a_(n-1)+12a_(n-2)=0, a_0=4, a_1=6
    a_n=10*3^n-6*4^n

(2) a_n+a_(n-2)=0, a_0=0, a_1=2
    a_(2k)=0
    a_(2k+1)=2*(-1)^k

(3) a_n+6a_(n-1)+9a_(n-2)=3, a_0=0, a_1=1
    a_n=[9-(4n+9)(-3)^n]/48

(4) a_n-3a_(n-1)+2a_(n-2)=1, a_0=4, a_1=6
    a_n=3*2^n-n+1

(5) a_n-7a_(n-1)+10a_(n-2)=3^n, a_0=0, a_1=1
    a_n=(8/3)*2^n+(11/6)*5^n-(9/2)*3^n

22.7、由解反推递推方程系数

已知递推方程：

1	c0a_n+c1a_(n-1)+c2*a_(n-2)=f(n)

其解为：

1	a_n=3^n+4^n+2

且 f(n)=6。答案：

1
2
3

c0=1/2
c1=-7/2
c2=6

22.8、换元与迭代

答案：

(1) n*a_n+(n-1)*a_(n-1)=2^n, n>=1, a_0=273
    令 b_n=n*a_n，则 b_n+b_(n-1)=2^n。
    b_n=[2^(n+1)+2*(-1)^(n+1)]/3
    a_n=[2^(n+1)+2*(-1)^(n+1)]/(3n), n>=1
    a_0=273

(2) a_n-n*a_(n-1)=n!, n>=1, a_0=2
    a_n=n!*(n+2)

22.9、集合划分数递推

设 a_n 是 n 元集合的划分数，即 Bell 数。结论：

1 2	a_(n+1)=sum_{i=0}^n C(n,i)*a_i a_0=1

证明思路：固定元素 x_1 所在划分块。若它还带着其余 n-i 个元素，则剩余 i 个元素可任意划分。

22.10、凸 n 边形对角线分割区域

递推：

1 2	a_n-a_(n-1)=C(n-1,3)+n-2 a_0=a_1=a_2=0

答案：

1	a_n=C(n,4)+C(n,2)-n+1

等价写法：

1	a_n=(n-1)(n-2)(n^2-3n+12)/24

22.11、n 阶行列式

该三对角行列式满足：

1 2	d_n=2d_(n-1)-d_(n-2) d_1=2, d_2=3

答案：

d_n=n+1

22.12、直线分割平面

若平面上 n 条直线两两相交且无三线共点，区域数满足：

1 2	a_n=a_(n-1)+n a_0=1

答案：

1	a_n=n(n+1)/2+1

22.13、红蓝涂色且红格不相邻

设 a_n 为方案数。按最后一个格子分类：

1 2	最后一格蓝色：a_(n-1) 最后一格红色：前一格必须蓝色，对应 a_(n-2)

递推：

1 2	a_n=a_(n-1)+a_(n-2) a_1=2, a_2=3

答案：

1	a_n=F_(n+2)

其中 F_0=0,F_1=1。

22.14、不含连续整数的 k 子集

设 f(n,k) 为从 {1,2,...,n} 中选出不含连续整数的 k 子集数。

递推：

1	f(n,k)=f(n-1,k)+f(n-2,k-1)

闭式：

1	f(n,k)=C(n-k+1,k)

所有不含连续整数的子集数：

1	sum_k f(n,k)=F_(n+2)

若课程使用 f(0)=f(1)=1 的 Fibonacci 记号，则它写作 f(n+1)。

22.15、黄金矩形相似

设每一步长边为 a_n，短边为 b_n，则：

1 2	a_(n+1)=b_n b_(n+1)=a_n-b_n

初始长短边比：

1	a_1/b_1=(1+sqrt(5))/2

由递推可知每一步仍保持：

1	a_n/b_n=(1+sqrt(5))/2

所以每一步得到的矩形都与原矩形相似。

22.16、证明生成函数性质

按定义逐项展开即可：

(1) c_n=a_n+b_n
    C(x)=A(x)+B(x)

(2) b_n=a_(n+l)
    B(x)=[A(x)-a_0-a_1*x-...-a_(l-1)x^(l-1)]/x^l

(3) b_n=alpha^n*a_n
    B(x)=A(alpha*x)

(4) b_n=a_n/(n+1)
    B(x)=1/x * integral_0^x A(t) dt

22.17、确定生成函数

答案：

(1) a_n=(-1)^n(n+1)
    A(x)=1/(1+x)^2

(2) a_n=(-1)^n 2^n
    A(x)=1/(1+2x)

(3) a_n=n+5
    A(x)=(5-4x)/(1-x)^2

(4) a_n=C(n,3)
    A(x)=x^3/(1-x)^4

22.18、由生成函数确定 a_n

答案：

(1) A(x)=x(1+x)/(1-x)^3
    a_n=n^2

(2) A(x)=1/[(1-x)(1-x^2)]
    a_n=floor(n/2)+1

第二问解释：x^n 的系数等于方程 i+2j=n 的非负整数解个数。

22.19、多重集 n 组合生成函数

设：

1	S={inftya1, inftya2, inftya3, inftya4}

答案：

(1) 每个 ai 出现奇数次：
    C(x)=x^4/(1-x^2)^4

(2) 每个 ai 出现 3 的倍数次：
    C(x)=1/(1-x^3)^4

(3) a1 不出现，a2 至多出现 1 次：
    C(x)=(1+x)/(1-x)^2

(4) a1 出现 1、3 或 11 次；a2 出现 2、4 或 5 次：
    C(x)=(x+x^3+x^11)(x^2+x^4+x^5)/(1-x)^2

(5) 每个 ai 至少出现 10 次：
    C(x)=x^40/(1-x)^4

22.20、四色涂色且红绿均为偶数

1 x n 方格用红、蓝、绿、橙四种颜色涂色，红色格数为偶数，绿色格数为偶数。

答案：

1 2	n=0 时：1 n>=1 时：4^(n-1)+2^(n-1)

等价写法：

1	(4^n+2*2^n)/4, n>=1

22.21、整数剖分与多重集划分

正整数 N 被无序剖分成允许重复的正整数，等价于非负整数解：

1	1x1+2x2+...+N*xN=N

多重集 {N*a} 划分成子多重集时，x_k 表示含 k 个 a 的子多重集个数，也满足同一个方程。因此两种方法数相等。

22.22、两个非负整数解个数相同

答案：

x1+x2+...+x7=13 的非负整数解数：
C(13+7-1,13)=C(19,6)

x1+x2+...+x14=6 的非负整数解数：
C(6+14-1,6)=C(19,6)

所以二者相同。

22.23、整数剖分递推

设 P(N,m) 为把 N 剖分成不超过 m 的正整数之和的方法数。

按是否含有一个 m 分类：

1 2	不含 m：P(N,m-1) 至少含一个 m：P(N-m,m)

结论：

1	P(N,m)=P(N,m-1)+P(N-m,m)

22.24、有序剖分与系数

设 (N,n,m) 表示把 N 有序剖分成 n 个正整数，且每个正整数不超过 m 的方案数。

每一部分贡献：

1	x+x^2+...+x^m

因此：

1	(N,n,m) = (x+x^2+...+x^m)^n 中 x^N 的系数

22.25、两类剖分等数

第一类：只有奇数项可以重复，即奇数项不限次数，偶数项至多出现一次。

生成函数：

1	prod_{j>=1} 1/(1-x^(2j-1)) * prod_{j>=1} (1+x^(2j))

第二类：没有一个项出现次数大于 3。

生成函数：

1	prod_{j>=1} (1+x^j+x^(2j)+x^(3j))

利用：

1	1+x^j+x^(2j)+x^(3j) = (1-x^(4j))/(1-x^j)

可化成与第一类相同的生成函数，所以两类剖分数相等。

22.26、指数生成函数

答案：

(1) a_n=n!
    E(x)=1/(1-x)

(2) a_n=2^n*n!
    E(x)=1/(1-2x)

(3) a_n=(-1)^n
    E(x)=e^(-x)

22.27、组合恒等式

要证：

1 2	sum_{k=0}^n C(n,k) * C(m+k,k)^(-1) * (-1)^k/(m+k+1) = 1/(n+m+1)

证明思路：令：

1 2	a_k = C(m+k,k)^(-1)/(m+k+1) b_n = sum_{k=0}^n (-1)^k C(n,k)a_k

结合上一章的带分母交错和，再用组合互逆变换即可得到结论。

22.28、由三个 1、两个 2、五个 3 组成四位数

答案：

1 2	不同四位数总数：71 其中偶数个数：20

偶数时末位只能是 2，再对剩余三位用指数生成函数或分类计数。

22.29、n 位奇数字且 1、3 均出现正偶数次

可选数字为：

1,3,5,7,9

其中 1 和 3 都要出现正偶数次。

指数生成函数：

1	(cosh x - 1)^2 * e^(3x)

答案：

1	a_n = [5^n - 44^n + 63^n - 4*2^n + 1]/4

22.30、圆周上 2n 点的不相交弦配对

设配对数为 h_n。固定一个点，与它配对的点会把其余点分成左右两部分，因此：

1 2	h_0=1 h_n=sum_{k=0}^{n-1} h_k*h_(n-1-k)

所以：

1	h_n=C_n=1/(n+1)*C(2n,n)

这也就是课件中按 C_0 为第一个时所说的“第 n+1 个 Catalan 数”。

22.31、计算第一类 Stirling 数 [6 n]

答案：

[6 1]=120
[6 2]=274
[6 3]=225
[6 4]=85
[6 5]=15
[6 6]=1

22.32、计算第一类 Stirling 数 [7 n]

答案：

[7 1]=720
[7 2]=1764
[7 3]=1624
[7 4]=735
[7 5]=175
[7 6]=21
[7 7]=1

22.33、第一类 Stirling 数恒等式

由下降阶乘展开：

1 2	x(x-1)...(x-n+1) = [n n]x^n - [n n-1]x^(n-1) + [n n-2]x^(n-2) - ...

令 x=n，左边为 n!，得到：

1	n! = [n n]n^n - [n n-1]n^(n-1) + [n n-2]n^(n-2) - ...

22.34、恰好 k 种颜色做旗子

题意：每面旗子由 n 条彩带构成，恰好用 k 种颜色，相邻彩带颜色不同。

答案：

1	k! * {n-1 k-1}

其中 {n-1 k-1} 是第二类 Stirling 数。

22.35、n 元集划分成 t 个非空有序子集

先把 n 元集划分成 t 个非空无序块，有：

{n t}

再给这 t 个块排序，有 t! 种。

答案：

1	T(n,t)=t!*{n t}

22.36、Bell 数

设 b_n 是 n 元集合划分成非空子集的方法数。

固定元素 a_1 所在划分块大小，得：

b_n = C(n-1,0)b_(n-1)
    + C(n-1,1)b_(n-2)
    + ...
    + C(n-1,n-1)b_0

按非空子集块数分类，得：

1	b_n = {n 1}+{n 2}+...+{n n}

9、复盘清单

1. 递推题先写清 a_n 的含义和初值。
2. 常系数线性递推先列特征方程，重根要补 n 的幂。
3. 非齐次递推要先解齐次，再猜特解；撞根时特解乘 n。
4. 生成函数题先判断普通生成函数还是指数生成函数。
5. 多重集组合题把每类元素的允许次数写成一个因子。
6. 剖分题看清“有序/无序”“部件是否可重复”“每部分是否有上界”。
7. Catalan 题优先找“不交叉、不越界、配对、括号”。
8. Stirling 题先分第一类循环、第二类划分。