组合数学2-母函数,递推关系

摘要: 组合数学：母函数与递推关系

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式，本文我们看一下组合数学的第二部分，母函数和递推关系，主要内容如下：

• 母函数
  • 定义，多项式乘法
  • 整数分拆：有序分拆，无序分拆，无序分拆数
  • FERRERS 图像
  • 常用函数的 Taylor 展开
• 递推关系的例子
  • 差分方程, Hanoi 问题
  • 应用：n 位 10 进制数中出现偶数个 5 的数的个数
  • 斐波那契数
  • 斐波那契恒等式
• k阶线性常系数齐次递推关系
  • 线性常系数齐次递推关系的母函数
  • 母函数与特征多项式
    • 1.特征多项式无重根
    • 2.特征多项式有重根
    • 3.特征多项式有共轭复根
  • 应用：k 种颜色对 n 个区域着色

---

母函数

母函数定义

序列 $c_{0}, c_{1}, c_{2}, …$ 的母函数：

$$G(x) = c_{0} + c_{1}x_{1} + c_{2}x_{2} + ...$$

伯努利(1654~1705)：投 m 粒骰子出 n 点有几种方法: 下式中 $x^{n}$ 的系数

$$(x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6})^{m}$$

1812 拉普拉斯：《概率的分析理论》系统研究母函数

多项式乘法

$$\sum^{\infty}_{k=0}a_{k}x^{k}\sum^{\infty}_{k=0}b_{k}x^{k}$$

蕴含了计数的乘法法则和加法法则。因此母函数具备计数的能力。

母函数例题

例1：1g, 2g, 3g, 4g 共 4 个砝码，对某个重量有多少种方案

$$G(x) = (1 + x)(1 + x^{2})(1 + x^{3})(1 + x^{4})$$

例2：1g, 2g, 4g, 8g, 16g, 32g 共 6 个砝码，对某个重量有多少种方案

$$\begin{align} G(x) &= (1 + x)(1 + x^{2})(1 + x^{4})(1 + x^{8})(1 + x^{26})(1 + x^{32}) \\ &= \frac{1 - x^{64}}{1 - x} = 1 + x + x^{2} + ... + x^{63} = \sum^{63}_{k=0}x^{k} \end{align}$$

整数分拆

• 有序分拆 Composition
• 无序分拆 Partition

无序分拆相当于把 n 个无标志的球放入 r 个无标志的盒子，盒子可以空着：

• n 拆成 1, 2, …, m 的和，可以重复：

$$\begin{align} G(x) &= (1 + x + x^{2} + ...)(1 + x^{2} + x^{4} + ...)...(1 + x^{m} + x^{2m} + ...) \\ &= (1 + x)^{-1}(1 + x^{2})^{-1}...(1 + x^{m})^{-1} \end{align}$$

• n 拆成 1, 2, …, m 的和，可以重复，且 m 至少出现一次：

$$\begin{align} G(x) &= (1 + x + x^{2} + ...)(1 + x^{2} + x^{4} + ...)...(x^{m} + x^{2m} + ...) \\ &= x^{m}(1 + x)^{-1}(1 + x^{2})^{-1}...(1 + x^{m})^{-1} \end{align}$$

• 无序分拆数：$P(n)$

Euler 1740：P(29) = 4565
拉马努金 1912：P(200) = 3982999029388
计算机出现 -> 大数相乘处理
系数卷积: $f * g[k] = \sum_{i}f[i]g[k - i]$

$$(1 + x + x^{2} + ...)(1 + x^{2} + x^{4} + ...) = (1 + x + 2x^{2} + 2x^{3} + 3x^{4} + 3x^{5} + ...)$$

FERRERS图像

n个数字 -> n个格子

格子不同摆放 -> n不同的分拆

无序分拆 -> 上层格子比下层格子多

共轭FERRERS角度解释下面两件事：

1. 最大数为 k 和有 k 个数的无序分拆数相等
2. 最大不超过 m 和最多不超过 m 个数的无序分拆数相等

常用函数的 Taylor 展开

母函数与数字序列一一对应：

$$(1 - x)^{-1} = 1 + x + x^{2} + ... \\ (1 - ax)^{-1} = 1 + ax + x^{2} + ...$$

例：部分分式展开 + 待定系数：

$$\begin{align} \frac{2 - 3x}{(1 - x)(1 - 2x)} &= \frac{1}{1 - x} + \frac{1}{1 - 2x} \\ &= \sum_{k=0}^{\infty}x^{k} + \sum_{k=0}^{\infty}2^{k}x^{k} \\ &= \sum_{k=0}^{\infty}(1 + 2^{k})x^{k} \end{align}$$

