专栏文章

【离散数学及其应用】课程笔记

wwishapig许愿中
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mlmkub8g
此快照首次捕获于
2026/02/15 01:15
4 天前
此快照最后确认于
2026/02/19 01:16
11 小时前
查看原文
成绩 96/10096/100，绩点 5.05.0
这是大一下的课，补一部分的笔记（由于这门课有较多知识点对 oier 来说是常识，因此笔记只有某几章内容）

第四章 数论和密码学

4.1 整除性和模运算（Divisibility and Modular Arithmetic）

4.1.2 Division
定义 1. 设 a,b∈Z,a≠0a,b\in \mathbb{Z},a\not=0，则称 a∣ba|b 当且仅当 ba\dfrac{b}{a} 为整数（aa divides bb），称 aa 为 bb 的一个因子（divisor/factor），bb 为 aa 的一个倍数（multiple）
定理 1. 设 a,b,c∈Z,a≠0a,b,c\in \mathbb{Z},a\not=0，则：
  1. a∣b,a∣c⇒a∣(b+c)a|b,a|c\Rightarrow a|(b+c)
  2. a∣b⇒a∣(bc)a|b\Rightarrow a|(bc)
  3. a∣b,b∣c⇒a∣ca|b,b|c\Rightarrow a|c
推论 1. 设 a,b,c∈Z,a≠0a,b,c\in \mathbb{Z},a\not= 0，则：a∣b,a∣c⇒a∣(mb+nc) (m,n∈Z)a|b,a|c\Rightarrow a|(mb+nc)\ (m,n\in \mathbb{Z})
4.1.3 The Division Algorithm
定理 2. 设 a∈Z,d∈Z+a\in \mathbb{Z},d\in \mathbb{Z}^{+}，则存在唯一的一对整数 q,rq,r，满足 a=dq+ra=dq+r，其中 0≤r<d0\le r<d
定义 2. 在上一条中，称 dd 为除数（divisor），aa 为被除数（dividend），qq 为商（quotient），rr 为余数（remainder），写为：q=a div⁡ bq=a\ \operatorname{div}\ b，r=a mod⁡ dr=a\ \operatorname{mod}\ d
4.1.4 Modular Arithmetic
定义 3. 设 a,b∈Z,m∈Z+a,b\in \mathbb{Z},m\in \mathbb{Z}^+，则称 a,ba,b 在模 mm 下同余当且仅当 m∣(a−b)m|(a-b)，a≡b(modm)a\equiv b\pmod m（aa is congruent to bb modulo mm）称 a≡b(modm)a\equiv b\pmod m 为同余式（congruence），其中 mm 为模数（modulus/moduli(pl.)）
定理 3. 设 a,b∈Z,m∈Z+a,b\in \mathbb{Z},m\in \mathbb{Z}^+，则 a≡b(modm)⇔a mod⁡ m=b mod⁡ ma\equiv b\pmod m\Leftrightarrow a\ \operatorname{mod}\ m=b\ \operatorname{mod}\ m
定理 4. 设 a,b∈Z,m∈Z+a,b\in \mathbb{Z},m\in \mathbb{Z}^+，则 a≡b(modm)⇔∃k∈Z,a=b+kma\equiv b\pmod m\Leftrightarrow \exist k\in \mathbb{Z},a=b+km
定理 5. 设 m∈Z+m\in \mathbb{Z}^+，且 a≡b(modm),c≡d(modm)a\equiv b\pmod m,c\equiv d\pmod m，则 a+c≡b+d(modm),ac≡bd(modm)a+c\equiv b+d\pmod m,ac\equiv bd\pmod m
推论 2. 设 a,b∈Z,m∈Z+a,b\in \mathbb{Z},m\in \mathbb{Z}^+，则 (a+b)mod⁡m=((amod⁡m)+(bmod⁡m))mod⁡m(a+b)\operatorname{mod}m=((a\operatorname{mod}m)+(b\operatorname{mod} m))\operatorname{mod}m，(ab)mod⁡m=((amod⁡m)×(bmod⁡m))mod⁡m(ab)\operatorname{mod}m=((a\operatorname{mod}m)\times (b\operatorname{mod} m))\operatorname{mod}m
4.1.5 Arithmetic Modulo mm
在模 mm 意义下，(Z,+m)(\mathbb{Z},+_m) 构成交换群（commutative group），(Z,+m,×m)(\mathbb{Z},+_m,\times_m) 构成交换环（commutative ring）
其满足：封闭性（closure），结合律（associativity），交换律（commutativity），存在单位元（identity elements），存在加法逆元（addictive inverses），分配律（distributivity）

4.2 整数的表示及相关算法（Integer Representation and Algorithms）

4.2.2 Representations of Integers
定理 1. 设 b∈Z,b>1,n∈Z+b\in \mathbb{Z},b>1,n\in \mathbb{Z}^+，则存在唯一的表示：n=akbk+ak−1bk−1+⋯+a1b+a0n=a_kb^k+a_{k-1}b^{k-1}+\cdots +a_1b+a_0，其中 k,ai∈N,ai<b,ak≠0k,a_i\in \mathbb{N},a_i<b,a_k\not=0，称为 nn 的 bb 进制表示（base bb expansion of nn）
当 b=2b=2 时为二进制表示（binary expansion）
当 b=8b=8 时为八进制表示（octal expansion）
当 b=10b=10 时为十进制表示（decimal expansion）
当 b=16b=16 时为十六进制表示（hexadecimal expansion）

