第六章 - 高级计数技术

约 3015 个字 预计阅读时间 10 分钟

求解线性递推关系

求解常系数线性齐次递推关系

一个常系数的 $k$ 阶线性齐次递推关系 (linear homogeneous recurrence relation) 是形如 $a_{n} = c_{a} a_{n - 1} + c_{2} a_{n - 2} + \cdots + c_{k} a_{n - k}$ 的递推关系，其中 $c_{1}, c_{2}, \cdots, c_{k}$ 是实数，$c_{k} \neq 0$。

这个定义中的递推关系是线性的，因为右式是序列前项的倍数之和；这个递推关系是齐次的，因为所处选的各项都是 $a_{j}$ 的倍数；序列各项的系数都是常数而不是依赖于 $n$ 的函数。

在正式求解之前，我们先给出如下定义。我们按照 $a_{n} = r^{n}$ 的形式代入递推式，得到方程 $r^{n} = c_{1} r^{n - 1} + c_{2} r^{n - 2} + \cdots + c_{k} r^{n - k}$，这个方程称作递推关系的特征方程 (characteristic equation)，方程的解称作递推关系的特征根 (characteristic root)。

现在，我们先考虑二阶线性齐次递推关系。

对于递推关系 $a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2}$，设方程 $r^{2} = c_{1} r + c_{2}$ 的两个根为 $r_{1}$ 和 $r_{2}$。若 $r_{1} \neq r_{2}$，则 $a_{n} = \alpha_{1} r_{1}^{n} + \alpha_{2} r_{2}^{n}$；若 $r_{1} = r_{2} = r_{0}$，则 $a_{n} = \alpha_{1} r_{0}^{n} + \alpha_{2} n r_{0}^{n}$。其中 $\alpha_{1}$ 和 $\alpha_{2}$ 可以根据初始条件解出。

这一定理的证明请读者参阅组合数学相关教科书或网络资料。

进一步地，我们考察更高阶的，也就是一般的情况。

若特征方程 $r^{k} = c_{1} r^{k - 1} + \cdots c_{k}$ 有 $k$ 个不相等的根 $r_{1}, r_{2}, \cdots r_{k}$，则 $a_{n} = \alpha_{1} r_{1}^{n} + \alpha_{2} r_{2}^{n} + \cdots \alpha_{k} r_{k}^{n}$ 是递推关系 $a_{n} = c_{1} a_{n - 1} + \cdots c_{k} a_{n - k}$ 的解。其中 $\alpha_{1}, \alpha_{2}, \cdots \alpha_{k}$ 可以根据初始条件解出。

除此之外，我们还需要了解存在重根的情况。

若特征方程 $r^{k} = c_{1} r^{k - 1} + \cdots c_{k}$ 有 $t$ 个不相等的根 $r_{1}, r_{2}, \cdots r_{t}$，其重数分别为 $m_{1}, m_{2}, \cdots, m_{t}$ 满足 $m_{i} \geq 1, \sum_{i} m_{i} = k$，则

$$\begin{aligned} a_{n} = & (\alpha_{1, 0} + \alpha_{1, 1} n + \cdots + \alpha_{1, m_{1} - 1} n^{m_{1} - 1}) r_{1}^{n} \\ & + (\alpha_{2, 0} + \alpha_{2, 1} n + \cdots + \alpha_{2, m_{2} - 1} n^{m_{2} - 1}) r_{2}^{n} \\ & + \cdots \\ & + (\alpha_{t, 0} + \alpha_{t, 1} n + \cdots + \alpha_{t, m_{t} - 1} n^{m_{t} - 1}) r_{t}^{n} \end{aligned}$$

是递推关系 $a_{n} = c_{1} a_{n - 1} + \cdots c_{k} a_{n - k}$ 的解。其中 $\alpha_{i, j}$ 可以根据初始条件解出。

求解常系数线性非齐次递推关系

