第六章 - 高级计数技术
约 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\),则
是递推关系 \(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}\),则
生成函数
定义
数列 \(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\),广义二项式系数
据此,我们可以得到广义二项式定理。
设 \(|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)\)。故有生成函数
利用广义二项式定理进一步变形:
故方法数即为 \(C(r - 1, r - n)\)。
使用生成函数求解递推关系
使用生成函数求解递推关系的一般步骤是:
- 以幂级数形式设出生成函数
- 利用递推关系得到生成函数的封闭形式
- 根据常用生成函数得到封闭形式函数对应的数列
这样的表述是十分概括而抽象的。我们用下面这个例子加以说明:
求解递推关系 \(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}\) 是有穷集,则
这里有必要提及一下容斥原理的证明。
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\),则
映上函数的个数
这里我们需要讨论利用容斥原理解决的两类具体问题。第一类为求映上函数的个数,即两个集合间能建立多少种可能的满射。
考虑一个 \(m\) 元素集合到 \(n\) 元素集合的满射,其中 \(m \geq n\),则可能的满射数为
再从另一个角度思考,从 \(m\) 元素集合到 \(n\) 元素集合的满射等价于:讲定义域中的 \(m\) 个元素分配到 \(n\) 个不可区别的盒子中,并保证每个盒子都不是空的。故根据我们在第五章对这类问题的讨论,我们所求的满射数即为第二类斯特林数 \(S(m, n)\) 再乘上 \(n\) 个元素的集合的排列数,故最终答案也可以表示为 \(n! S(m, n)\)。
错位排列
另一类经典的问题被称作错位排列 (derangement) 问题,即求 \(n\) 个元素没有一个在初始位置上的排列方案数。
这个问题的答案被称作错位排列数,记作 \(D_{n}\),具体为