第 8 章高级计数技术¶

章节导引

本页从《离散数学讲义》拆分而来，保留原章节锚点，方便从旧总览页和旧链接跳转。

学习目标¶

能在直接计数困难时，转向递推、生成函数或容斥模型。

前置知识¶

第 3 章函数增长、第 5 章递归、第 6 章排列组合与二项式系数。

建议用时¶

建议 6–8 小时：递推 2 小时，分治递推 1–2 小时，生成函数 2 小时，容斥/错排 1–2 小时。

练习建议¶

解 2 个线性递推；用生成函数解释一个组合模型；用容斥解决一个带禁位的计数题。

参考资料与引用边界¶

整理者：Lumner。
课程来源：根据 DM/ 目录下的课件整理；本章对应课件：DM8.1-8.2(6).pdf, DM8.3.pdf, DM8.4(6).pdf, DM8.5-8.6(9).pdf。
原始讲义文件：note/离散数学讲义.md。
引用边界：这是公开学习笔记，不替代课程正式教材、教师课件或考试要求；外部引用时请注明来自本网站整理版。

8.0 核心目标¶

本章把计数问题推进到递推关系、分治递推、生成函数和容斥原理。重点是从问题结构中建立方程，再用代数工具求解。

8.1 递推关系的应用¶

递推关系回顾¶

递推关系用先前项定义当前项。一个完整递推问题通常需要：

递推公式。
初始条件。

例如细菌每小时数量翻倍，初始 5 个：

\(a_0=5,\quad a_n=2a_{n-1}\)

解为：

\(a_n=5\cdot2^n\)

兔子问题和 Fibonacci 数¶

理想化兔子繁殖模型可得到：

\(f_n=f_{n-1}+f_{n-2}\)

这类递推出现于许多“当前状态由前两种状态合并而来”的计数问题。

汉诺塔¶

设 \(H_n\) 为移动 \(n\) 个盘子所需最少步数。

移动步骤：

将上面 \(n-1\) 个盘子从源柱移动到辅助柱。
将最大盘子移动到目标柱。
将 \(n-1\) 个盘子从辅助柱移动到目标柱。

所以：

\(H_n=2H_{n-1}+1,\quad H_1=1\)

解得：

\(H_n=2^n-1\)

不含连续 0 的位串¶

设 \(a_n\) 为长度 \(n\) 且不含两个连续 0 的位串数。

按最后一位分类：

以 1 结尾：前 \(n-1\) 位任意合法，有 \(a_{n-1}\) 种。
以 0 结尾：倒数第二位必须为 1，前 \(n-2\) 位任意合法，有 \(a_{n-2}\) 种。

递推：

\(a_n=a_{n-1}+a_{n-2}\)

初始：

\(a_1=2,\quad a_2=3\)

所以 \(a_n\) 与 Fibonacci 数密切相关。

算法与递推¶

递归算法的时间复杂度常由递推关系表示。例如二分搜索：

\(T(n)=T(n/2)+c\)

解得 \(T(n)=O(\log n)\)。

8.2 线性递推关系¶

线性齐次常系数递推¶

k 阶线性齐次常系数递推形如：

\(a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}\)

其中 \(c_i\) 为常数，\(c_k\ne0\)。

尝试形如 \(a_n=r^n\) 的解，代入得到特征方程：

\(r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots-c_k=0\)

二阶不同根¶

若：

\(a_n=c_1a_{n-1}+c_2a_{n-2}\)

特征方程：

\(r^2-c_1r-c_2=0\)

有两个不同根 \(r_1,r_2\)，则通解为：

\(a_n=\alpha_1r_1^n+\alpha_2r_2^n\)

常数由初始条件确定。

Fibonacci 闭式¶

Fibonacci 递推：

\(f_n=f_{n-1}+f_{n-2},\quad f_0=0,\ f_1=1\)

特征方程：

\(r^2-r-1=0\)

根为：

\(\phi=\frac{1+\sqrt5}{2},\quad \psi=\frac{1-\sqrt5}{2}\)

所以：

\(f_n=\frac{\phi^n-\psi^n}{\sqrt5}\)

重根情形¶

若二阶特征方程只有一个根 \(r\)，则通解为：

\(a_n=(\alpha_1+\alpha_2n)r^n\)

更一般地，若根 \(r\) 的重数为 \(m\)，对应项为：

\((\alpha_0+\alpha_1n+\cdots+\alpha_{m-1}n^{m-1})r^n\)

非齐次线性递推¶

非齐次形式：

\(a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}+F(n)\)

通解：

\(a_n=a_n^{(h)}+a_n^{(p)}\)

其中 \(a_n^{(h)}\) 是对应齐次方程通解，\(a_n^{(p)}\) 是一个特解。

例：求前 \(n\) 个正整数和。设 \(a_n=a_{n-1}+n,\ a_0=0\)。可得：

\(a_n=\frac{n(n+1)}2\)

8.3 分治算法与递推¶

分治思想¶

分治算法通常包括：

Divide：把规模 \(n\) 的问题分成若干更小的同类问题。
Conquer：递归解决子问题。
Combine：合并子问题答案。

若分成 \(a\) 个子问题，每个规模为 \(n/b\)，额外处理代价为 \(g(n)\)，常得到：

\(T(n)=aT(n/b)+g(n)\)

二分搜索¶

二分搜索递推：

\(T(n)=T(n/2)+O(1)\)

所以：

\(T(n)=O(\log n)\)

快速整数乘法¶

课件提到快速乘法：把两个 \(2n\) 位整数拆成两半，减少乘法次数。典型例子是 Karatsuba 思想，其复杂度优于普通乘法。

Master Theorem¶

对递推：