4.3 质数和最大公约数（Primes and Greatest Common Divisors）

4.3.2 Primes
定义 1. 设 p∈N,p>1p\in \mathbb{N},p>1，称 pp 为质数（prime）当且仅当 pp 的正因子只有 11 和 pp；设 p′∈N+p'\in \mathbb{N}^+ 且 p′p' 不是质数，则称 p′p' 为合数（composite）
定理 1. 算术基本定理（The Fundamental Theorem of Arithmetic） 任意大于 11 的整数都可以唯一写成若干个质数之积
4.3.3 Trial Division
定理 2. 若 nn 为一个大于 11 的合数，则 nn 存在一个 ≤n\le \sqrt{n} 的质因子
4.3.4 The Sieve of Eratosthenes
定理 3. 质数有无穷多个（证明略）
定理 4. 设 π(n)\pi(n) 为 ≤n\le n 的质数个数，则 π(n)∼nln⁡n(n→∞)\pi (n)\sim \dfrac{n}{\ln n}(n\rightarrow \infty)
4.3.6 Greatest Common Divisors and Least Common Multiple
定义 2. 设 a,ba,b 为不同时为 00 的整数，设 dd 为最大的能同时整除 a,ba,b 的整数，则称 dd 为 a,ba,b 的最大公约数（greatest common divisor），记为 d=gcd⁡(a,b)d=\gcd(a,b)
定义 3. 整数 a,ba,b 互质，当且仅当 gcd⁡(a,b)=1\gcd(a,b)=1
定义 4. nn 个整数 a1,a2,⋯ ,ana_1,a_2,\cdots ,a_n 两两互质，当且仅当 gcd⁡(ai,aj)=1(1≤i<j≤n)\gcd(a_i,a_j)=1(1\le i<j\le n)
定义 5. 设 a,ba,b 为两个正整数，设 dd 为最小的能同时被 a,ba,b 整除的整数，则称 dd 为 a,ba,b 的最小公倍数（least common multiple），记为 d=lcm⁡(a,b)d=\operatorname{lcm}(a,b)
定理 5. 设 a,ba,b 为两个正整数，则 ab=gcd⁡(a,b)×lcm⁡(a,b)ab=\gcd(a,b)\times \operatorname{lcm}(a,b)
4.3.7 The Euclidean Algorithm
引理 1. 设 a=bq+r(a,b,q,r∈Z)a=bq+r(a,b,q,r\in \mathbb{Z})，则 gcd⁡(a,b)=gcd⁡(b,r)\gcd(a,b)=\gcd(b,r)
4.3.8 gcds as Linear Combinations
定理 6. 裴蜀定理（Bézout's Theorem） 若 a,b∈N+a,b\in \mathbb{N}^+，则存在 s,t∈Zs,t\in \mathbb{Z}，满足 gcd⁡(a,b)=sa+tb\gcd(a,b)=sa+tb，其中 s,ts,t 称为裴蜀系数（Bézout coefficients）
引理 2. 设 a,b,c∈N+a,b,c\in \mathbb{N}^+，若 gcd⁡(a,b)=1,a∣(bc)\gcd(a,b)=1,a|(bc)，则 a∣ca|c
引理 3. 设 pp 为质数，若 p∣(a1a2⋯an)p|(a_1a_2\cdots a_n)，则存在 i∈[1,n]i\in [1,n]，满足 p∣aip|a_i
定理 7. 设 m∈N+,a,b,c∈Zm\in \mathbb{N}^+,a,b,c\in \mathbb{Z}，若 ac≡bc(modm)ac\equiv bc\pmod m 且 gcd⁡(c,m)=1\gcd(c,m)=1，则 a≡b(modm)a\equiv b\pmod m（这条定理说明当 c,mc,m 互质时存在乘法逆元 c−1c^{-1}，满足 cc−1≡1(modm)cc^{-1}\equiv 1\pmod m）

4.4 求解同余式（Solving Congruences）