形如 $a_{n} = c_{a} a_{n - 1} + c_{2} a_{n - 2} + \cdots + c_{k} a_{n - k} + F(n)$ 的递推关系是常系数线性非齐次递推关系 (linear nonhomogeneous recurrence relation)。对应的 $a_{n} = c_{a} a_{n - 1} + c_{2} a_{n - 2} + \cdots + c_{k} a_{n - k}$ 是「相伴的」齐次递推关系，其在求解非齐次递推关系中发挥了重要作用。

关于常系数线性非齐次递推关系的一个关键事实在于，每个解都是一个特解与相伴的线性齐次递推关系的一个解的和。形式化的定理如下：

如果 $\{ a_{n}^{(p)} \}$ 是常系数线性非齐次递推关系 $a_{n} = c_{a} a_{n - 1} + c_{2} a_{n - 2} + \cdots + c_{k} a_{n - k} + F(n)$ 的一个特解，而 $\{ a_{n}^{(h)} \}$ 是相伴的齐次递推关系的一个解，则原非齐次递推关系的每个解都是 $\{ a_{n}^{(p)} + a_{n}^{(h)} \}$ 的形式。

更进一步地，如果我们能够确定 $F(n)$ 的形式，那么我们可以给出一个更具体的解。

对于线性非齐次递推关系 $a_{n} = c_{a} a_{n - 1} + c_{2} a_{n - 2} + \cdots + c_{k} a_{n - k} + F(n)$，其中 $F(n) = (b_{t} n^{t} + b_{t - 1} n^{t - 1} + \cdots + b_{1} n + b_{0}) s^{n}$。当 $s$ 不是相伴的线性齐次递推关系的特征方程的根时，存在一个形式为 $(p_{t} n^{t} + p_{t - 1} n^{t - 1} + \cdots + p_{1} n + p_{0}) s^{n}$ 的特解；当 $s$ 是相伴的线性齐次递推关系的特征方程的 $m$ 重根时，存在一个形式为 $n^{m} (p_{t} n^{t} + p_{t - 1} n^{t - 1} + \cdots + p_{1} n + p_{0}) s^{n}$ 的特解。

分治递推关系

假设一个递归算法把一个规模为 $n$ 的问题分成 $a$ 个子问题，其中每个子问题的规模是 $\frac{n}{b}$。将每个子问题的解组合成原来问题的解的算法需要总量为 $g(n)$ 的额外运算。则求解规模为 $n$ 的问题所需的运算数的总量 $f(n)$ 满足递推关系 $f(n) = a f(\frac{n}{b}) + g(n)$。这样的关系称作分治递推关系 (divide-and-conquer recurrence relation)。

我们直接给出一类 $g(n) = c b^{dk}$ 时 $f(n)$ 的阶。这个定理非常重要，被称作主定理 (master theorem)。

设 $f$ 满足递推关系 $f(n) = a f(\frac{n}{b}) + c n^{d}$，其中 $n = b^{k}$，则

$$f(n) = \begin{cases} O(n^{d}), & a < b^{d} \\ O(n^{d} \log n), & a = b^{d} \\ O(n^{\log_{b} a}), & a > b^{d} \end{cases}$$

生成函数

定义

数列 $a_{0}, a_{1}, \cdots, a_{k}, \cdots$ 的生成函数 (generating function) 是无穷级数 $G(x) = a_{0} + a_{1} x + \cdots + a_{k} x^{k} + \cdots = \sum_{k = 0}^{\infty} a_{k} x^{k}$。

特别地，这样的生成函数称作普通生成函数。因为事实上还存在其他形式的生成函数。

另一种常用的生成函数是指数生成函数，即为无穷级数 $\hat{G}(x) = a_{0} + a_{1} \frac{x}{1!} + a_{2} \frac{x^{2}}{2!} + a_{3} \frac{x^{3}}{3!} + \cdots = \sum_{k = 0}^{\infty} a_{k} \frac{x^{k}}{k!}$

通过之后的讨论，我们可以发现指数生成函数常用于基于 $e^{x}$ 变形得到的生成函数。

同时，为了后续的数学表示简便，我们还定义广义二项式系数。对于实数 $u$ 和非负整数 $k$，广义二项式系数

$${u \choose k} = \begin{cases} \frac{u (u - 1) \cdots (u - k + 1)}{k!}, & k > 0 \\ 1, & k = 0 \end{cases}$$

