第一章：数理逻辑

1.1 命题逻辑

1.1.1 核心概念深度解析

• 命题：必须是陈述句且具有唯一真值。
  • 易错点：悖论（如"我正在说谎"）不是命题；含有未定变量的句子（如"$x+1=2$"）是谓词而非命题。
• 原子命题与复合命题：
  • 原子命题：不能再分解的命题。
  • 复合命题：通过联结词组合而成。

1.1.2 联结词与真值表 (详细版)

联结词	符号	英文	优先级	逻辑详解	常见语言表达
否定	$\mathrm{\neg }$	NOT	1	真变假，假变真	"并不是..."
合取	$\wedge$	AND	2	仅当两者全真时为真	"且", "虽然...但是...", "既...又..."
析取	$\vee$	OR	3	仅当两者全假时为假	"或" (包含性或)
蕴涵	$\to$	IMPLIES	4	前真后假时为假，其余全真	"若...则...", "只要...就...", "只有...才..."
双蕴涵	$\leftrightarrow$	IFF	5	同真同假时为真	"当且仅当", "充分必要条件"

重点难点：蕴涵关系 ($P\to Q$) 的翻译

• 充分条件："只要 $P$ 就 $Q$" $\Rightarrow P\to Q$
• 必要条件："只有 $Q$ 才 $P$" $\Rightarrow P\to Q$ (注意：$P$ 是 $Q$ 的充分条件，或者理解为 $\mathrm{\neg }Q\to \mathrm{\neg }P$)
• 除非："除非 $P$ 否则 $Q$" $\Rightarrow \mathrm{\neg }P\to Q$ (即 $P\vee Q$)

1.1.3 命题公式的分类 (Classifications)

常考题型：判断给定公式属于哪一类。

1. 永真式 (重言式, Tautology)：
   • 在所有真值赋值下，结果均为真 ($1$)。
   • 例：$P\vee \mathrm{\neg }P$
2. 矛盾式 (永假式, Contradiction)：
   • 在所有真值赋值下，结果均为假 ($0$)。
   • 例：$P\wedge \mathrm{\neg }P$
3. 可满足式 (Contingency)：
   • 不是矛盾式的公式（即至少有一种赋值为真）。
   • 注意：永真式也是可满足式的一种，但通常指"既非永真也非永假"的公式。

1.1.4 逻辑等值式 (Laws of Logic)

核心：用于化简命题公式。

1. 双重否定律：$\mathrm{\neg }\mathrm{\neg }P\iff P$
2. 幂等律：$P\vee P\iff P$, $P\wedge P\iff P$
3. 交换律：$P\vee Q\iff Q\vee P$, $P\wedge Q\iff Q\wedge P$
4. 结合律：$(P\vee Q)\vee R\iff P\vee (Q\vee R)$
5. 分配律 (非常重要)：
   • $P\vee (Q\wedge R)\iff (P\vee Q)\wedge (P\vee R)$ (析取对合取的分配)
   • $P\wedge (Q\vee R)\iff (P\wedge Q)\vee (P\wedge R)$ (合取对析取的分配)
