Principle of Inclusion and Exclusion

对于任意有限集合 $ A_1, A_2, \dots, A_n $，容斥原理如下： $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i=1}^{n} \left| A_i \right| - \sum_{1\leq i< j\leq n} \left| A_i \cap A_j \right| + \dots + (-1)^{n} \left| \bigcap_{i=1}^{n} A_i \right| $$
可更紧凑地表示为 $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k-1} \sum_{S \subseteq [n], |S|=k} \left| \bigcap_{i \in S} A_i \right| $$ 或 $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|-1} \left| \bigcap_{i \in S} A_i \right| $$

证

我们通过观察每个元素 $ x $ 对等式两边的贡献来证明。若 $ x $ 不属于任何集合 $ A_i $，则其贡献为 $ 0 $。若 $ x $ 属于恰好 $ m \geq 1 $ 个集合，则对左侧贡献 $ 1 $，对右侧贡献 $ \sum_{j=1}^m (-1)^{j-1} \binom{m}{j} $。由二项式定理，$ \sum_{j=0}^m (-1)^j \binom{m}{j} = 0 $（当 $ m \geq 1 $），故 $ \sum_{j=1}^m (-1)^{j-1} \binom{m}{j} = 1 $，等式成立。

补集形式

在组合学中，常使用补集形式。给定全集 $ U $ 和子集 $ B_1, B_2, \dots, B_n $（视为“坏事件”），不属于任何 $ B_i $ 的元素数量为： $$ \left| U \setminus \bigcup_{i=1}^n B_i \right| = \sum_{S \subseteq [n]} (-1)^{|S|} \left| \bigcap_{i \in S} B_i \right| $$
其中约定 $ \bigcap_{i \in \emptyset} B_i = U $。

Derangements and Surjective Functions

Surjective Counting

考虑从 $ [n] $ 到 $ [m] $ 的满射（surjective functions）。设全集 $ U $ 为所有映射，$ |U| = m^n $。定义 $ B_i $ 为没有元素映射到 $ i \in [m] $ 的映射集合，则 $ \left| \bigcap_{k \in S} B_k \right| = (m - |S|)^n $。由补集形式，满射数量为： $$ m! \left\{ n \atop m \right\} = \sum_{k=0}^m (-1)^k \binom{m}{k} (m-k)^n = \sum_{k=0}^m (-1)^{m-k} \binom{m}{k} k^n $$

Derangement Counting

错排：一个置换 $ f: [n] \to [n] $ 称为错排，若无固定点，即 $ \forall x \in [n], f(x) \neq x $。错排的循环分解不含大小为 $ 1 $ 的循环。$ D_n $ 表示 $ n $ 个元素的错排数量。

方法 1：容斥原理

设 $ U $ 为 $ [n] $ 上的所有置换，$ |U| = n! $。定义 $ B_i $ 为固定 $ i $ 的置换集合（$ f(i) = i $）。则 $ \left| \bigcap_{i \in S} B_i \right| = (n - |S|)! $，错排数量为 $$ D_n = \sum_{S \subseteq [n]} (-1)^{|S|} (n - |S|)! = n! \sum_{k=0}^n \frac{(-1)^k}{k!} $$ 当 $ n \to \infty $，$ D_n / n! \approx 1/e $，表示随机置换为错排的概率趋于 $ 1/e $。

方法 2：循环分解

方法 3：指数生成函数

先求出递推式

递推 1：$ D_n = (n-1)(D_{n-1} + D_{n-2}) $，初始条件 $ D_0 = 1 $，$ D_1 = 0 $。

证：考虑错排 $ f $，$ f(n) = k \neq n $。分两种情况：

  • 若 $ f(k) = n $，移除 $ n $ 和 $ k $，其余 $ n-2 $ 个元素形成错排，贡献 $ (n-1)D_{n-2} $。
  • 若 $ f(k) \neq n $，构造 $ g: [n-1] \to [n-1] $，使 $ g(i) = f(i) $（$ i \neq k $），$ g(k) = n $，$ g $ 为 $ [n-1] $ 上的错排，贡献 $ (n-1)D_{n-1} $。

递推 2：$ D_n = n D_{n-1} + (-1)^n $。

证：由第一种递推关系代数推导，或考虑若 $ \sigma(n) = n $，则其余 $ n-1 $ 个元素形成错排，贡献 $ D_{n-1} $。

定义 $ D(x) = \sum_{n=0}^\infty \frac{D_n}{n!} x^n $。由递推 $ D_n = n D_{n-1} + (-1)^n $，得微分方程 $ D(x) - x D'(x) = e^{-x} $，解得 $ D(x) = \frac{e^{-x}}{1-x} $。展开： $$ D(x) = \left( \sum_{k=0}^\infty \frac{(-1)^k}{k!} x^k \right) \left( \sum_{j=0}^\infty x^j \right) $$
提取 $ x^n $ 的系数，$ \frac{D_n}{n!} = \sum_{k=0}^n \frac{(-1)^k}{k!} $，即 $ D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} $。

方法 3：置换拆分

把一个置换看成若干个环的组合，错排表示拆分中没有大小为 $ 1 $ 的环。（后续过程待完成）

方法 4：固定点计数

恰有 $ k $ 个固定点的置换数为 $ \binom{n}{k} D_{n-k} $。总置换数为 $$ n! = \sum_{k=0}^n \binom{n}{k} D_{n-k} $$ 通过莫比乌斯反演，可推导 $ D_n $ 的显式公式。

积和式