所以 $\frac{2 - 3x}{(1 - x)(1 - 2x)}$ 是 $1 + 2^{k}$ 的母函数

---

递推关系的例子

• 递推关系即差分方程
• Hanoi 问题的递推关系

n 位 10 进制数中出现偶数个 5 的数的个数

DP 方程组 :

• $a_{n}$ : n 位 10 进制数中出现偶数个 5 的数的个数
• $b_{n}$ : n 位 10 进制数中出现奇数个 5 的数的个数

$$a_{n} = 9a_{n-1} + b_{n-1} \\ b_{n} = 9b_{n-1} + a_{n-1}$$

初始化 : $a_{1} = 8, b_{1} = 1$

求解过程：

另一种 DP 方程组列法：

将 n 位 10 进制数的 $a_{n}$ 按照尾数分类:

• 尾数不是 5 且出现偶数个 5 的数的个数: $9a_{n-1}$
• 尾数是 5 且出现偶数个 5 的数的个数: $b_{n-1} = 9 \times 10^{n-2} - a_{n-1}$

联立后得到独立的递推关系：

$$a_{n} = 9a_{n-1} + 9\times 10^{n-2} - a_{n-1}$$

求解过程：

计数序列 <==> 母函数 <==> 递推关系

有理分式的分项表达，分母的特征意义

斐波那契数

$$F(0) = 0 \\ F(1) = 1 \\ F(n) = F(n - 1) + F(n - 2)$$

最早原型：用箱子包装长宽为 1 和 2 的物件的可行方法数。

Fibonacci Prime:

• 除了 n = 4, 所有 Fibonacci Prime 序号都是素数
• 不是所有素数序号的斐波那契数都是素数

斐波那契恒等式

(1) $F_{1}^{2} + F_{2}^{2} + … + F_{n}^{2} = F_{n}F_{n+1}$

可以用垒小正方形的方法证明。

(2) $F_{1} + F_{2} + … + F_{n} = F_{n+2} - 1$

递推关系展开，累加每项，累加时可以销项。

(3) $F_{1} + F_{3} + … + F_{2n-1} = F_{2n}$

---

k阶线性常系数齐次递推关系

• 斐波那契数: $F_{n} + F_{n-1} + F_{n-2} = 0$
• 汉诺塔: $h(n) - 3h(n-1) + 2h(n-2) = 0$

共同点：

1. 线性累加和
2. 右端为0
3. 系数是常数

线性常系数齐次递推关系定义

若 $\{a_{n}\}$ 满足:

$$a_{n} + c_{1}a_{n-1} + c_{2}a_{n-2} + ... + c_{k}a_{n-k} = 0 \\ a_{0} = d_{0}, a_{1} = d_{1}, ..., a_{k} = d_{k} \\ c_{0}, c_{1}, ..., c_{k}, d_{0}, d_{1}, ..., d_{k-1} 为常数 \\ c_{k} \neq 0$$

则 $\{a_{n}\}$ 为 k 阶线性常系数齐次递推关系（Linear Homogeneous Recurrence Relation）。

线性常系数齐次递推关系的母函数

若 a 是一元多项式 $f(x^{-1})$ 的根，即 $f(a) = 0$ 成立，则多项式 $f(x^{-1})$ 有一个因式 $x^{-1} - a = (1 - ax) / x$。

推导过程

设 $G(x)$ 为 $\{a_{n}\}$ 的母函数 $G(x) = a_{0} + a_{1}x + … + a_{0}x^{n} + …$

$\{a_{n}\}$ 有线性常系数齐次递推关系

$$ a_{n} + c_{1}a_{n-1} + c_{2}a_{n-2} + ... + c_{k}a_{n-k} = 0 $$

用累加得到母函数表达式：

$$x^{k}(a_{k} + c_{1}a_{k-1} + c_{2}a_{k-2} + ... + c_{k}a_{0}) = 0 \\ x^{k+1}(a_{k+1} + c_{1}a_{k} + c_{2}a_{k-1} + ... + c_{k}a_{1}) = 0 \\ ... \\ x^{n}(a_{n} + c_{1}a_{n-1} + c_{2}a_{n-2} + ... + c_{k}a_{n-k}) = 0 \\ ...$$

得到

$$G(x) - \sum_{i=0}^{k-1}a_{i}x^{i} + c_{1}x(G(x) - \sum_{i=0}^{k-2}a_{i}x^{i}) + ... + c_{k}x^{k}G(x) = 0$$

得到

$$(1 + c_{1}x + c_{2}x^{2} + ... + c_{k}x^{k})G(x) = \sum_{j=0}^{k-1}c_{j}x^{j}\sum_{i=0}^{k-1-j}a_{i}x^{i}$$