6. 德·摩根律 (De Morgan's Laws) (变号变词)：
   • $\mathrm{\neg }(P\vee Q)\iff \mathrm{\neg }P\wedge \mathrm{\neg }Q$
   • $\mathrm{\neg }(P\wedge Q)\iff \mathrm{\neg }P\vee \mathrm{\neg }Q$
7. 吸收律 (合并同类项)：
   • $P\vee (P\wedge Q)\iff P$
   • $P\wedge (P\vee Q)\iff P$
8. 蕴含等值式：$P\to Q\iff \mathrm{\neg }P\vee Q$ (去箭头核心公式)
9. 等价等值式：$P\leftrightarrow Q\iff (P\to Q)\wedge (Q\to P)$
10. 假言易位 (逆否命题)：$P\to Q\iff \mathrm{\neg }Q\to \mathrm{\neg }P$
11. 归谬律：$(P\to Q)\wedge (P\to \mathrm{\neg }Q)\iff \mathrm{\neg }P$

1.1.4 范式 (Normal Forms)

析取范式 (DNF) 与 合取范式 (CNF)

• 定义：
  • DNF：简单合取式的析取 ($\sum$)。例如：$(P\wedge Q)\vee (\mathrm{\neg }P\wedge R)$
  • CNF：简单析取式的合取 ($\prod$)。例如：$(P\vee Q)\wedge (\mathrm{\neg }P\vee R)$
• 主范式 (Principal NF)：
  • 极小项 ($m_i$)：包含所有变量的合取项，编码对应真值表中的行号。
  • 极大项 ($M_i$)：包含所有变量的析取项。
  • 转换方法：
    1. 真值表法：
       • 主析取范式：取真值表中结果为 $T$ 的行对应的极小项之和。
       • 主合取范式：取真值表中结果为 $F$ 的行对应的极大项之积。
    2. 等值演算法：利用双重否定、德摩根、分配律展开。

---

1.2 谓词逻辑 (Predicate Logic)

1.2.1 基本要素

• 个体词：常量 ($a,b$) 和 变量 ($x,y$)。
• 谓词：$P(x_1,\dots ,x_n)$，表示个体之间的性质或关系。
• 量词：
  • 全称量词 $\mathrm{\forall }$ (For all)
  • 存在量词 $\mathrm{\exists }$ (Exists)
• 论域 (Universe)：个体变元的取值范围。若未指定，通常指全总个体域。

1.2.2 翻译技巧 (易错)

1. "所有的 S 都是 P"：
   • 正确：$\mathrm{\forall }x(S(x)\to P(x))$
   • 错误：$\mathrm{\forall }x(S(x)\wedge P(x))$ (这意味着宇宙中万物既是S也是P)
2. "有的 S 是 P"：
   • 正确：$\mathrm{\exists }x(S(x)\wedge P(x))$
   • 错误：$\mathrm{\exists }x(S(x)\to P(x))$ (这通常是恒真的，没有意义)

1.2.3 谓词逻辑等值式

1. 量词否定律：
   • $\mathrm{\neg }\mathrm{\forall }xP(x)\iff \mathrm{\exists }x\mathrm{\neg }P(x)$ (改变量词，否定谓词)
   • $\mathrm{\neg }\mathrm{\exists }xP(x)\iff \mathrm{\forall }x\mathrm{\neg }P(x)$
2. 量词辖域扩展 (设 $Q$ 不含 $x$)：
   • $\mathrm{\forall }x(P(x)\vee Q)\iff (\mathrm{\forall }xP(x))\vee Q$
   • $\mathrm{\exists }x(P(x)\wedge Q)\iff (\mathrm{\exists }xP(x))\wedge Q$
3. 量词分配律：
   • $\mathrm{\forall }x(P(x)\wedge Q(x))\iff \mathrm{\forall }xP(x)\wedge \mathrm{\forall }xQ(x)$ (全称对合取可分配)
   • $\mathrm{\exists }x(P(x)\vee Q(x))\iff \mathrm{\exists }xP(x)\vee \mathrm{\exists }xQ(x)$ (存在对析取可分配)
   • 注意：$\mathrm{\forall }$ 对 $\vee$ 不可分配，$\mathrm{\exists }$ 对 $\wedge$ 不可分配！

1.2.4 前束范式 (Prenex Normal Form)

形式：$Q_1{x}_1{Q}_2{x}_2\dots Q_k{x}_{k}M$

• 所有量词都在最左边。
• $M$ 是不含量词的基式。

化简步骤：

1. 消去蕴涵：利用 $A\to B\iff \mathrm{\neg }A\vee B$。
2. 否定内移：利用德摩根律和量词否定律，将 $\mathrm{\neg }$ 移到原子公式前。
3. 变元改名：确保不同量词使用不同的变量名 (如 $\mathrm{\forall }xP(x)\vee \mathrm{\exists }xQ(x)$ 改为 $\mathrm{\forall }xP(x)\vee \mathrm{\exists }yQ(y)$)。
4. 量词左提：利用量词辖域扩展规则将量词提到最前面。

---

1.3 推理理论 (Inference Theory)

1.3.1 常用推理规则

1. 假言推理 (Modus Ponens): $P,P\to Q\Rightarrow Q$
2. 拒取式 (Modus Tollens): $\mathrm{\neg }Q,P\to Q\Rightarrow \mathrm{\neg }P$
3. 析取三段论: $P\vee Q,\mathrm{\neg }P\Rightarrow Q$
4. 假言三段论: $P\to Q,Q\to R\Rightarrow P\to R$
5. 化简律: $P\wedge Q\Rightarrow P$
6. 附加律: $P\Rightarrow P\vee Q$

1.3.2 谓词推理规则

1. 全称特指 (US): $\mathrm{\forall }xP(x)\Rightarrow P(c)$ (任意 $\to$ 个体)
2. 全称推广 (UG): $P(x)\Rightarrow \mathrm{\forall }xP(x)$ (任意个体 $\to$ 任意) 注意限制条件
3. 存在特指 (ES): $\mathrm{\exists }xP(x)\Rightarrow P(c)$ (存在 $\to$ 特指常量 $c$) 注意 $c$ 必须是新引入的
4. 存在推广 (EG): $P(c)\Rightarrow \mathrm{\exists }xP(x)$ (个体 $\to$ 存在)

1.3.3 证明方法

1. 直接证明法：从前提及其逻辑推论出发，推导出结论。
2. 附加前提证明法 (CP规则)：
   • 若要证 $A\to B$，可将 $A$ 作为附加前提加入前提集，只需证出 $B$ 即可。
3. 反证法 (归谬法)：
   • 将结论的否定 $\mathrm{\neg }C$ 加入前提集，推导出矛盾 ($F$)。

第二章：集合论与二元关系

2.1 集合论

2.1.1 基础运算

• 并 (${\displaystyle A\cup B}$)、交 (${\displaystyle A\cap B}$)、补 (${\displaystyle \overline{A}}$)、差 (${\displaystyle A-B}$)。
• 对称差 (${\displaystyle A\oplus B}$)：${\displaystyle A\oplus B=(A-B)\cup (B-A)}$。
  • 属于 A 或属于 B，但不同时属于两者。
  • 特性：${\displaystyle A\oplus A=\mathrm{\varnothing }}$, ${\displaystyle A\oplus \mathrm{\varnothing }=A}$, ${\displaystyle A\oplus B=B\oplus A}$。

2.1.2 集合恒等式证明技巧

1. 子集互证法：证明 ${\displaystyle A=B}$ 即证 ${\displaystyle A\subseteq B}$ 且 ${\displaystyle B\subseteq A}$。
   • 任取 ${\displaystyle x\in A}$，逻辑推导 ${\displaystyle x\in B}$。
2. 集合演算法：利用集合恒等式（类似逻辑等值式）进行变形。
   • ${\displaystyle A-B=A\cap \overline{B}}$ (最常用的变形)
   • 德摩根律：${\displaystyle \overline{A\cup B}=\overline{A}\cap \overline{B}}$
3. 成员表法/特征函数法：
   • 列出元素属于各集合的所有 ${\displaystyle 0/1}$ 组合，验证结果是否一致。

2.1.3 幂集与笛卡尔积

• 幂集 ${\displaystyle P(A)}$：${\displaystyle A}$ 的所有子集构成的集合。
  • 若 ${\displaystyle |A|=n}$，则 ${\displaystyle |P(A)|=2^n}$。
  • 易错：${\displaystyle \mathrm{\varnothing }\in P(A)}$, ${\displaystyle A\in P(A)}$。
• 笛卡尔积 ${\displaystyle A\times B}$：有序对的集合。
  • ${\displaystyle |A\times B|=|A|\cdot |B|}$。
  • 不满足交换律：${\displaystyle A\times B\ne B\times A}$ (除非 ${\displaystyle A=B}$ 或为空)。

2.2 二元关系

2.2.1 关系的表示与基本性质

关系 ${\displaystyle R}$ 是 ${\displaystyle A\times A}$ 的子集。

• 表示法：集合表达式、关系矩阵 ${\displaystyle M_R}$、关系图 ${\displaystyle G_R}$。

五大基本性质 (必须熟练判断)

性质	定义	矩阵特征	图特征
自反性	${\displaystyle \mathrm{\forall }x,(x,x)\in R}$	主对角线全 1	每个节点都有自环
反自反性	${\displaystyle \mathrm{\forall }x,(x,x)\notin R}$	主对角线全 0	无自环
对称性	${\displaystyle (x,y)\in R\to (y,x)\in R}$	对称矩阵 (${\displaystyle M=M^T}$)	所有边双向
反对称性	${\displaystyle (x,y)\in R\wedge (y,x)\in R\to x=y}$	${\displaystyle m_{ij}=1\wedge i\ne j\Rightarrow m_{ji}=0}$	无双向边
传递性	${\displaystyle (x,y)\in R\wedge (y,z)\in R\to (x,z)\in R}$	${\displaystyle M^2\le M}$ (布尔乘)	有路必达（形成捷径）

2.2.2 关系矩阵详解

定义：设 ${\displaystyle A=\{a_1,a_2,\dots ,a_n\}}$，关系矩阵 ${\displaystyle M_R}$ 是一个 ${\displaystyle n\times n}$ 的 0-1 矩阵。

• 若 ${\displaystyle (a_i,a_j)\in R}$，则 ${\displaystyle m_{ij}=1}$；否则 ${\displaystyle m_{ij}=0}$。

关系运算的矩阵表示

1. 逆关系：${\displaystyle M_{R^{-1}}=(M_R{)}^T}$ (转置矩阵)。
2. 并集/交集：${\displaystyle M_{R\cup S}=M_R\vee M_S}$, ${\displaystyle M_{R\cap S}=M_R\wedge M_S}$ (对应位置逻辑运算)。
3. 复合关系：${\displaystyle M_{S\circ R}=M_R\cdot M_S}$ (布尔矩阵乘法)。
   • 注意顺序：${\displaystyle S\circ R}$ 表示先 ${\displaystyle R}$ 后 ${\displaystyle S}$，矩阵乘法也是 ${\displaystyle M_R}$ 在前。
   • 布尔乘法规则：${\displaystyle c_{ij}=\underset{k=1}{\overset{n}{\bigvee }}(a_{ik}\wedge b_{kj})}$。
4. 幂运算：${\displaystyle M_{R^n}=(M_R{)}^n}$ (布尔乘幂)。

2.2.3 关系性质的运算封闭性 (表 6.2)

运算	自反性	反自反性	对称性	反对称性	传递性
逆关系 ${\displaystyle R^{-1}}$	是	是	是	是	是
交 ${\displaystyle R\cap S}$	是	是	是	是	是
并 ${\displaystyle R\cup S}$	是	是	是	否	否
差 ${\displaystyle R-S}$	否	是	是	是	否
复合 ${\displaystyle R\circ S}$	是	否	否	否	否

注：表中“是”表示该性质在运算下一定保持，“否”表示不一定保持。

2.2.4 关系的闭包

• 自反闭包 ${\displaystyle r(R)=R\cup I_A}$ (矩阵：主对角线置1)
• 对称闭包 ${\displaystyle s(R)=R\cup R^{-1}}$ (矩阵：${\displaystyle M\vee M^T}$)
• 传递闭包 ${\displaystyle t(R)=R\cup R^2\cup \cdots \cup R^n}$ (连通性)

Warshall 算法 (计算传递闭包的核心)

用于在计算机中高效计算 ${\displaystyle t(R)}$。

• 输入：${\displaystyle n\times n}$ 关系矩阵 ${\displaystyle M}$。
• 逻辑：

  for k from 1 to n:
      for i from 1 to n:
          for j from 1 to n:
              M[i,j] = M[i,j] or (M[i,k] and M[k,j])

  直观理解：第 ${\displaystyle k}$ 轮循环尝试以节点 ${\displaystyle k}$ 为中转站，如果 ${\displaystyle i\to k}$ 且 ${\displaystyle k\to j}$，则建立 ${\displaystyle i\to j}$ 的直达路径。

2.2.5 等价关系与划分

• 定义：满足 自反、对称、传递 的关系。
• 等价类 ${\displaystyle [x{]}_R}$：所有与 ${\displaystyle x}$ 有关系 ${\displaystyle R}$ 的元素集合。
• 划分：
  • 集合 ${\displaystyle A}$ 被划分为若干个不相交的子集，其并集为 ${\displaystyle A}$。
  • 定理：等价关系与划分一一对应。等价类就是划分出的子集。
  • 例：整数集上的模 3 同余关系，划分为 ${\displaystyle \{3k\},\{3k+1\},\{3k+2\}}$ 三类。

2.2.6 偏序关系详解

• 定义：满足 自反、反对称、传递 的关系。符号 ${\displaystyle ⪯}$。
• 相关符号：
  • ${\displaystyle x⪯y}$：${\displaystyle x}$ 小于等于 ${\displaystyle y}$ (或 ${\displaystyle x}$ 排在 ${\displaystyle y}$ 前)。
  • ${\displaystyle x\prec y}$：${\displaystyle x⪯y\wedge x\ne y}$。
  • 可比：若 ${\displaystyle x⪯y}$ 或 ${\displaystyle y⪯x}$，则称 ${\displaystyle x,y}$ 可比。
  • 不可比：若既不 ${\displaystyle x⪯y}$ 也不 ${\displaystyle y⪯x}$，则称 ${\displaystyle x,y}$ 不可比。
• 覆盖关系：
  • 若 ${\displaystyle x\prec y}$ 且不存在 ${\displaystyle z}$ 使得 ${\displaystyle x\prec z\prec y}$，则称 ${\displaystyle y}$ 覆盖 ${\displaystyle x}$。
  • 哈斯图即是基于覆盖关系绘制的简化图。

哈斯图画法步骤

1. 画出覆盖关系（即去掉所有自环和传递边）。
2. 若 ${\displaystyle y}$ 覆盖 ${\displaystyle x}$，则将 ${\displaystyle y}$ 画在 ${\displaystyle x}$ 上方并连线。
3. 方向默认向上，省略箭头。

特殊元素 (重要考点)

设 ${\displaystyle (A,⪯)}$ 为偏序集，${\displaystyle B\subseteq A}$。

1. 极小元：${\displaystyle B}$ 中没有比它更小的元素。${\displaystyle \mathrm{\neg }\mathrm{\exists }x\in B,x\prec a}$。
2. 极大元：${\displaystyle B}$ 中没有比它更大的元素。${\displaystyle \mathrm{\neg }\mathrm{\exists }x\in B,a\prec x}$。
3. 最小元：${\displaystyle B}$ 中所有元素都比它大。${\displaystyle \mathrm{\forall }x\in B,a⪯x}$ (若存在则唯一)。
4. 最大元：${\displaystyle B}$ 中所有元素都比它小。${\displaystyle \mathrm{\forall }x\in B,x⪯a}$ (若存在则唯一)。
5. 下界：${\displaystyle A}$ 中小于等于 ${\displaystyle B}$ 中所有元素的元素。${\displaystyle \mathrm{\forall }x\in B,l⪯x}$。
6. 上界：${\displaystyle A}$ 中大于等于 ${\displaystyle B}$ 中所有元素的元素。${\displaystyle \mathrm{\forall }x\in B,x⪯u}$。
7. 下确界 (GLB/Infimum)：最大下界。符号 ${\displaystyle infB}$ 或 ${\displaystyle \wedge B}$。
8. 上确界 (LUB/Supremum)：最小上界。符号 ${\displaystyle supB}$ 或 ${\displaystyle \vee B}$。

示例：整除关系

设 ${\displaystyle A=\{1,2,3,4,6,12\}}$，关系为整除 (${\displaystyle |}$)。

• 哈斯图层级：${\displaystyle 12}$ 在顶；${\displaystyle 4,6}$ 在中；${\displaystyle 2,3}$ 在下；${\displaystyle 1}$ 在底。
• ${\displaystyle 2}$ 和 ${\displaystyle 3}$ 不可比。
• 子集 ${\displaystyle \{2,3\}}$ 的上界是 ${\displaystyle 6,12}$，上确界是 ${\displaystyle 6}$。
• 子集 ${\displaystyle \{2,3\}}$ 的下界是 ${\displaystyle 1}$，下确界是 ${\displaystyle 1}$。

格

• 定义：偏序集 ${\displaystyle (L,⪯)}$ 中任意两个元素 ${\displaystyle x,y}$ 都有确定的上确界 (${\displaystyle x\vee y}$) 和下确界 (${\displaystyle x\wedge y}$)。
• 性质：格可以看作代数系统，满足交换律、结合律、吸收律。

2.3 函数

2.3.1 函数的性质

• 单射：
  • 定义：${\displaystyle f(a)=f(b)\Rightarrow a=b}$。
  • 判别：陪域中每个元素最多被 1 个箭头指到。
• 满射：
  • 定义：${\displaystyle \mathrm{\forall }y\in B,\mathrm{\exists }x\in A,f(x)=y}$。
  • 判别：陪域中每个元素至少被 1 个箭头指到 (值域=陪域)。
• 双射：既单且满。
  • 只有双射存在逆函数 ${\displaystyle f^{-1}}$。

2.3.2 复合函数

• ${\displaystyle (g\circ f)(x)=g(f(x))}$。
• 性质：
  • 若 ${\displaystyle f,g}$ 都是单射，则 ${\displaystyle g\circ f}$ 是单射。
  • 若 ${\displaystyle f,g}$ 都是满射，则 ${\displaystyle g\circ f}$ 是满射。
  • 若 ${\displaystyle g\circ f}$ 是单射 $\Rightarrow f$ 必为单射。
  • 若 ${\displaystyle g\circ f}$ 是满射 $\Rightarrow g$ 必为满射。

2.3.3 特殊函数与算法复杂度

1. 取整函数：
   • 向下取整 (Floor) $\lfloor x\rfloor$：小于等于 $x$ 的最大整数。
   • 向上取整 (Ceiling) $\lceil x\rceil$：大于等于 $x$ 的最小整数。
2. 算法复杂度 (Big-O Notation)：
   • 定义：设 $f,g$ 是从整数集或实数集到实数集的函数。若存在常数 $C$ 和 $k$，使得当 $x>k$ 时，$|f(x)|\le C|g(x)|$，则称 $f(x)$ 是 $O(g(x))$。
   • 常见阶：$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)<O(n!)$。
   • 判定技巧：
     • 忽略系数：$7n^3$ 是 $O(n^3)$。
     • 只看最高次项：$n^2+n+1$ 是 $O(n^2)$。

