母函数与递推关系

本节导读

母函数与递推关系单元大纲列了十条：母函数、递推关系、Fibonacci 数列、线性常系数递推关系、整数拆分与 Ferrers 图像、指数型母函数、应用举例、错排问题、Stirling 数、Catalan 数。大纲在组合数学部分特别点名要求掌握「线性常系数递推关系的解法」。

常见的考法：写出某个计数问题的母函数并求某一项的系数；解一个二阶递推关系；求错排数、Stirling 数、Catalan 数的具体值，或者判断一个问题对应哪一种数。学完你应该能熟练用特征根法解递推，并能分清普通母函数（组合，不计顺序）与指数型母函数（排列，计顺序）的用法。

普通母函数

数列 $a_0, a_1, a_2, \ldots$a0​,a1​,a2​,… 的普通母函数是 $G(x) = a_0 + a_1 x + a_2 x^2 + \cdots$G(x)=a0​+a1​x+a2​x2+⋯，x 只是一个记号，$x^n$xn 的系数就是要数的 $a_n$an​。常用展开式：

母函数	对应的 $a_n$an​
$\frac{1}{1-x}$1−x1​	1
$\frac{1}{1-ax}$1−ax1​	$a^n$an
$(1+x)^m$(1+x)m	$C(m, n)$C(m,n)
$\frac{1}{(1-x)^m}$(1−x)m1​	$C(m + n - 1, n)$C(m+n−1,n)

有限制的组合计数，每一类元素写一个因子：这一类可以取 0 个、1 个、2 个……就写 $1 + x + x^2 + \cdots$1+x+x2+⋯，取的个数受限制就只写允许的那些项，最后乘起来取 $x^r$xr 的系数。例如从 2 个相同的苹果、3 个相同的香蕉里取 3 个：$(1 + x + x^2)(1 + x + x^2 + x^3)$(1+x+x2)(1+x+x2+x3) 展开后 $x^3$x3 的系数是 3，即苹果取 0、1、2 个三种。

整数的拆分与 Ferrers 图像

把正整数 n 写成若干正整数之和、不计顺序，叫 n 的拆分，拆分数记作 $p(n)$p(n)：$p(1)$p(1) 到 $p(6)$p(6) 依次是 1、2、3、5、7、11。母函数是 $\prod_{k \ge 1} \frac{1}{1 - x^k}$∏k≥1​1−xk1​；分成互不相同的部分，母函数是 $\prod_{k \ge 1} (1 + x^k)$∏k≥1​(1+xk)；分成奇数部分，母函数是 $\prod_{k \ge 1} \frac{1}{1 - x^{2k-1}}$∏k≥1​1−x2k−11​。后两者相等，所以「分成互不相同的部分」与「分成奇数部分」的方法数总相同。例如 5：互不相同的是 5、4＋1、3＋2，奇数部分的是 5、3＋1＋1、1＋1＋1＋1＋1，都是 3 种。

把拆分的每一部分画成一行点、从大到小排列，就是 Ferrers 图像。把图像沿对角线翻转（行变列），得到共轭拆分，由此可以证明：n 拆成至多 k 部分的方法数，等于拆成每部分都不超过 k 的方法数。

指数型母函数

数列的指数型母函数是 $G_e(x) = \sum a_n \frac{x^n}{n!}$Ge​(x)=∑an​n!xn​，用来数「计顺序」的排列问题。每一类元素写一个因子 $\sum \frac{x^k}{k!}$∑k!xk​（只写允许的 k），乘起来后 $\frac{x^n}{n!}$n!xn​ 的系数就是答案。常用 $e^x = \sum \frac{x^n}{n!}$ex=∑n!xn​，$\frac{e^x + e^{-x}}{2} = \sum_{k} \frac{x^{2k}}{(2k)!}$2ex+e−x​=∑k​(2k)!x2k​。

例如用 a、b、c 组成长度为 n 的字符串，要求 a 出现偶数次：$G_e(x) = \frac{e^x + e^{-x}}{2} \cdot e^{2x} = \frac{e^{3x} + e^x}{2}$Ge​(x)=2ex+e−x​⋅e2x=2e3x+ex​，所以 $a_n = \frac{3^n + 1}{2}$an​=23n+1​。

线性常系数递推关系

Fibonacci 数列 $F_1 = F_2 = 1$F1​=F2​=1，$F_n = F_{n-1} + F_{n-2}$Fn​=Fn−1​+Fn−2​，是最有名的递推关系；汉诺塔的移动次数 $h_n = 2h_{n-1} + 1$hn​=2hn−1​+1，$h_1 = 1$h1​=1，解得 $h_n = 2^n - 1$hn​=2n−1。

齐次的 $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$an​=c1​an−1​+c2​an−2​+⋯+ck​an−k​ 用特征根法：写出特征方程 $x^k - c_1 x^{k-1} - \cdots - c_k = 0$xk−c1​xk−1−⋯−ck​=0，求出特征根。

特征根的情况	通解的形式
k 个互不相同的根 $q_1, \ldots, q_k$q1​,…,qk​	$a_n = A_1 q_1^n + \cdots + A_k q_k^n$an​=A1​q1n​+⋯+Ak​qkn​
q 是 m 重根	这一部分写成 $(A_1 + A_2 n + \cdots + A_m n^{m-1}) q^n$(A1​+A2​n+⋯+Am​nm−1)qn

最后用初值列方程组，解出常数。非齐次的 $a_n = c_1 a_{n-1} + \cdots + f(n)$an​=c1​an−1​+⋯+f(n)：通解等于齐次通解加一个特解。$f(n)$f(n) 是 k 次多项式时，1 不是特征根就设 k 次多项式，1 是 m 重特征根就再乘上 $n^m$nm；$f(n) = b^n$f(n)=bn 而 b 不是特征根就设 $A b^n$Abn，b 是 m 重特征根就设 $A n^m b^n$Anmbn。也可以用母函数解：两边乘 $x^n$xn 求和，解出 $G(x)$G(x)，再部分分式展开。