4.4.2 Linear Congruences
定理 1. 若 a,m(m>1)a,m(m>1) 互质，则 aa 在 mod m\bmod m 意义下的乘法逆元存在且唯一
4.4.3 The Chinese Remainder Theorem
定理 2. 中国剩余定理（The Chinese Remainder Theorem）
设 m1,m2,⋯ ,mnm_1,m_2,\cdots, m_n 是 nn 个两两不同的质数，则同余方程组：
{x≡a1(modm1)x≡a2(modm2)     ⋮x≡an(modmn)\begin{cases} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2}\\ \ \ \ \ \ \vdots\\ x\equiv a_n\pmod {m_n} \end{cases}
存在唯一解 x≡∑aiMi(Mi−1(modmi))(modM)x\equiv\sum a_iM_i(M_i^{-1}\pmod {m_i})\pmod M，其中 M=∏miM=\prod m_i，Mi=MmiM_i=\dfrac{M}{m_i}
4.4.5 Fermat's Little Theorem
定理 3. 费马小定理（Fermat's Little Theorem） 设 pp 为质数，aa 不为 pp 的倍数，则 ap−1≡1(modp)a^{p-1}\equiv 1\pmod p 或 ap≡a(modp)a^p\equiv a\pmod p
4.4.6 Pseudoprimes
定义 1. 设 b∈N+b\in \mathbb{N}^+，nn 为一个正合数，若 bn−1≡1(modn)b^{n-1}\equiv 1\pmod n，则称 nn 为以 bb 为基下的伪素数
定义 2. 设 nn 为一个正合数，若对所有 gcd⁡(n,b)=1\gcd(n,b)=1 的 bb 均有 bn−1≡1(modn)b^{n-1}\equiv 1 \pmod n，则称 nn 为一个 Carmichael Number
4.4.7 Primitive Roots and Discrete Logarithms
定义 3. 对质数 pp，若 rk(k=0,1,2,⋯ ,p−1)r^k(k=0,1,2,\cdots, p-1) 在 mod p\bmod p 下两两不同，则称 rr 为一个 mod p\bmod p 意义下的原根（primitive root）
定义 4. 设 pp 为质数，rr 为一个 mod p\bmod p 意义下的原根，a∈[1,p−1]a\in [1,p-1]，若 re≡a(modp)(0≤e<p)r^e\equiv a \pmod p(0\le e<p)，则称 ee 为 aa 对 rr 的离散对数（Discrete Logarithm），即为 e=log⁡rae=\log_ra

第六章 计数

6.1 计数基础（The Basic of Counting）

6.1.2 Basic Counting Principles

  • 乘法原理：分步
  • 加法原理：分类

6.1.4 The Subtraction Rule（Inclusion-Exclusion for Two Sets）

∣A1∪A2∣=∣A1∣+∣A2∣−∣A1∩A2∣|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|

6.1.6 Tree Diagrams

用树形图来展示所有的可能性（类似 Trie 树）

6.2 鸽巢原理（The Pigeonhole Principle）

6.2.1 Introduction

定理 1. ≥k+1\ge k+1 个物品放入 kk 个盒子中，则至少有一个盒子放了至少 22 个物品
推论 1. 由 ≥k+1\ge k+1 个元素的集合到 kk 个元素的集合的所有函数都不是一对一的（one-to-one）

6.2.2 The Generalized Pigeonhole Principle

定理 2. nn 个物品放入 kk 个盒子中，则至少有一个盒子放了至少 ⌈nk⌉\left\lceil\dfrac{n}{k}\right\rceil 个物品

6.2.3 Some Elegant Applications of the Pigeonhole Principle

定理 3. 任意一个长为 n2+1n^2+1 的序列（序列中元素两两不同），则存在一个长为 n+1n+1 的严格单增或严格单减子序列

6.3 排列和组合（Permutations and Combinations）

6.3.2 Permutations

定理 1. 设 n,rn,r 均为正整数且 1≤r≤n1\le r\le n，则存在 P(n,r)=n(n−1)(n−2)⋯(n−r+1)P(n,r)=n(n-1)(n-2)\cdots(n-r+1) 种不同的 nn 个元素的长为 rr 的排列
推论 1. P(n,r)=n!(n−r)!P(n,r)=\dfrac{n!}{(n-r)!}

6.3.3 Combinations

定理 2. 设 n,rn,r 均为正整数且 1≤r≤n1\le r\le n，则存在 C(n,r)=n!r!(n−r)!C(n,r)=\dfrac{n!}{r!(n-r)!} 种不同的 nn 个元素的长为 rr 的组合
推论 2. C(n,r)=C(n,n−r)C(n,r)=C(n,n-r)
定义 1. combinatorial proof：利用组合意义或通过建立双射完成证明的手段

6.4 二项式系数及恒等式（Binomial Coefficients and Identities）

6.4.1 The Binomial Theorem

定理 1. 二项式定理（The Binomial Theorem）
(x+y)n=∑i=0n(ni)xiyn−i(x+y)^n=\sum_{i=0}^n\binom{n}{i}x^iy^{n-i}
推论 1. ∑i=0n(ni)=(1+1)n=2n\sum_{i=0}^n\binom{n}{i}=(1+1)^n=2^n
推论 2. ∑i=0n(ni)(−1)n=(1−1)n=[n=0]\sum_{i=0}^n\binom{n}{i}(-1)^n=(1-1)^n=[n=0]
推论 1. ∑i=0n(ni)2n=(2+1)n=3n\sum_{i=0}^n\binom{n}{i}2^n=(2+1)^n=3^n

6.4.2 Pascal's Identity and Triangle

定理 2. 帕斯卡恒等式（Pascal's Identity） 设 n,k≥1,n≥kn,k\ge 1,n\ge k 则
(nk)=(n−1k)+(n−1k−1)\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}
（讨论 nn 个元素中的某个元素有没有选即可）

6.4.3 Other Identities Involving Binomial Coefficients