2.3.4 典型考题：等价关系的证明

题目：设 $R$ 是集合 $A$ 上的等价关系，证明 $R\circ R$ 也是 $A$ 上的等价关系。 证明思路：

1. 自反性：
   • $\because R$ 自反 $\therefore \mathrm{\forall }a\in A,(a,a)\in R$。
   • 故 $(a,a)\in R\circ R$（通过中间点 $a$），即 $R\circ R$ 自反。
2. 对称性：
   • 任取 $(x,y)\in R\circ R$，则 $\mathrm{\exists }t\in A$ 使得 $(x,t)\in R\wedge (t,y)\in R$。
   • $\because R$ 对称 $\therefore (t,x)\in R\wedge (y,t)\in R$。
   • 交换顺序得 $(y,t)\in R\wedge (t,x)\in R\Rightarrow (y,x)\in R\circ R$。
3. 传递性：
   • $\because R$ 传递，且 $R$ 是等价关系 $\therefore R\circ R=R$（等价关系的幂运算封闭性）。
   • $R$ 自身具备传递性，故 $R\circ R$ 传递。
   • (注：若题目要求严格分布证明，需设 $(x,y)\in R^2,(y,z)\in R^2$ 推导 $(x,z)\in R^2$)。

第三章：组合数学

3.0 基础数论概念 (补充)

