CS2304 计算机科学中的数学基础课程期末复习。

Set and Ordering

有关集合的基础知识在此不再赘述。

对称差 (Symmetric Diff)仅在 或 中的元素：

$$A \oplus B = (A - B) \cup (B - A)$$

Relations and Functions

• 有序对：$<x,y> = <u,v> \Leftrightarrow x=u \land y=v$
• 笛卡尔积：$A \times B = \{<x,y> \mid x \in A \land y \in B\}$

关系

• 二元关系：$R \subseteq A \times B$（有序对的集合）
• 性质：
  • 自反性：$\forall a \in A (aRa)$
  • 对称性：$\forall a,b \in A (aRb \to bRa)$
  • 传递性：$\forall a,b,c \in A (aRb \land bRc \to aRc)$

等价关系与划分

• 等价关系：同时满足自反、对称、传递的关系
• 等价类：$[x]_R = \{y \mid xRy\}$
• 划分：集合 A 的非空互斥子集族，覆盖 A

函数

• 函数定义：关系 F 满足
  • $\forall x \in \text{dom } F, \exists! y (xFy)$ , 记作 F(x) = y
• 特殊函数：
  • 单射 (Injective)：$x_1 \neq x_2 \to F(x_1) \neq F(x_2)$
  • 满射 (Surjective)：$\text{ran } F = B$
  • 双射 (Bijective)：单射且满射

Orderings

偏序 (Partial Order)

• 定义：关系 满足：
  • 自反性：
  • 反对称：
  • 传递性：
• 线性序 (Total Order) 是偏序的特例，满足：
  • 任意两元素可比较：$\forall a,b (a \leq b \lor b \leq a)$
  • 唯一极大元和极小元
• 哈斯图 (Hasse Diagram)：
  仅保留直接后继关系（ 表示 是 的立即后继）

特殊元素

性质：

• 最大/最小元一定是极大/极小元，但反之不成立
• 有限偏序集必存在极小元与极大元

线性扩充定理

线性扩充(Linear extensions):对有限偏序集 $(S, \preccurlyeq)$, 存在一个线性序集 $(S, \preccurlyeq')$ 满足

$$x \preccurlyeq y \to x \preccurlyeq' y .$$

即任何偏序集都可以扩展为线性序，且保持原有序关系。（实际上是拓扑排序）

反链与链

Dilworth 定理

• 核心结论：最大反链大小等于最小反链划分数
  
• 推论：
  其中 是最大反链大小， 是最长链长度

应用：Erdős–Szekeres 引理

任意含 个元素的实数序列，必存在长度为 的单调子序列。

基数 (Cardinality)

等势 (Equinumerosity)

• 定义：
• 重要结论：
  • （自然数与有理数等势）
  • （实数集不可数）
  • （Cantor 定理）

连续统假设 (Continuum Hypothesis)

• 问题：是否存在基数 满足 ？
• 结论：在 ZFC 公理系统中既不能证明也不能证伪（Gödel & Cohen）

Combinatorics

基础计数问题：球入箱模型

n个球放入m个箱子的不同情形：

其中：

• $(m)_n$：下降阶乘
• $\begin{Bmatrix} n \\ k \end{Bmatrix}$：第二类Stirling数（集合划分）
• $p_k(n)$：整数n划分为k部分的方案数

基本计数原理

子集计数

• n元素集合的子集数：$2^n$
• k元子集数：$\binom{n}{k} = \frac{n!}{k!(n-k)!}$

排列计数

• n元素集合的排列数：$n!$
• 带限制排列（多项式系数）： $$\binom{n}{k_1,k_2,\ldots,k_m} = \frac{n!}{k_1!k_2!\cdots k_m!}$$

二项式定理与多项式定理

二项式定理

$$(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k$$

推论：

• $$\sum_{k=0}^n \binom{n}{k} = 2^n$$
• $$\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$$

多项式定理

$$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+\cdots+k_m=n} \binom{n}{k_1,\ldots,k_m} x_1^{k_1}\cdots x_m^{k_m}$$

广义二项式定理（牛顿）

$$(x+y)^r = \sum_{k=0}^\infty \binom{r}{k} x^{r-k}y^k, \quad |x|>|y|$$

其中 $\binom{r}{k} = \frac{r(r-1)\cdots(r-k+1)}{k!}$

特殊计数序列

Catalan数

定义：

$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

递推关系：

$$C_0=1, \quad C_n = \sum_{k=0}^{n-1} C_k C_{n-k-1}$$

应用：

• 凸n+2边形三角剖分
• Dyck路（不穿越对角线的网格路径）
• 合法括号序列数

Stirling数

• 第二类Stirling数（集合划分）：

  $$\begin{Bmatrix} n \\ k \end{Bmatrix} = k\begin{Bmatrix} n-1 \\ k \end{Bmatrix} + \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}$$