据此，我们可以得到广义二项式定理。

设 $|x| < 1$，则 $(1 + x)^{u} = \sum_{k = 0}^{\infty} {u \choose k} x^{k}$。

性质

当用生成函数求解计数问题时，通常将它们视作形式幂级数，即不考察其收敛性，而只将其当作运算对象。

我们首先需要了解两个生成函数是怎样相加和相乘的，事实上处理方法和幂级数是一致的。令 $f(x) = \sum_{k = 0}^{\infty} a_{k} x^{k}, g(x) = \sum_{k = 0}^{\infty} b_{k} x^{k}$，则 $f(x) + g(x) = \sum_{k = 0}^{\infty} (a_{k} + b_{k}) x^{k}, f(x) g(x) = \sum_{k = 0}^{\infty} (\sum_{j = 0}^{k} a_{j} b_{k - j}) x^{k}$。

我们给出如下常用的生成函数。

$G(x)$	$a_{k}$
$(1 + x)^{n} = \sum_{k = 0}^{n} C(n, k) x^{k} = 1 + C(n, 1) x + C(n, 2) x^{2} + \cdots + x^{n}$	$C(n, k)$
$(1 + ax)^{n} = \sum_{k = 0}^{n} C(n, k) a^{k} x^{k} = 1 + C(n, 1) ax + C(n, 2) a^{2} x^{2} + \cdots + a^{n} k^{n}$	$C(n, k) a^{k}$
$(1 + x^{r})^{n} = \sum_{k = 0}^{n} C(n, k) x^{rk} = 1 + C(n, 1) x^{r} + C(n, 2) x^{2r} + \cdots + x^{rn}$	若 $r \mid k$，则 $C(n, \frac{k}{r})$；否则为 $0$
$\frac{1 - x^{n + 1}}{1 - x} = \sum_{k = 0}^{n} x^{k} = 1 + x + x^{2} + \cdots + x^{n}$	若 $k \leq n$，则为 $1$；否则为 $0$
$\frac{1}{1 - x} = \sum_{k = 0}^{\infty} x^{k} = 1 + x + x^{2} + \cdots$	$1$
$\frac{1}{1 - ax} = \sum_{k = 0}^{\infty} a^{k} x^{k} = 1 + ax + a^{2} x^{2} + \cdots$	$a^{k}$
$\frac{1}{1 - x^{r}} = \sum_{k = 0}^{\infty} x^{rk} = 1 + x^{r} + x^{2r} + \cdots$	若 $r \mid k$，则为 $1$；否则为 $0$
$\frac{1}{(1 - x)^{2}} = \sum_{k = 0}^{\infty} (k + 1) x^{k} = 1 + 2x + 3x^{2} + \cdots$	$k + 1$
$\frac{1}{(1 - x)^{n}} = \sum_{k = 0}^{\infty} C(n + k - 1, k) x^{k} = 1 + C(n, 1) x + C(n + 1, 2) x^{2} + \cdots$	$C(n + k - 1, k) = C(n + k - 1, n - 1)$
$\frac{1}{(1 + x)^{n}} = \sum_{k = 0}^{\infty} C(n + k - 1, k) x^{k} = 1 - C(n, 1) x + C(n + 1, 2) x^{2} - \cdots$	$(-1)^{k} C(n + k - 1, k) = (-1)^{k} C(n + k - 1, n - 1)$
$\frac{1}{(1 - ax)^{n}} = \sum_{k = 0}^{\infty} C(n + k - 1, k) a^{k} x^{k} = 1 + C(n, 1) ax + C(n + 1, 2) a^{2} x^{2} + \cdots$	$C(n + k - 1, k) a^{k} = C(n + k - 1, n - 1) a^{k}$
$e^{x} = \sum_{k = 0}^{\infty} \frac{x^{k}}{k!} = 1 + x + \frac{x^{2}}{2} + \frac{x^{3}}{6} + \cdots$	$\frac{1}{k!}$
$\ln (1 + x) = \sum_{k = 0}^{\infty} \frac{(-1)^{k + 1}}{k} x^{k} = x - \frac{x^{2}}{2} + \frac{x^{3}}{3} - \frac{x^{4}}{4} + \cdots$	$\frac{(-1)^{k + 1}}{k}$