• 完全数 (Perfect Number)：
  • 一个正整数等于其所有真因子（即除了自身以外的约数）之和。
  • 例：$6=1+2+3$；$28=1+2+4+7+14$。
  • 考点：判断给定数字是否为完全数，或计算其真因子之和。

3.1 基础计数原理

3.1.1 加法与乘法原理

• 加法原理 (分类)：$S=S_1\cup S_2\dots$ (互不相交)，则 $|S|=|S_1|+|S_2|\dots$
• 乘法原理 (分步)：步骤 1 有 $n_1$ 种，步骤 2 有 $n_2$ 种... 则总数为 $n_1\times n_2\dots$

3.1.2 排列与组合 (Notation: $C_n^r,P_n^r$)

模型	公式	典型场景
排列 (有序)	$P_n^r=\frac{n!}{(n-r)!}$	$n$ 人选 $r$ 人排队拍照
组合 (无序)	$C_n^r=\frac{n!}{r!(n-r)!}$	$n$ 人选 $r$ 人组队
可重排列	$n^r$	$r$ 位密码，每位 $n$ 种选择
可重组合	$C_{n+r-1}^r$	$n$ 种口味冰淇淋选 $r$ 球 (隔板法)

3.1.3 组合恒等式

1. 对称性：$C_n^r=C_n^{n-r}$
2. 帕斯卡公式：$C_n^k=C_{n-1}^k+C_{n-1}^{k-1}$
   • 组合意义：选 $k$ 人，要么包含特定人 A ($C_{n-1}^{k-1}$)，要么不包含 A ($C_{n-1}^k$)。