定义 $ n \times n $ 矩阵 $ A = (a_{i,j}) $ 的积和式为 $$ \text{perm } A = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i, \sigma(i)} $$
若 $ A $ 为 0-1 矩阵，perm $ A $ 计数满足 $ a_{i, \sigma(i)} \neq 0 $ 的置换数。特别地，$ D_n = \text{perm}(1_n - I_n) $。对于二分图的邻接矩阵，perm $ A $ 计数完美匹配数量。

容斥计算积和式

设 $ U = S_n $，$ B_i = {\sigma \in S_n \mid a_{i, \sigma(i)} = 0} $。令 $ R = {(i,j) \mid a_{i,j} = 0} $，$ r_k $ 为 $ R $ 中 $ k $ 个互不共享行或列的坐标对数量。则 $$ \sum_{S: |S|=k} \left| \bigcap_{i \in S} B_i \right| = r_k (n-k)! $$
积和式为 $$ \text{perm } A = \sum_{k=0}^n (-1)^k r_k (n-k)! $$
更优方法：设 $ U $ 为满足 $ a_{i,f(i)} \neq 0 $ 的映射集合，$ B_i $ 为 $ f^{-1}(i) = \emptyset $ 的映射集合。则： $$ |U| = \prod_{i=1}^n \left( \sum_{j=1}^n a_{i,j} \right), \quad \left| \bigcap_{k \in S} B_k \right| = \prod_{i=1}^n \left( \sum_{j \in [n] \setminus S} a_{i,j} \right) $$
Ryser 公式： $$ \text{perm } A = \sum_{S \subseteq [n]} (-1)^{|S|} \prod_{i=1}^n \left( \sum_{j \in [n] \setminus S} a_{i,j} \right) $$

Möbius Inversion in Number Theory

欧拉函数

欧拉函数 $ \phi(n) $ 为 $ [n] $ 中与 $ n $ 互质的正整数数量： $$ \phi(n) = \sum_{k=1}^n [\gcd(n,k) = 1] $$ $ \phi(n) $ 是积性函数：若 $ \gcd(a,b) = 1 $，则 $ \phi(ab) = \phi(a)\phi(b) $。对于素数 $ p $，$ \phi(p) = p-1 $，$ \phi(p^r) = (p-1)p^{r-1} $。

性质：$ \sum_{d|n} \phi(d) = n $。

证：对于 $ k \in [n] $，若 $ \gcd(n,k) = d $，则 $ \gcd(n/d, k/d) = 1 $。故 $$ n = \sum_{d|n} |{k \in [n] \mid \gcd(n,k) = d}| = \sum_{d|n} \phi(n/d) = \sum_{d|n} \phi(d) $$

容斥计算 $ \phi(n) $

设 $ n = p_1^{r_1} \dots p_m^{r_m} $，$ U = [n] $，$ B_i = {k \in [n] \mid p_i \text{ 整除 } k} $。则 $ \phi(n) = \left| U \setminus \bigcup_{i=1}^m B_i \right| $，且 $ \left| \bigcap_{i \in S} B_i \right| = \frac{n}{\prod_{i \in S} p_i} $。由补集形式 $$ \phi(n) = n \prod_{i=1}^m \left( 1 - \frac{1}{p_i} \right) $$ 莫比乌斯函数 $$ \mu(n) = \begin{cases} 1 & \text{若 } n = 1 \\ 0 & \text{若 } \exists p, p^2 \text{ 整除 } n \\ (-1)^k & \text{若 } n = p_1 \dots p_k \text{（不同素数）} \end{cases} $$则 $$ \phi(n) = \sum_{d|n} \mu(d) \frac{n}{d} $$

莫比乌斯反演公式

若 $ f = g * 1 = \sum_{d|n} g(d) $，则 $$ g = f * \mu = \sum_{d|n} f(d) \mu(n/d) $$

证明：设 $ n = p_1^{r_1} \dots p_m^{r_m} $，$ U = \bigcup_{d|n} T_d $，$ T_d = \{(d,j) \mid 1 \leq j \leq g(d)\} $，$ B_i = \{(d,j) \in U \mid p_i \mid d\} $。则 $ g(n) = \left| U \setminus \bigcup B_i \right| $，且 $ |U| = f(n) $，$ \left| \bigcap_{i \in S} B_i \right| = f\left( n / \prod_{i \in S} p_i \right) $。由补集形式： $$ g(n) = \sum_{S \subseteq [m]} (-1)^{|S|} f \left( n / \prod_{i \in S} p_i \right) = \sum_{d|n} \mu(d) f(n/d) $$

集合函数反演

若 $ f(S) = \sum_{T \subseteq S} g(T) $，则 $$ g(S) = \sum_{T \subseteq S} (-1)^{|S|-|T|} f(T) $$

应用：有限域上不可约多项式

在有限域 $ F_q $（$ q = p^t $）上，次数为 $ n $ 的首一不可约多项式数量 $ N_n $ 满足 $$ q^n = \sum_{d|n} d N_d $$
由莫比乌斯反演 $$ N_n = \frac{1}{n} \sum_{d|n} \mu(n/d) q^d $$

证：设 $ F(x) = \sum_{n=0}^\infty q^n x^n = \frac{1}{1-qx} $ 为首一多项式数量的 OGF。由唯一分解定理 $$ F(x) = \prod_{d=1}^\infty \left( \frac{1}{1-x^d} \right)^{N_d} $$
取对数并比较 $ x^n $ 系数，得 $ q^n = \sum_{d|n} d N_d $，再反演得结果。