计数问题与生成函数

生成函数可以用于求解各种计数问题。

我们先来看一类问题，求 $e_{1} + e_{2} + \cdots + e_{n} = C$ 的解，其中 $e_{i}$ 为有受到约束的非负整数，$C$ 为常数。我们用下面这个例子来展示生成函数的使用方法。

求 $e_{1} + e_{2} + e_{3} = 17$ 的解的个数，其中 $e_{1}. e_{2}, e_{3}$ 为非负整数，且满足 $2 \leq e_{1} \leq 5, 3 \leq e_{2} \leq 6, 4 \leq e_{3} \leq 7$。

考察生成函数 $(x^{2} + x^{3} + x^{4} + x^{5})(x^{3} + x^{4} + x^{5} + x^{6})(x^{4} + x^{5} + x^{6} + x^{7})$，则原题的答案即为该生成函数中 $x^{17}$ 这一项的系数。

进一步地，我们使用生成函数解决这类问题中的一个典型问题，求出从 $n$ 类不同物体中选择 $r$ 个物体，且每类物体至少选 $1$ 个的方式数。

记 $a_{r}$ 为从 $n$ 类不同物体中选择 $r$ 个物体，且每类物体至少选 $1$ 个的方式数。因为每类物体至少需要选 $1$ 个，因此这 $n$ 个类中每类物体都对序列 $\{ a_{r} \}$ 的生成函数 $G(x)$ 贡献了因子 $(x + x^{2} + x^{3} + \cdots)$。故有生成函数

$$G(x) = (x + x^{2} + x^{3} + \cdots)^{n} = x^{n} (1 + x + x^{2} + \cdots)^{n} = \frac{x^{n}}{(1 - x)^{n}}$$

利用广义二项式定理进一步变形：

$$\begin{aligned} G(x) & = \frac{x^{n}}{(1 - x)^{n}} \\ & = x^{n} (1 - x)^{-n} \\ & = x^{n} \sum_{r = 0}^{\infty} {{-n} \choose {r}} (-x)^{r} \\ & = x^{n} \sum_{r = 0}^{\infty} (-1)^{r} C(n + r - 1, r) (-1)^{r} x^{r} \\ & = \sum_{r = 0}^{\infty} C(n + r - 1, r) x^{r} \\ & = \sum_{r = n}^{\infty} C(r - 1, r - n) x^{r} \end{aligned}$$

故方法数即为 $C(r - 1, r - n)$。

使用生成函数求解递推关系

使用生成函数求解递推关系的一般步骤是：

1. 以幂级数形式设出生成函数
2. 利用递推关系得到生成函数的封闭形式
3. 根据常用生成函数得到封闭形式函数对应的数列

这样的表述是十分概括而抽象的。我们用下面这个例子加以说明：

求解递推关系 $a_{0} = 2, a_{k} = 3 a_{k - 1}$。

设 $G(x)$ 是 $\{ a_{n} \}$ 的生成函数，即 $G(x) = \sum_{k = 0}^{\infty} a_{k} x_{k}$。

则根据递推关系，有 $G(x) - 3x G(x) = a_{0} = \sum_{k = 1}^{\infty} (a_{k} - 3a_{k - 1}) x^{k} = 2$，于是变形得到 $G(x)$ 的封闭形式 $G(x) = \frac{2}{1 - 3x}$。

与常用生成函数 $\frac{1}{1 - ax} = \sum_{k = 0}^{\infty} a^{k} x^{k}$ 比较，得到 $G(x) = \sum_{k = 0}^{\infty} 2 \cdot 3^{k} x^{k}$。故 $a_{k} = 2 \cdot 3^{k}$。

容斥

在第五章中，我们已经介绍过容斥原理的简单形式。接下来我们将讨论更一般情况下的容斥原理。

容斥原理

设 $A_{1}, A_{2}, \cdots, A_{n}$ 是有穷集，则