3. 二项式定理：$(x+y{)}^n=\sum _{k=0}^n{C}_n^k{x}^{n-k}{y}^k$
   • 推论：$\sum _{k=0}^n{C}_n^k=2^n$ (所有子集个数)
   • 推论：$\sum _{k=0}^n(-1{)}^k{C}_n^k=0$ (奇数个元素的子集数 = 偶数个元素的子集数)
4. 范德蒙恒等式：$C_{m+n}^r=\sum _{k=0}^r{C}_m^k{C}_n^{r-k}$

---

3.2 高级计数方法

3.2.1 鸽巢原理 (Pigeonhole Principle)

• 原理：$N$ 个物体放入 $k$ 个盒子，必有一个盒子至少有 $\lceil N/k\rceil$ 个物体。
• 应用技巧：准确定义“鸽子”（物体）和“巢”（分类标准）。
  • 例：任意 13 人中必有 2 人生肖相同 ($13/12\to 2$)。

3.2.2 容斥原理 (Inclusion-Exclusion)

求 $|A_1\cup A_2\cup \dots \cup A_n|$：

• 公式：$\sum |A_i|-\sum |A_i\cap A_j|+\sum |A_i\cap A_j\cap A_k|-\dots$
• 错排问题 ($D_n$)：$n$ 封信全部装错信封的方法数。
  • $D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}-\dots +(-1{)}^n\frac{1}{n!})$
  • 递推式：$D_n=(n-1)(D_{n-1}+D_{n-2})$