令 $P(x) = \sum_{j=0}^{k-1}c_{j}x^{j}\sum_{i=0}^{k-1-j}a_{i}x^{i}$, $P(x)$ 的次数 $\leq k - 1$

$$G(x) = \frac{P(x)}{1 + c_{1}x + c_{2}x^{2} + ... + c_{k}x^{k}}$$ 构造这个 ${P(x)}$ 的主要目的是为了凑出 $(1 - ax)^{-1}$ $$(1 - ax)^{-1} = 1 + ax +a^{2}x^{2} + ...$$

对 $1 + \sum\limits_{i=1}\limits^{k}c_{i}x^{i}$ 的处理

把 $x^{k}$ 提出来，用 m 表示 $x^{-1}$，

$$ C(m) = m^{k} + c_{1}m^{k - 1} + ... +c_{k-1}m + c_{k} $$

$C(m)$ 称为特征多项式, 他有若干个根: $a_{1}, a_{2}, …, a_{i}$

$$C(m) = (m - a_{1})^{k_{1}}(m - a_{2})^{k_{2}}...(m - a_{i})^{k_{i}} \\ k_{1} + k_{2} + ... + k_{i} = k$$

代回去得到：

$$G(x) = \frac{P(x)}{(1-a_{1})^{k_{1}}(1-a_{2})^{k_{2}}...(1-a_{i})^{k_{i}}}$$

原递推关系和特征多项式(两个绿色公式)是一一对应的关系

斐波那契的例子

step1: 把序列作为系数，得到母函数 $G(x) = F_{1}x + F_{2}x^{2} + …$
step2: 通过推理，得到母函数应该为 $g(x) = \frac{x}{1 - x - x^{2}}$
step3: 用到 taylor 展开：$(1 - ax)^{-1} = 1 + ax + a^{2}x^{2} + …$
step4: 用 $(1 - x - x^{2}) = (1 - \frac{1-\sqrt{5}}{2}x)(1 - \frac{1+\sqrt{5}}{2}x)$ 去套 $(1 - ax)^{-1}$

母函数与特征多项式

特征多项式在递推关系和母函数系数之间架起桥梁

• 序列 $a_{0}, a_{1}, a_{2}, …$
• 母函数: $G(x) = a_{0} + a_{1}x + a_{2}x^{2} + …$
• 特征多项式: $C(x) = x^{k} + c_{1}x^{k-1} + c_{2}x^{k-2} + … + c_{k-1}x + c_{k}$
• 递推关系: $a_{n} + c_{1}a_{n-1} + c_{2}a_{n-2} + … + c_{k}a_{n-k} = 0$

1. 特征多项式无重根

$$C_(x) = (x - \alpha_{1})(x - \alpha_{2})...(x - \alpha_{k}) \\$$ $$\begin{align} G_(x) &= \frac{P(x)}{(1 - \alpha_{1}x)(1 - \alpha_{2}x)...(1 - \alpha_{k}x)} \\ &= \frac{A_{1}}{1 - \alpha_{1}x} + \frac{A_{2}}{1 - \alpha_{2}x} + ... + \frac{A_{k}}{1 - \alpha_{k}x} \\ &= \sum_{i=1}^{k}\frac{l_{i}}{1 - \alpha_{i}x} \end{align}$$

其中 $l_{i}, i \in [1, k]$。可以由线性方程组得到：