\(T(n)=aT(n/b)+f(n)\)

比较 \(f(n)\) 与 \(n^{\log_b a}\)：

若 \(f(n)=O(n^{\log_b a-\varepsilon})\)，则 \(T(n)=\Theta(n^{\log_b a})\)。
若 \(f(n)=\Theta(n^{\log_b a}\log^k n)\)，则 \(T(n)=\Theta(n^{\log_b a}\log^{k+1} n)\)。
若 \(f(n)=\Omega(n^{\log_b a+\varepsilon})\) 且满足正则条件，则 \(T(n)=\Theta(f(n))\)。

这是分析分治算法复杂度的常用工具。

8.4 生成函数¶

定义¶

序列 \(a_0,a_1,a_2,\ldots\) 的普通生成函数为：

\(G(x)=a_0+a_1x+a_2x^2+\cdots=\sum_{n=0}^{\infty}a_nx^n\)

生成函数把序列转化为形式幂级数，便于用代数方式处理计数问题和递推关系。

常见生成函数¶

序列	生成函数
\(1,1,1,\ldots\)	\(\frac1{1-x}\)
\(1,r,r^2,\ldots\)	\(\frac1{1-rx}\)
\(0,1,2,3,\ldots\)	\(\frac{x}{(1-x)^2}\)
\(\binom n0,\binom n1,\ldots,\binom nn\)	\((1+x)^n\)

基本恒等式：

\(\frac1{1-x}=1+x+x^2+\cdots,\quad |x|<1\)

在组合中常作为形式幂级数使用，不一定关注收敛。

扩展二项式定理¶

对实数 \(u\)：

\((1+x)^u=\sum_{k=0}^{\infty}\binom ukx^k\)

其中：

\(\binom uk=\frac{u(u-1)\cdots(u-k+1)}{k!}\)

这可用于处理无限级数和带重复组合。

用生成函数计数¶

例：求非负整数解：

\(x_1+x_2+x_3=r\)

每个变量贡献生成函数：

\(1+x+x^2+\cdots=\frac1{1-x}\)

总生成函数：

\(\frac1{(1-x)^3}\)

\(x^r\) 的系数为：

\(\binom{r+2}{2}\)

这与 stars and bars 结果一致。

有限制的选择¶

若红、蓝、白三种球各最多 \(2r\) 个，要选 \(3r\) 个，生成函数为：

\((1+x+x^2+\cdots+x^{2r})^3\)

答案是 \(x^{3r}\) 的系数。

生成函数的优势是能自然处理“每类对象可选数量有限制”的问题。

用生成函数解递推¶

步骤：

设 \(G(x)=\sum_{n\ge0}a_nx^n\)。
将递推两边乘以 \(x^n\) 并对 \(n\) 求和。
用初始条件处理低阶项。
解出 \(G(x)\)。
展开生成函数，读取 \(a_n\)。

8.5 容斥原理¶

两个和三个集合¶

两个集合：

\(|A\cup B|=|A|+|B|-|A\cap B|\)

三个集合：

\(|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\)

一般容斥公式¶

对有限集合 \(A_1,A_2,\ldots,A_n\)：

\(\left|\bigcup_{i=1}^nA_i\right|=\sum_i|A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap\cdots\cap A_n|\)

思想：单个集合先加，两个集合交集被多加所以减，三个集合交集被减多所以再加，依此交替。

反向计数¶

很多问题问“没有任何坏性质”的对象数。设全集为 \(U\)，\(A_i\) 为具有第 \(i\) 个坏性质的对象集合，则目标为：

\(|U|-|A_1\cup A_2\cup\cdots\cup A_n|\)

再用容斥计算并集大小。

例：不超过 1000 且不被 5、6、8 整除¶

设：

\(A_5=\{x\le1000:5\mid x\}\)

\(A_6=\{x\le1000:6\mid x\}\)

\(A_8=\{x\le1000:8\mid x\}\)

用容斥计算被至少一个整除的数：

\(|A_5|+|A_6|+|A_8|-|A_5\cap A_6|-|A_5\cap A_8|-|A_6\cap A_8|+|A_5\cap A_6\cap A_8|\)

交集用最小公倍数计数，例如：

\(|A_5\cap A_6|=\left\lfloor\frac{1000}{\operatorname{lcm}(5,6)}\right\rfloor\)

最后用 1000 减去该数量。

8.6 容斥的应用¶

满射函数计数¶

从 \(m\) 元集合到 \(n\) 元集合的满射个数。

总函数数：\(n^m\)。

设 \(A_i\) 为没有元素映到第 \(i\) 个陪域元素的函数集合。则满射数为没有任何 \(A_i\) 发生的函数数。

公式：

\(\sum_{j=0}^n(-1)^j\binom nj(n-j)^m\)

也可写为：

\(n!S(m,n)\)

其中 \(S(m,n)\) 是第二类 Stirling 数。

错排¶

错排是没有任何元素留在原位置的排列。

设 \(D_n\) 为 \(n\) 个元素的错排数。由容斥：

\(D_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\)

近似：

\(D_n\approx \frac{n!}{e}\)

更准确地，\(D_n\) 是最接近 \(n!/e\) 的整数。

帽子问题¶

n 个人寄存帽子，取回时随机发还。没有任何人拿到自己帽子的方式数就是错排数 \(D_n\)。

若问概率：

\(\frac{D_n}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}\approx \frac1e\)

本章小结与后续扩展¶

本章已覆盖递推应用、线性递推、分治递推、生成函数、容斥、满射和错排。后续可补充：

更多生成函数系数提取技巧。
非齐次递推的待定系数法例题。
容斥与 Stirling 数的综合题。

第 8 章 高级计数技术¶