• 第一类Stirling数（轮换排列）：

  $$\begin{bmatrix} n \\ k \end{bmatrix} = (n-1)\begin{bmatrix} n-1 \\ k \end{bmatrix} + \begin{bmatrix} n-1 \\ k-1 \end{bmatrix}$$

性质：

$$\sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} = B_n \text{（Bell数）}, \quad \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} = n!$$

容斥原理

基本公式

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq I \subseteq [n]} (-1)^{|I|-1} \left| \bigcap_{i \in I} A_i \right|$$

应用

错排问题（Derangement）：

$$D(n) = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \sim \frac{n!}{e}$$

欧拉函数（Euler’s totient）：

$$\varphi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right)$$

生成函数

普通生成函数（OGF）

定义：

$$A(x) = \sum_{n=0}^\infty a_n x^n$$

生成函数的操作

应用

Fibonacci序列：

$$F(x) = \frac{x}{1-x-x^2}$$

Catalan数：

$$C(x) = \frac{1 - \sqrt{1-4x}}{2x}$$

递推关系求解

齐次线性递推

$$h_n = \sum_{i=1}^k a_i h_{n-i}$$

解法：

1. 解特征方程：$x^k - a_1 x^{k-1} - \cdots - a_k = 0$
2. 根据根的情况构造通解：
   • 单根 $\lambda_i$：$c_i \lambda_i^n$
   • 重根 $r$重：$(c_0 + c_1 n + \cdots + c_{r-1} n^{r-1}) \lambda^n$

非齐次递推

$$h_n = \sum_{i=1}^k a_i h_{n-i} + b_n$$

通解 = 齐次解 + 特解（根据 $b_n$ 形式假设特解）

渐近分析

渐近符号

• f(n) = O(g(n))：$\exists C>0, n_0 \quad \forall n>n_0: |f(n)| \leq C g(n)$
• $f(n) = \Theta(g(n))$：f=O(g) 且 g=O(f)

重要渐近估计

阶乘（Stirling公式）：

$$n! \sim \sqrt{2\pi n} \left( \frac{n}{e} \right)^n$$

调和级数：

$$H_n = \sum_{k=1}^n \frac{1}{k} \sim \ln n$$

二项式系数：

$$\binom{n}{k} \leq \left( \frac{en}{k} \right)^k, \quad \text{当 } k=o(\sqrt{n}) \text{ 时 } \binom{n}{k} \sim \frac{n^k}{k!}$$

Graph theory

图论中已有详细介绍

（吐槽：图论这玩意从大一下数据结构开始学，大二上电路理论、离散数学又学一遍，大二下算法以及这门数学课又学一遍，只能说饱和式学习了）

The probabilistic method

同上，基础概念不再赘述。

随机变量

定义与分布

• 随机变量
• 离散分布：

期望与方差

• 期望：
• 方差：
• 线性性： $$E\left[\sum X_i\right] = \sum E[X_i], \quad E[cX] = cE[X]$$

常见分布

几何分布无记忆性

$$Pr(X=n+k \mid X>k) = Pr(X=n)$$

---

概率不等式

基础不等式

• Markov：对非负 和 ： $$Pr(X \geq a) \leq \frac{E[X]}{a}$$
• Chebyshev： $$Pr(|X - E[X]| \geq a) \leq \frac{Var[X]}{a^2}$$

Chernoff 界

对独立 Bernoulli() 变量，，：

• 上界：
• 下界：

---

概率方法

通过随机选择指定类别的对象，证明目标对象存在的概率大于零，是一种非构造性方法。

基本计数论证

• 布尔函数存在性：存在需要 符号描述的 变量布尔函数 $$2^{2^n} > (n+8)^m \implies m < 2^n / \log_2(n+8)$$

期望论证

• 图分割： 顶点 边图存在割 的划分 $$E[\text{割边数}] = m \cdot \frac{n}{2n-1} > \frac{m}{2}$$
• 独立集下界： $$\alpha(G) \geq \sum_{v} \frac{1}{\deg(v)+1} \geq \frac{n^2}{2|E|+n} \quad (\text{Turán's theorem})$$
• MAXSAT： 子句（最小长度 ），存在赋值满足 子句 $$E[\text{满足子句数}] = \sum (1-2^{-k_i}) \geq m(1-2^{-k})$$

Lovász 局部引理

事件 依赖图最大度 ，若 且 ，则：

$$Pr\left(\bigcap \overline{E_i}\right) > 0$$

应用：

• -SAT 中变量出现次数 时可满足
• 边不相交路径存在性：当 时存在解

Random graph

随机图