定理 3. 范德蒙德恒等式（Vandermonde‘s identity）
(m+nr)=∑k=0r(mk)(nr−k)\binom{m+n}{r}=\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}
（从 m+nm+n 个物品中选 kk 个，则考虑分别从 mm 个和 nn 个物品中选了 kk 个和 r−kr-k 个）
（需要扩展组合数的定义到 n,m≤0n,m\le 0 或 n≤mn\le m 的情况，不过这些都是平凡的）
推论 4. ∑k=0n(nk)2=(2nn)\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}
定理 4. (n+1m+1)=∑k=mn(km)\binom{n+1}{m+1}=\sum_{k=m}^n\binom{k}{m}（列向前缀和有封闭形式，行向前缀和无封闭形式）

6.5 广义排列组合（Generalized Permutations and Combinations）

6.5.2 Permutations with Repetition

定理 1. 长为 rr 的 nn 个元素的排列，允许元素重复，则排列数为 nrn^r

6.5.3 Combinations with Repetition

定理 2. 长为 rr 的 nn 个元素的组合，允许元素重复，则组合数为 (n+r−1n−1)\binom{n+r-1}{n-1}
证明：对 rr 进行查板，划分成 nn 个可以为空的部分

6.5.4 Permutations with Indistinguishable Objects

定理 3. 多重组合数，有 n1n_1 个物品 11，n2n_2 个物品 22，⋯\cdots，nmn_m 个物品 mm，则它们的排列数为：
(nn1,n2,⋯ ,nm)=n!∏i=1mni!       (n=∑i=1mni)\binom{n}{n_1,n_2,\cdots,n_m}=\dfrac{n!}{\prod_{i=1}^m n_i!}\ \ \ \ \ \ \ \left(n=\sum_{i=1}^m n_i\right)

6.5.5 Distributing Objects into Boxes

  1. 盒子可区分，小球可区分 则设第 ii 个盒子个小球，共有 n=∑nin=\sum n_i 个小球，则方案数即为广义组合数 (nn1,⋯)\binom{n}{n_1,\cdots}
  2. 盒子可区分，小球不可区分 则此时我们只关注每个盒子里放了多少个球，换言之，求 x1+x2+⋯+xm=nx_1+x_2+\cdots+x_m=n 的解个数 若 xi≥0x_i\ge0，则方案数为 (n+m−1m−1)\binom{n+m-1}{m-1}
  3. 盒子不可区分，小球可区分 将 nn 个可区分的小球放到 mm 个不可区分的盒子中，每个盒子至少放一个 则方案数为第二类斯特林数 {nm}{n\brace m}，有边界条件，递推关系，表达式如下，可以使用二项式反演或容斥原理推导（本质相同）
    {00}=1{n0}=0   (n≥1){nm}={n−1m−1}+m{n−1m}{nm}=1m!∑k=0m(−1)k(mk)(m−k)n\begin{aligned} &{0\brace 0}=1\\ &{n\brace 0}=0\ \ \ (n\ge 1)\\ &{n\brace m}={n-1\brace m-1}+m{n-1\brace m}\\ &{n\brace m}=\dfrac{1}{m!}\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n \end{aligned}
    若允许盒子有空，则方案数为斯特林数一行的前缀和

第八章 高级计数技巧

8.1 递推式的应用（Applications of Recurrence Relations）

  • 汉诺塔问题：Hn=2Hn+1H_n=2H_n+1，H1=1H_1=1
  • 卡特兰数问题（合法括号序列数）：Catn=∑k=0n−1Catk⋅Catn−k−1Cat_n=\sum_{k=0}^{n-1}Cat_k\cdot Cat_{n-k-1}，Cat0=Cat1=1Cat_0=Cat_1=1

8.2 求解线性递推式（Solving Linear Recurrence Relations）

8.2.1 Introduction

定义 1. 常系数 kk 阶齐次线性递推（linear homogeneous recurrence of degree kk with constant coefficients）
an=c1an−1+c2an−2+⋯+ckan−ka_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}
其中 cic_i 为常数，ck≠0c_k\not=0，且需要提供初始条件 a0∼ak−1a_0\sim a_{k-1}

8.2.2 Solving Linear Homogeneous Recurrence Relations with constant coefficients