3.2.3 球盒模型 (Twelvefold Way 概览)

将 $n$ 个球放入 $k$ 个盒子：

球 (Label)	盒子 (Label)	限制	方案数
不同	不同	无	$k^n$
不同	不同	$\le 1$	$P_k^n$
相同	不同	无	$C_{n+k-1}^n$ (隔板法)
相同	不同	$\ge 1$	$C_{n-1}^{k-1}$ (先各放1个)
不同	相同	无	$S_2(n,k)$ (第二类斯特林数)

---

3.3 递推关系 (Recurrence Relations)

3.3.1 线性常系数齐次递推关系

形式：$a_n+c_1{a}_{n-1}+\dots +c_k{a}_{n-k}=0$求解步骤：

1. 写出特征方程：$r^k+c_1{r}^{k-1}+\dots +c_k=0$。
2. 求特征根 $r_1,r_2,\dots$。
3. 写出通解结构：
   • 无重根：$a_n=A_1{r}_1^n+A_2{r}_2^n+\dots$
   • 有重根 (如 $r_1$ 为 $m$ 重根)：$a_n=(A_1+A_{2}n+\dots +A_m{n}^{m-1})r_1^n+\dots$
4. 代入初值求解常数 $A_i$。

3.3.2 生成函数 (Generating Functions)