$$\begin{aligned} |A_{1} \cup A_{2} \cup \cdots \cup A_{n}| = & \sum_{1 \leq i \leq n} |A_{i}| - \sum_{1 \leq i < j \leq n} |A_{i} \cap A_{j}| \\ & + \sum_{1 \leq i < j < k \leq n} |A_{i} \cap A_{j} \cap A_{k}| - \cdots \\ & + (-1)^{n + 1} |A_{1} \cap A_{2} \cap \cdots \cap A_{n}| \end{aligned}$$

这里有必要提及一下容斥原理的证明。

Proof

我们考察左式中每个元素在右式中被计数的次数。

设 $a \in |A_{1} \cup A_{2} \cup \cdots \cup A_{n}|$，假设其恰好为 $A_{1}, A_{2}, \cdots, A_{n}$ 中 $r$ 个集合的元素。则 $a$ 被右式中第一项 $\sum_{1 \leq i \leq n} |A_{i}|$ 计数了 $C(r, 1)$ 次，被第二项 $-\sum_{1 \leq i < j \leq n} |A_{i} \cap A_{j}|$ 计数了 $C(r, 2)$ 次。以此类推，其在右式中最终被计数的次数为 $C(r, 1) - C(r, 2) + \cdots + (-1)^{r + 1} C(r, r)$。

根据组合数的恒等式 $C(r, 0) - C(r, 1) + C(r, 2) - \cdots + (-1)^{r} C(r, r) = 0$，得到上式 $C(r, 1) - C(r, 2) + \cdots + (-1)^{r + 1} C(r, r) = C(r, 0) = 1$。

因此，左式中每个元素恰好在右式中被计数 $1$ 次。即证。

容斥原理的另一种形式

设 $A_{i}$ 是具有性质 $P_{i}$ 的元素的子集。同时具有性质 $P_{i_{1}}, P_{i_{2}}, \cdots, P_{i_{k}}$ 的元素数记为 $N(P_{i_{1}} P_{i_{2}} \cdots P_{i_{k}})$，即 $|A_{i_{1}} \cap A_{i_{2}} \cap \cdots \cap A_{i_{k}}| = N(P_{i_{1}} P_{i_{2}} \cdots P_{i_{k}})$。

同时不具有性质 $P_{i_{1}}, P_{i_{2}}, \cdots, P_{i_{k}}$ 的元素数记为 $N(P_{i_{1}}' P_{i_{2}}' \cdots P_{i_{k}}')$，全集中的元素数记为 $N$，则

$$\begin{aligned} N(P_{1}' P_{2}' \cdots P_{n}') & = N - |A_{1} \cup A_{2} \cup \cdots \cup A_{n}| \\ & = N - \sum_{1 \leq i \leq n} N(P_{i}) + \sum_{1 \leq i < j \leq n} N(P_{i} P_{j}) - \cdots + (-1)^{n} N(P_{1} P_{2} \cdots P_{n}) \end{aligned}$$

映上函数的个数

这里我们需要讨论利用容斥原理解决的两类具体问题。第一类为求映上函数的个数，即两个集合间能建立多少种可能的满射。

考虑一个 $m$ 元素集合到 $n$ 元素集合的满射，其中 $m \geq n$，则可能的满射数为

$$n^{m} - C(n, 1)(n - 1)^{m} + C(n, 2)(n - 2)^{m} - \cdots + (-1)^{n - 1} C(n, n - 1) 1^{m}$$

再从另一个角度思考，从 $m$ 元素集合到 $n$ 元素集合的满射等价于：讲定义域中的 $m$ 个元素分配到 $n$ 个不可区别的盒子中，并保证每个盒子都不是空的。故根据我们在第五章对这类问题的讨论，我们所求的满射数即为第二类斯特林数 $S(m, n)$ 再乘上 $n$ 个元素的集合的排列数，故最终答案也可以表示为 $n! S(m, n)$。

错位排列

另一类经典的问题被称作错位排列 (derangement) 问题，即求 $n$ 个元素没有一个在初始位置上的排列方案数。

这个问题的答案被称作错位排列数，记作 $D_{n}$，具体为

$$D_{n} = n! \left[ 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^{n} \frac{1}{n!} \right]$$