定理 1. 对递推式 an=c1an−1+c2an−2a_n=c_1a_{n-1}+c_2a_{n-2}，若 r1,r2r_1,r_2 是方程 x2−c1x−c2=0x^2-c_1x-c_2=0 的两个不同的根，则 ana_n 可写为 an=α1r1n+α2r2na_n=\alpha_1r_1^n+\alpha_2r_2^n，其中 α1,α2\alpha_1,\alpha_2 均为常数
定理1. 补充说明 对递推式 an=c1an−1+c2an−2+⋯+ckan−ka_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}，称方程 xk−c1xk−1−c2xk−2−⋯−ck=0x^k-c_1x^{k-1}-c_2x^{k-2}-\cdots-c_k=0 为其特征方程（characteristic equation），这个方程的根称为特征根（characteristic roots）
定理 2. 对递推式 an=c1an−1+c2an−2(c2≠0)a_n=c_1a_{n-1}+c_2a_{n-2}(c_2\not=0)，若其特征方程有一个重根 r0r_0，则 ana_n 可写为 an=α1r0n+α2nr0na_n=\alpha_1r_0^n+\alpha_2nr_0^n，其中 α1,α2\alpha_1,\alpha_2 均为常数
定理 3. 对递推式 an=c1an−1+c2an−2+⋯+ckan−ka_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}，若其特征方程有 kk 个不同的根 r1⋯kr_{1\cdots k}，则 ana_n 可写为 an=∑i=1kαirina_n=\sum_{i=1}^k\alpha_ir_i^n，其中 αi\alpha_i 均为常数
定理 4. 对递推式 an=c1an−1+c2an−2+⋯+ckan−ka_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}，若其特征方程有 tt 个不同的根 r1,r2,⋯ ,rtr_1,r_2,\cdots ,r_t，各根重数分别为 m1,m2,⋯mtm_1,m_2,\cdots m_{t}（自然得到 ∑mi=k\sum m_i=k），则 ana_n 可写为
an=∑i=1trin∑j=0mi−1αi,jnja_n=\sum_{i=1}^tr_i^n\sum_{j=0}^{m_i-1}\alpha_{i,j}n^j
其中 αi,j\alpha_{i,j} 均为常数（可以注意到内层 ∑\sum 实际上是一个关于 nn 的 mi−1m_i-1 次多项式）

8.2.3 Linear Nonhomogeneous Recurrence Relations with Constant Coefficients

定义 2. 常系数 kk 阶非齐次线性递推（linear nonhomogeneous recurrence of degree kk with constant coefficients）
an=c1an−1+c2an−2+⋯+ckan−k+F(n)a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}+F(n)
其中 cic_i 为常数，ck≠0c_k\not=0，F(n)F(n) 为只与 nn 有关的非零值函数
定义 3. 对一个非齐次线性递推 an=c1an−1+c2an−2+⋯+ckan−k+F(n)a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}+F(n) 其对应的常系数 kk 阶齐次线性递推为 an=c1an−1+c2an−2+⋯+ckan−ka_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}
定理 5. 对非齐次线性递推 an=c1an−1+c2an−2+⋯+ckan−k+F(n)a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}+F(n)，设其一组特解为 {an(p)}\{a_n^{(p)}\}，其对应的齐次线性递推的一组通解为 {an(h)}\{a_n^{(h)}\}，则原非齐次线性递推的通解为 {an(p)+an(h)}\{a_n^{(p)}+a_n^{(h)}\}
例：an=3an−1+2na_n=3a_{n-1}+2n
其中 an=3an−1a_n=3a_{n-1} 的通解为 an(h)=α⋅3na_n^{(h)}=\alpha \cdot 3^n
而 an=3an−1+2na_n=3a_{n-1}+2n 特解：设 an=pn+qa_n=pn+q，解出 p=−1,q=−32p=-1,q=-\dfrac{3}{2}，则特解 an(p)=−n−32a_n^{(p)}=-n-\dfrac{3}{2}
因此通解为 an=α⋅3n−n−32a_n=\alpha\cdot 3^n-n-\dfrac{3}{2}
定理 6. 若 F(n)=(btnt+bt−1nt−1+⋯+b1n+b0)⋅snF(n)=(b_tn^t+b_{t-1}n^{t-1}+\cdots+b_1n+b_0)\cdot s^n，则：
  1. 若 ss 为特征根，则特解为 an(p)=nm(ptnt+pt−1nt−1+⋯+p1n+p0)⋅sna_n^{(p)}=n^m(p_tn^t+p_{t-1}n^{t-1}+\cdots+p_1n+p_0)\cdot s^n（mm 为 ss 的重数）
  2. 若 ss 不为特征根，则特解为 an(p)=(ptnt+pt−1nt−1+⋯+p1n+p0)⋅sna_n^{(p)}=(p_tn^t+p_{t-1}n^{t-1}+\cdots+p_1n+p_0)\cdot s^n

8.3 分治算法及其递推关系（Divide-and-Conquer Algorithms and Recurrence Relations）

8.3.2 Divide-and-Conquer Recurrence Relations