• 定义：$G(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$。
• 应用场景：
  • 求解组合数：如 $(1+x{)}^n$ 的系数。
  • 求解不定方程 $x_1+x_2+x_3=k$ 的非负整数解个数。
    • 构造多项式 $(1+x+x^2+\dots {)}^3$，求 $x^k$ 系数。

---

3.4 典型考题：不定方程解计数

题目：求 $x_1+x_2+x_3=15$ 的整数解个数，满足 $x_1\ge 1,0\le x_2\le 5,x_3\ge 0$。 解题思路：

1. 换元消下界：令 $y_1=x_1-1\ge 0$。
   • 原方程变为 $(y_1+1)+x_2+x_3=15\Rightarrow y_1+x_2+x_3=14$。
2. 全集计算：无上限限制时的非负整数解。
   • ${\displaystyle N=C_{14+3-1}^{3-1}=C_{16}^2=120}$。
3. 容斥处理上界：
   • 坏条件 $P_1$：$x_2\ge 6$ (即原题 $x_2>5$)。
   • 在坏条件 $P_1$ 下，令 $z_2=x_2-6\ge 0$。
   • 方程变为 $y_1+(z_2+6)+x_3=14\Rightarrow y_1+z_2+x_3=8$。
   • $|P_1|=C_{8+3-1}^2=C_{10}^2=45$。
4. 最终结果：$Ans=N-|P_1|=120-45=75$。

---

3.5 典型考题：常系数齐次线性递推关系求解

题目：求解递推关系 $a_n=7a_{n-1}-16a_{n-2}+12a_{n-3}$，初始条件为 $a_0=0,a_1=4,a_2=18$。 解题步骤：

1. 构造特征方程 将递推式移项得 $a_n-7a_{n-1}+16a_{n-2}-12a_{n-3}=0$。 对应的特征方程为： $r^3-7r^2+16r-12=0$

2. 求解特征根 观察系数，尝试代入 $r=2$：$8-28+32-12=0$，故 $(r-2)$ 是因子。 多项式除法分解得： $(r-2)(r^2-5r+6)=0$$(r-2)(r-2)(r-3)=0$ 解得特征根：$r_1=2$ (二重根)，$r_2=3$ (单根)。

3. 写出通解结构 对于二重根 $2$ 和单根 $3$，通解形式为： $a_n=(C_1+C_{2}n)\cdot 2^n+C_3\cdot 3^n$

4. 代入初始条件求解常数

   • 当 $n=0$ 时：$C_1+C_3=0⟹C_3=-C_1$
   • 当 $n=1$ 时：$(C_1+C_2)\cdot 2+3C_3=4$
   • 当 $n=2$ 时：$(C_1+2C_2)\cdot 4+9C_3=18$

   将 $C_3=-C_1$ 代入后两式：

   • $2C_1+2C_2-3C_1=4⟹-C_1+2C_2=4$
   • $4C_1+8C_2-9C_1=18⟹-5C_1+8C_2=18$

   联立求解： 由第一式得 $C_1=2C_2-4$，代入第二式： $-5(2C_2-4)+8C_2=18$$-10C_2+20+8C_2=18$$-2C_2=-2⟹C_2=1$ 回代得 $C_1=2(1)-4=-2$$C_3=-(-2)=2$

5. 最终解$a_n=(-2+n)\cdot 2^n+2\cdot 3^n$ 或整理为： $a_n=(n-2)2^n+2\cdot 3^n$

第四章：图论

4.1 图的基本概念

4.1.1 定义与术语

• 图 $G=(V,E)$：$V$ 为顶点集，$E$ 为边集。
• 度 (Degree)：$\mathrm{deg}(v)$ 为关联的边数 (自环算 2 度)。
  • 握手定理：$\sum _{v\in V}\mathrm{deg}(v)=2|E|$。
  • 推论：奇度顶点的个数必为偶数。
• 子图：$V^{\prime }\subseteq V,E^{\prime }\subseteq E$。
• 补图：$\overline{G}$，顶点相同，边互补 (完全图 $K_n$ 减去原图的边)。

4.1.2 图的连通性

• 路径 (Path)：$v_0,e_1,v_1,\dots ,v_k$。
• 简单路径：不经过重复边。
• 基本路径 (Elementary Path)：不经过重复顶点。
• 连通图：任意两点间均有路径。
• 割点 (Cut Vertex)：删去该点及关联边，图分量增加。
• 割边 (Bridge)：删去该边，图分量增加。
• 连通度：
  • 点连通度 $\kappa (G)$：使图不连通所需删除的最少顶点数。
  • 边连通度 $\lambda (G)$：使图不连通所需删除的最少边数。
  • 不等式关系：$\kappa (G)\le \lambda (G)\le \delta (G)$ (最小度)。

4.1.3 图的矩阵表示

• 邻接矩阵 $A(G)$：$n\times n$ 矩阵，$a_{ij}$ 表示 $v_i,v_j$ 间的边数。
  • 性质：$A^k$ 的元素 $a_{ij}^{(k)}$ 表示从 $v_i$ 到 $v_j$ 长度为 $k$ 的路径条数。
• 关联矩阵 $M(G)$：顶点与边的关系。

4.1.4 图的同构 (Isomorphism)

判断 $G_1\cong G_2$ 的必要条件 (若不满足则必不同构)：

1. 顶点数、边数相同。
2. 度数列相同 (将所有点度数排序后一致)。
3. 连通分量数相同。
4. 对应长度的回路数相同 (如都有或都没有三角形)。 充分性证明通常需要构造双射函数。

4.2 特殊图类

4.2.1 欧拉图 (Euler) 与 哈密顿图 (Hamilton)

特性	欧拉图 (Euler)	哈密顿图 (Hamilton)
定义	经过每条边恰好一次的回路	经过每个顶点恰好一次的回路
判定(充要)	连通 + 所有点度为偶数	无简单充要条件
判定(充分)	-	(Dirac) $n\ge 3,\mathrm{\forall }v,\mathrm{deg}(v)\ge n/2$
半图(路径)	连通 + 恰有 0 或 2 个奇度点	-
哈密顿图常用判定方式 (充分/必要)：

• 必要条件：$\delta (G)\ge 2$；且无割点 (2-连通)。
• Dirac 定理 (充分)：$n\ge 3,\delta (G)\ge n/2$。
• Ore 定理 (充分)：$n\ge 3$ 且任意非邻接顶点 $u,v$ 满足 $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$。

4.2.2 树 (Trees)

• 定义：连通且无回路的无向图。
• 等价性质：
  1. 无回路且 $E=V-1$。
  2. 连通且 $E=V-1$。
  3. 任意两点间存在唯一路径。
• 度数和：$\sum _{v\in V}\mathrm{deg}(v)=2E=2(V-1)$。
• 叶子与内部点关系：设 $L$ 为叶子数，则 $L=2+\sum _{\mathrm{deg}(v)\ge 2}(\mathrm{deg}(v)-2)$。
• 树中心 (Center)：
  • 反复删除所有叶子，最终剩下 1 个或 2 个顶点，这些顶点即中心。
  • 等价表述：中心是到其他顶点最大距离最小的顶点(们)。
• 二叉树常用关系：
  • 满二叉树：若内部结点数为 $I$，叶子数为 $L$，则 $L=I+1$。
  • 完全二叉树：$n$ 个结点时高度 $h=\lfloor {\log }_{2}n\rfloor +1$。
• 最小生成树 (MST) 算法：
  • Kruskal (加边法)：按权值排序，从小到大选边，不构成回路就加入。
  • Prim (加点法)：从任意点开始，每次选离当前生成树集合最近的点加入。

4.2.3 平面图 (Planar Graphs)

• 欧拉公式：$V-E+R=2$ ($R$ 为面数，包含无限面)。
• 定理：连通简单平面图 ($V\ge 3$) 满足 $E\le 3V-6$。
  • 证明要点：每个面至少 3 条边，故 $3R\le 2E$，与欧拉公式联立得 $E\le 3V-6$。
  • 性质：简单平面图 ($V\ge 3$) 满足 $E\le 3V-6$。
  • 重要证明：存在度数 $\le 5$ 的顶点
    • 假设所有顶点度数 $\mathrm{deg}(v)\ge 6$。
    • 由握手定理：$2E=\sum \mathrm{deg}(v)\ge 6V\Rightarrow E\ge 3V$。
    • 这与平面图性质 $E\le 3V-6$ 矛盾。
    • 故必然存在 $\mathrm{deg}(v)\le 5$ 的顶点。
  • 推论：$K_5$ ($E=10,3V-6=9$) 不是平面图。
  • 推论：$K_{3,3}$ ($E=9,3V-6=12$, 但它是二分图无三角形，需用 $E\le 2V-4$, $9\nleqq 8$) 不是平面图。
• 常用等价与应用：
  • 连通简单平面图：$E\le 3V-6⟺V\ge (E+6)/3$。
  • 平均度：$\bar{d}=2E/V<6$，因此必存在度 $\le 5$ 的顶点。
  • 判否：若某简单图满足 $E>3V-6$，则必非平面图。
  • 若无三角形 (如二分图)，改用 $E\le 2V-4$。
• 库拉图斯基定理 (Kuratowski)：图是平面图 $⟺$ 不含同胚于 $K_5$ 或 $K_{3,3}$ 的子图。

4.2.4 二分图 (Bipartite Graphs)

• 定义：顶点集可划分为 $X,Y$，且所有边都在 $X$ 与 $Y$ 之间。
• 判定：图是二分图 $⟺$ 图中没有奇数长度的回路。
• 完全二分图：$K_{m,n}$，$|X|=m,|Y|=n$，边数 $E=mn$。
• 度数与边数：$\sum _{x\in X}\mathrm{deg}(x)=\sum _{y\in Y}\mathrm{deg}(y)=|E|$。
• 平面图推论：连通简单二分平面图 ($V\ge 3$) 满足 $E\le 2V-4$。
• 二染色判定 (BFS/DFS)：
  1. 对每个连通分量，任选起点染色为 0。
  2. 进行 BFS/DFS，对每条边 $(u,v)$ 要求 $color[u]\ne color[v]$。
  3. 若遇到冲突 (已染且相同) 则非二分图；无冲突则是二分图。
• 匹配：Hall 定理 (相异代表系)。

4.3 核心算法逻辑

4.3.1 最短路径 (Dijkstra)

适用于非负权图。

1. 初始化：$S=\{start\}$, $dist[start]=0$, 其他无穷大。
2. 循环：
   • 在 $V-S$ 中找 $dist$ 最小的点 $u$。
   • 加入 $S$。
   • 松弛 (Relax) $u$ 的所有邻居 $v$：若 $dist[u]+w(u,v)<dist[v]$，则更新。

4.3.2 图着色 (Graph Coloring)

• 点色数 $\chi (G)$：相邻顶点不同色所需的最少颜色数。
• 布鲁克定理 (Brooks)：若 $G$ 不是奇环也不是完全图，则 $\chi (G)\le \mathrm{\Delta }(G)$ (最大度)。
• 平面图四色定理：平面图 $\chi (G)\le 4$。
• 色多项式 $P_k(G)$：用 $k$ 种颜色染色的方案数。
  • 递推公式：$P_k(G)=P_k(G-e)-P_k(G\cdot e)$
    • $G-e$：删边。
    • $G\cdot e$：收缩边 (合并端点)。

4.3.3 最优二叉树 (Huffman Coding)

常考题型：给定一组权值，构造哈夫曼树并计算带权路径长度 (WPL)。

1. 算法步骤：
   • 初始化：将所有权值看作独立的单节点树森林 $F=\{T_1,T_2,\dots \}$。
   • 循环：
     1. 在 $F$ 中选出根节点权值最小的两棵树 $T_1,T_2$。
     2. 构造新树：根权值为 $W(T_1)+W(T_2)$，左右子树分别为 $T_1,T_2$。
     3. 从 $F$ 中删除 $T_1,T_2$，加入新树。
     4. 重复直到 $F$ 中只剩一棵树。
2. 带权路径长度 (WPL)：
   • $WPL=\sum _{i=1}^n{w}_i\times l_i$
   • $w_i$：第 $i$ 个叶子的权值。
   • $l_i$：第 $i$ 个叶子到根的路径长度（边数）。
   • 简便算法：WPL = 所有非叶子节点的权值之和。