$$\left\{ \begin{array}{**lr**} l_{1} + l_{2} + ... + l_{k} = d_{0} \\ l_{1}\alpha_{1} + l_{2}\alpha_{2} + ... + l_{k}\alpha_{k} = d_{1} \\ ... \\ l_{1}\alpha_{1}^{k-1} + l_{2}\alpha_{2}^{k-1} + ... + l_{k}\alpha_{k}^{k-1} = d_{k-1} \\ \end{array} \right.$$

其中: $d_{0}, d_{1}, …, d_{k}$ 是 $a_{n}$ 的初始值。

最终结果为：

$$a_{n} = l_{1}\alpha_{1}^{n} + l_{2}\alpha_{2}^{n} + ... + l_{k}\alpha_{k}^{n}$$

2. 特征多项式有重根

例子: $a_{n} - 4a_{n-1} + 4a_{n-2} = 0, a_{0} = 1, a_{1} = 4$

• 法1: 母函数法

用到泰勒公式 $(1 + x)^{\alpha} = \sum_{n=0}^{\infty}\frac{1}{n!}\alpha(\alpha - 1)…(\alpha - n + 1)x^{n}, \alpha \in R$

$$x^{2} : a_{2} = 4a_{1} - 4a_{0} \\ x^{3} : a_{3} = 4a_{2} - 4a_{1} \\ ... \\$$

对母函数做推导和整理之后，得到：

$$G(x) = \frac{1}{1 - 4x + 4x^{2}} = \frac{1}{(1 - 2x)^{2}} = (1 - 2x)^{2} = \sum_{k=0}^{\infty}C_{k+1}^{k}2^{k}x^{k} = \sum_{k=0}^{\infty}(k + 1)2^{k}x^{k}$$

• 法2: 特征根法

特征方程: $x^{2} - 4x + 4 = (x - 2)^{2}$

母函数形式 :

$$\begin{align} G(x) &= \frac{ax + b}{(1 - 2x)^{2}} = \frac{A}{1 - 2x} + \frac{B}{(1 - 2x)^{2}} \\ &= A(1 + 2x + 2^{2}x^{2} + ...) + B(1 + 2x + 2^{2}x^{2} + ...)(1 - 2x + 2^{2}x^{2} + ...) \\ &= A(1 + 2x + 2^{2}x^{2} + ...) + B(1 + 2(2x) + 3(2x)^{2} + ...) \end{align}$$

待定系数解 $a_{n} = A2^{n} + B(n + 1)2^{n}$，得到结果: $a_{n} = (n + 1)^{2n}$

一般情况：$\beta 为 C(x) 的 k 重根$，则 $G(x) = \sum_{j=1}^{k}\frac{A_{j}}{(1 - \beta x)^{j}}$

$x^{n}$ 的系数 $a_{n} = \sum_{j=1}^{k}A_{j}\dbinom{j + n - 1}{n}\beta^{n}$

递推中对应于重根 $\beta$ 的项: $(A_{0} + A_{1}n + … + A_{k-1}n^{k-1})\beta^{n}$

k 个待定系数。

3. 特征多项式有共轭复根

共轭复根：

$$\begin{align} \alpha_{1} = \rho(cos\theta + isin\theta) \\ \alpha_{2} = \bar{\alpha_{1}} = \rho(cos\theta 1 isin\theta) \end{align}$$

对应的通项：

$$A_{1}\alpha_{1}^{n} + A_{2}\alpha_{2}^{n} \\ = (A_{1} + A_{2})\rho^{n}cosn\theta + B\rho^{n}sinn\theta\\$$

其中：$A = A_{1} + A_{2}, B = i(A_{1} - A_{2})$

例子：

$a_{n} + a_{n-1} + a_{n-2}, a_{1} = 1, a_{2} = 0$

特正方程 $x^{2} - x + 1 = 0$

有共轭复根: $cos\frac{\pi}{3} \pm isin\frac{\pi}{3}$

$$a_{n} = A_{1}cos\frac{n\pi}{3} + A_{2}sin\frac{n\pi}{3}$$

将 n = 1, 2 的值代入，解出待定系数。

应用

例1：求 $1 + 2 + 3 + …$

累减法

$$S_{n} - S_{n-1} = n \\ S_{n - 1} - S_{n-2} = n - 1 \\$$

得到

$$S_{n} - 3S_{n-1} + 3S_{n-2} - S_{n-3} = 0 \\ S_{0} = 0, S_{1} = 1, S_{2} = 3$$

特征方程 $m^{3} - 3m^{2} + 3m - 1 = 0$, $m = 1$ 为 3 重根。

$$S_{n} = (A + Bn + Cn^{2})1^{n} = A + Bn + Cn^{2}$$

求待定系数 A, B, C, 当数量多时上行列式

$\sum i^{k}$ 的一般做法： 累减 -> 特征方程 -> 解。

例2: k 种颜色对 n 个区域着色

k 种颜色对 n 个区域着色, 相邻颜色要求不同，求方案数：

(1) $D_{1}$ 与 $D_{n-1}$ 同色

• $D_{n}$ 有 k - 1 种
• $D_{1}$ ~ $D_{n - 2}$ 有 $(k - 1)a_{n-2}$ 种

(2) $D_{1}$ 与 $D_{n-1}$ 不同色

• $D_{n}$ 有 k - 2 种
• $D_{1}$ ~ $D_{n - 1}$ 有 $(k - 2)a_{n-1}$ 种

通过 1 和 2 两类，得到递推关系：$a_{n} = (k - 2)a_{n-1} + (k - 1)a_{n-2}$

列出特征方程：$x^{2} - (k - 2)x - (k - 1) = 0$

出解：$x_{1} = k - 1, x_{2} = -1$

有待定系数的通项公式：$a_{n} = A(k - 1)^{n} + B(-1)^{n}, n \geq 2$

---

---