定理 1. 设函数 ff 单增且满足 f(n)=af(nb)+cf(n)=af\left(\dfrac{n}{b}\right)+c，其中默认 b∣n,a≥1,c>0b|n,a\ge 1,c>0 均为常数，则有：
f(n)={O(nlog⁡ba)if  a>1O(log⁡n)if  a=1f(n)=\begin{cases} O(n^{\log_ba})&\text{if}\ \ a>1\\ O(\log n)&\text{if}\ \ a=1 \end{cases}
**定理 2. 主定理（Master Theorem）**设函数 ff 单增且满足 f(n)=af(nb)+cndf(n)=af\left(\dfrac{n}{b}\right)+cn^d，其中 n=bk(k∈N+),a≥1,c>0,d≥0n=b^k(k\in \mathbb{N}^+),a\ge 1,c>0,d\ge 0 均为常数，则有：
f(n)={O(nd)if  a<bdO(ndlog⁡n)if  a=bdO(nlog⁡ba)if  a>bdf(n)=\begin{cases} O(n^d)&\text{if}\ \ a<b^d\\ O(n^d\log n)&\text{if}\ \ a=b^d\\ O(n^{\log_ba})&\text{if}\ \ a>b^d \end{cases}

8.4 生成函数（Generating Functions）

8.4.1 Introduction

定义 1. 实数序列 a0,a1,⋯ ,an,⋯a_0,a_1,\cdots ,a_n,\cdots 的生成函数为一个无穷级数 G(x)=a0+a1x+a2x2+⋯+anxn+⋯=∑k≥0akxkG(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots=\sum_{k\ge0}a_kx^k
这种生成函数称为普通型生成函数（ordinary generating function, OGF），与之对应的还有指数型生成函数（EGF）和概率生成函数（PGF）

8.4.2 Useful Facts About Power Series

定理 1. 设 f(x)=∑k≥0akxkf(x)=\sum_{k\ge0} a_kx^k，g(x)=∑k≥0bkxkg(x)=\sum_{k\ge0} b_kx^k，则：
f(x)±g(x)=∑k≥0(ak±bk)xkf(x)g(x)=∑k≥0(∑i=1kaibk−i)xk\begin{aligned} &f(x)\pm g(x)=\sum_{k\ge0}(a_k\pm b_k)x^k\\ &f(x)g(x)=\sum_{k\ge 0}\left(\sum_{i=1}^ka_ib_{k-i}\right)x^k \end{aligned}
由此可得一个重要的生成函数：
1(1−x)2=11−x⋅11−x=∑k≥0(∑i=0k1)xk=∑k≥0(k+1)xk\dfrac{1}{(1-x)^2}=\dfrac{1}{1-x}\cdot\dfrac{1}{1-x}=\sum_{k\ge 0}\left(\sum_{i=0}^k 1\right)x^k=\sum_{k\ge 0}(k+1)x^k
定义 2. 扩展二项式系数（extended binomial coefficients）
(uk)=uk‾k!\binom{u}{k}=\dfrac{u^{\underline{k}}}{k!}
其中 k∈N,u∈Rk\in \mathbb{N},u\in \mathbb{R}，uk‾u^{\underline{k}} 为 uu 的 kk 次下降幂 u(u−1)⋯(u−k+1)u(u-1)\cdots (u-k+1)
定理 2. 扩展二项式定理（The Extended Binomial Theorem）
(1+x)u=∑k≥0(uk)xk     (u∈R,∣x∣<1)(1+x)^u=\sum_{k\ge0}\binom{u}{k}x^k\ \ \ \ \ (u\in \mathbb{R},|x|< 1)

8.5 容斥（Inclusion-Exclusion）

8.5.2 The Principle of Inclusion-Exclusion

定理 1. 容斥原理 设 A1,A2,⋯ ,AnA_1,A_2,\cdots, A_n 为 nn 个有限集，则：
∣A1∪A2∪⋯∪An∣=∑S⊆{1,2,⋯ ,n}(−1)∣S∣+1∣⋂i∈SAi∣|A_1\cup A_2\cup\cdots\cup A_n|=\sum_{S\subseteq\{1,2,\cdots,n\}}(-1)^{|S|+1}\left|\bigcap_{i\in S} A_i\right|

8.6 容斥的应用（Applications of Inclusion-Exclusion）

8.6.4 The Number of Onto Functions

定理 1. 设 n,m∈N+,m≥nn,m\in \mathbb{N}^+,m\ge n，则从一个大小为 mm 的集合到一个大小为 nn 的集合的单射个数为：
∑i=0n(−1)i(ni)(n−i)m\sum_{i=0}^n(-1)^i\binom{n}{i}(n-i)^m
（即容斥哪些元素没有被映射到）
定理 2. nn 个元素的错排（dearrangement）的个数为：
Dn=n![1−11!+12!−13!+⋯+(−1)n1n!]D_n=n!\left[1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots+(-1)^n\dfrac{1}{n!}\right]
（容斥哪些位置没有错开即可）

第九章 关系

9.1 关系及其性质（Relations and Their Properties）

9.1.1 Introduction

定义 1. 设 A,BA,B 为集合，则 A,BA,B 之间的一个二元关系（binary relation）为一个 A×BA\times B 的子集

9.1.3 Relations on a Set

定义 2. 设 AA 为集合，则 AA 上的一个关系为一个 A×AA\times A 的子集

9.1.4 Properties of Relations

定义 3. 自反性（reflexive） 称 AA 上的关系 RR 是自反的，当且仅当 ∀x∈A,(x,x)∈R\forall x\in A,(x,x)\in R
定义 4.1. 对称性（symmetric） 称 AA 上的关系 RR 是对称的，当且仅当 ∀a,b∈A,(a,b)∈R⇔(b,a)∈R\forall a,b\in A,(a,b)\in R\Leftrightarrow (b,a)\in R
定义 4.2. 反对称性（antisymmetric） 称 AA 上的关系 RR 是反对称的，当且仅当 ∀a,b∈A,(a,b)∈R\and(b,a)∈R⇒a=b\forall a,b\in A,(a,b)\in R\and (b,a)\in R\Rightarrow a=b
定义 4.3. 非对称性（asymmetric） 称 AA 上的关系 RR 是非对称的，当且仅当 ∀a,b∈A,(a,b)∈R⇒(a,b)∉R\forall a,b\in A,(a,b)\in R\Rightarrow (a,b)\not\in R
定义 5. 传递性（transitive） 称 AA 上的关系 RR 是传递的，当且仅当 ∀a,b,c∈A,(a,b)∈R\and(b,c)∈R⇒(a,c)∈R\forall a,b,c\in A,(a,b)\in R\and (b,c)\in R\Rightarrow (a,c)\in R

9.1.5 Combining Relations

定义 6. 设 RR 为 AA 到 BB 的关系，SS 为 BB 到 CC 的关系，则定义 S∘R={(a,c)∣a∈A,c∈C,∃b∈B,(a,b)∈R,(b,c)∈S}S\circ R=\{(a,c)|a\in A,c\in C, \exist b\in B,(a,b)\in R,(b,c)\in S\}，书写时注意 SS 在前
定义 7. 设 RR 为 AA 上的关系，则 Rn+1=Rn∘RR^{n+1}=R^n\circ R，R1=RR^1=R（n∈Nn\in \mathbb{N}）
定理 1. AA 上的关系 RR 是传递的当且仅当 ∀n∈N+,Rn⊆R\forall n\in \mathbb{N^+},R^n\subseteq R

9.4 关系的闭包（Closures of Relations）

9.4.2 Different Types of Closures

定义 1. 设 RR 是 AA 上的一个关系，PP 是某种性质（如自反性，对称性，传递性）则 RR 关于性质 PP 的闭包（closure）为 RR 的最小的满足性质 PP 的超集
如 RR 的自反闭包为 R∪ΔR\cup \Delta（Δ={(a,a)∣a∈A}\Delta=\{(a,a)|a\in A\}），RR 的对称闭包为 R∪R−1R\cup R^{-1}（R−1R^{-1} 为 RR 的逆关系，R−1={(b,a)∣(a,b)∈R}R^{-1}=\{(b,a)|(a,b)\in R\}）

9.4.3 Paths in Directed Graphs

定义 2. 对有向图 G=(V,E)G=(V,E)，从节点 aa 至节点 bb 的路径为节点序列 x0,x1,⋯ ,xnx_0,x_1,\cdots,x_n，其中 x0=a,xn=b,(xi−1,xi)∈E (1≤i≤n)x_0=a,x_n=b,(x_{i-1},x_i)\in E\ (1\le i\le n)，且称这条路径的长度为 nn（即路径中边的个数）
定理 1. 设 RR 为 AA 上的一个关系，则存在一条从 aa 到 bb，长度为 nn 的路径，当且仅当 (a,b)∈Rn(a,b)\in R^n
定义 3. 设 RR 为 AA 上的一个关系，定义 R∗R^* 为 RR 的连同关系，即 R∗={(a,b)∣b is reachable from a}R^*=\{(a,b)|\text{b is reachable from a}\}，自然得到：
R∗=⋃n=1+∞RnR^*=\bigcup_{n=1}^{+\infty}R^n
定理 2. RR 的传递闭包就是 RR 的连通关系 R∗R^*
引理 1. 设节点个数为 nn，则对节点 aa，若存在 a→aa\rightarrow a 的回路（circuit/cycle），则存在长度 ≤n\le n 的回路，对节点 a,b (a≠b)a,b\ (a\not=b)，若存在 a→ba\rightarrow b 的路径，则存在长度 ≤n−1\le n-1 的路径
定理 3. 由上述引理，得到：
MR∗=MR∪MR2∪⋯∪MRn=MR∪MR2∪⋯∪MRn\begin{aligned} M_{R^*}&=M_R\cup M_{R^2}\cup\cdots\cup M_{R^n}\\ &=M_R\cup M_R^2\cup \cdots\cup M_R^n \end{aligned}
于是可以通过将 MRM_R 的幂次叠加得到传递闭包

9.5 等价关系（Equivalence Relations）

9.5.2 Equivalence Relations

定义 1. 称 AA 上的关系 RR 是等价关系当且仅当 RR 同时具有自反性，对称性，传递性
定义 2. 对 a,b∈Aa,b\in A，若 (a,b)∈R(a,b)\in R，则称 a,ba,b 等价（equivalent），记为 a∼ba\sim b

9.5.3 Equivalence Classes

定义 3. 设 RR 是一个 AA 上的等价关系，a∈Aa\in A，记 [a]R={b∣(a,b)∈R}[a]_R=\{b|(a,b)\in R\} 为所有与 aa 等价的元素形成的集合，则称 [a]R[a]_R 为 aa 的等价类（equivalence class），其中任意的 b∈[a]Rb\in [a]_R 均可被视作这个等价类的代表元素（representative）

9.5.4 Equivalence Classes and Partitions

定理 1. 设 RR 是一个 AA 上的等价关系，a,b∈Aa,b\in A，则以下三个表述是等价的
  • aRb((a,b)∈R)aRb((a,b)\in R)
  • [a]R=[b]R[a]_R=[b]_R
  • [a]R∩[b]R=∅[a]_R\cap [b]_R=\empty
定理 2. 设 RR 是一个 AA 上的等价关系，则由 RR 定义出的等价类形成对 AA 的划分（partition），相反地，给出一个 AA 的划分，也存在一个与之对应的等价关系

9.6 偏序（Partial Orderings）

9.6.1 Introduction

定义 1. 称集合 SS 上的关系 RR 是一个偏序关系当且仅当 RR 同时具有自反性，反对称性，传递性；二元组 (S,R)(S,R) 被称为一个偏序集（partial ordered set/poset）其中 SS 中的元素被称为偏序集的元素
定义 2. 设偏序集 (S,≼)(S,\preccurlyeq) ，a,ba,b 是它的两个元素，则称 a,ba,b 是可比的（comparable）当且仅当 a≼ba\preccurlyeq b 或 b≼ab\preccurlyeq a，若均不满足，则称 a,ba,b 是不可比的（incomparable）
定义 3. 若偏序集中的任意两个元素都是可比的，则称 RR 为一个全序关系（total ordering），相应偏序集也被称为全序集（如 (Z,⩽)(\mathbb{Z},\leqslant)
定义 4. 称偏序集 (S,≼)(S,\preccurlyeq) 是良序的（well-ordered）当且仅当 ≼\preccurlyeq 是全序关系，且 SS 的每个非空子集都有一个最小元素，如以字典序定义的 ≼\preccurlyeq，就有：
  • (Z+×Z+,≼)(\mathbb{Z}^+\times \mathbb{Z}^+,\preccurlyeq) 是良序的
  • (Z×Z,≼)(\mathbb{Z}\times\mathbb{Z},\preccurlyeq) 不是良序的（因为 Z×Z\mathbb{Z}\times \mathbb{Z} 不存在最小元素）
定理 1. 良序归纳原理（The Principle of Well-Ordered Induction） 设 SS 是一个良序集，则 P(x)P(x) 对所有 x∈Sx\in S 为真，当下列条件成立：
每个 y∈Sy\in S，若所有 x≺yx\prec y 的 xx 均有 P(x)P(x) 为真，则 P(y)P(y) 也为真
（这一步称为归纳步，induction step）
注意：这种归纳方法不需要 basis step，因为对 SS 的最小元素 y0y_0，不存在 x∈S,x≺y0x\in S,x\prec y_0，此时 P(y0)P(y_0) 自动为真（感觉有点奇怪）

9.6.3 Hasse Diagrams

当所有偏序关系中的二元数对以有向边连接，入点在上，出点在下，再删除所有可以通过传递性导出的边和自环，就可以得到哈塞图（Hasse Diagram）
具体的图可以看教材
定义 5. 设 (S,≼)(S,\preccurlyeq) 为一个偏序集，x,y∈Sx,y\in S，则称 yy 覆盖（cover）xx 当且仅当 x≺yx\prec y 且不存在另一个 z∈Sz\in S，x≺z≺yx\prec z\prec y，这样所有的 (x,y)(x,y) 形成的关系即为覆盖关系（covering relation）
容易发现哈塞图即由覆盖关系形成

9.6.4 Maximal and Minimal Elements

定义 6. 设偏序集 (S,≼)(S,\preccurlyeq)，a∈Sa\in S，则给出以下几个定义：
  • aa 为极大值（Maximal Element）当且仅当不存在 b∈Sb\in S，a≺ba\prec b
  • aa 为最大值（Greatest Element）当且仅当任意 b∈Sb\in S，b≼ab\preccurlyeq a
  • aa 为极小值（Minimal Element）当且仅当不存在 b∈Sb\in S，b≺ab\prec a
  • aa 为最小值（Least Element）当且仅当任意 b∈Sb\in S，a≼ba\preccurlyeq b
最大值/最小值若存在，则只有唯一一个，极大值/极小值可以有多个
定义 7. 设偏序集 (S,≼)(S,\preccurlyeq)，集合 A⊆S,u∈SA\subseteq S,u\in S，则给出以下几个定义：
  • 若 ∀a∈A\forall a\in A 都有 a≼ua\preccurlyeq u，则称 uu 是集合 AA 的一个上界（upper bound）
  • 若 ∀a∈A\forall a\in A 都有 u≼au\preccurlyeq a，则称 uu 是集合 AA 的一个下界（lower bound）
  • uu 是集合 AA 的最小上界（least upper bound）当且仅当 uu 是 AA 的所有上界中最小的一个
  • uu 是集合 AA 的最大下界（greatest lower bound）当且仅当 uu 是 AA 的所有下界中最大的一个
对集合 AA，这四个都可能不存在

9.6.5 Lattices

定义 8. 若偏序集 (S,≼)(S,\preccurlyeq) 满足其任意非空子集都存在最小上界和最大下界，则称该偏序集为一个栅格（lattice）

9.6.6 Topological Sorting

引理 1. 设 (S,≼)(S,\preccurlyeq) 是一个有限偏序集，则 SS 存在极小值
拓扑排序通过不断删除极小值来得到一个新的全序关系 a1≺ta2≺t⋯≺tana_1\prec_t a_2\prec_t\cdots\prec_t a_n，其中任意 x,y∈Sx,y\in S，若 x≺yx\prec y，则有 x≺tyx\prec_t y

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...