容斥原理与鸽巢原理

本节导读

这个单元大纲列了六条：容斥原理、棋盘多项式与有限制排列、一般公式、二项式反演与 Möbius 反演、鸽巢原理、Ramsey 问题和 Ramsey 数。大纲要求掌握「容斥原理和鸽巢原理的应用」。

两个原理的考法很不一样。容斥原理用于计数，题目要你算出一个具体的数，关键是把「具有某性质」的集合设清楚、把交集算对；鸽巢原理用于证明「一定存在」，关键是想清楚什么是鸽子、什么是巢。学完你应该能写出容斥原理的完整计算过程，并能用鸽巢原理写出简短的存在性证明。

容斥原理

设全集有 N 个元素，$A_1, \ldots, A_n$A1​,…,An​ 是具有各个性质的子集。不具有任何一个性质的元素个数是

$\lvert \overline{A_1} \cap \cdots \cap \overline{A_n} \rvert = N - \sum \lvert A_i \rvert + \sum \lvert A_i \cap A_j \rvert - \sum \lvert A_i \cap A_j \cap A_k \rvert + \cdots + (-1)^n \lvert A_1 \cap \cdots \cap A_n \rvert$∣A1​​∩⋯∩An​​∣=N−∑∣Ai​∣+∑∣Ai​∩Aj​∣−∑∣Ai​∩Aj​∩Ak​∣+⋯+(−1)n∣A1​∩⋯∩An​∣

记成「全部减单个、加两两、减三三……符号交替」。常见的几类应用：

问题	设法与结果
1 到 N 中不被 $d_1, \ldots, d_k$d1​,…,dk​ 中任何一个整除的数	$A_i$Ai​ 是 $d_i$di​ 的倍数，交集用最小公倍数：$\lfloor N / \operatorname{lcm} \rfloor$⌊N/lcm⌋
欧拉函数 $\varphi(n)$φ(n)（1 到 n 中与 n 互素的数）	$\varphi(n) = n \prod (1 - \frac{1}{p})$φ(n)=n∏(1−p1​)，p 取遍 n 的素因子
错排数	$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$Dn​=n!∑k=0n​k!(−1)k​
n 元集到 m 元集的满射	$\sum_{k=0}^{m} (-1)^k C(m, k) (m - k)^n$∑k=0m​(−1)kC(m,k)(m−k)n
$x_1 + \cdots + x_n = r$x1​+⋯+xn​=r 且 $0 \le x_i \le u$0≤xi​≤u	先不管上界，再减去某个 $x_i \ge u + 1$xi​≥u+1 的情形，依此类推

例如 1 到 600 中不被 6、10、15 中任何一个整除的数：6、10、15 的倍数分别有 100、60、40 个；任意两个的最小公倍数都是 30，三个的最小公倍数也是 30，有 20 个。所以被至少一个整除的有 $100 + 60 + 40 - 20 - 20 - 20 + 20 = 160$100+60+40−20−20−20+20=160 个，不被整除的有 440 个。注意交集要用最小公倍数，不能直接把两个数相乘。

棋盘多项式与有限制的排列

把 n 个人分配到 n 项工作，有些人不能做某些工作，这类「有禁区的排列」用棋盘多项式来算。把禁止的格子组成棋盘 B，在 B 上放 k 个互不同行、不同列的棋子（像国际象棋的车，互不攻击）的方法数记作 $r_k(B)$rk​(B)，棋盘多项式 $R(B) = \sum r_k(B) x^k$R(B)=∑rk​(B)xk，$r_0 = 1$r0​=1。

求棋盘多项式有两个工具：任取一个格子，$R(B) = R(B_i) + x R(B_e)$R(B)=R(Bi​)+xR(Be​)，其中 $B_i$Bi​ 是去掉这个格子、$B_e$Be​ 是去掉这个格子所在的行和列；两部分没有公共的行和列时，$R(B) = R(B_1) R(B_2)$R(B)=R(B1​)R(B2​)。有了它，避开禁区的排列数是

$N = \sum_{k=0}^{n} (-1)^k r_k(B) (n - k)!$N=∑k=0n​(−1)krk​(B)(n−k)!

例如 4 个人做 4 项工作，第 1 人不做工作 1、2，第 2 人不做工作 2，第 3 人不做工作 3。禁区中前三格只用到第 1、2 行和第 1、2 列，它们的棋盘多项式是 $1 + 3x + x^2$1+3x+x2；第 3 人那一格单独成块，是 $1 + x$1+x。相乘得 $R(B) = 1 + 4x + 4x^2 + x^3$R(B)=1+4x+4x2+x3，所以 $N = 4! - 4 \times 3! + 4 \times 2! - 1 \times 1! = 7$N=4!−4×3!+4×2!−1×1!=7。

一般公式与反演

设 $S_k$Sk​ 是「任取 k 个性质的交集」的大小之和，恰好具有 m 个性质的元素个数为 $N_m = \sum_{k=m}^{n} (-1)^{k-m} C(k, m) S_k$Nm​=∑k=mn​(−1)k−mC(k,m)Sk​，m = 0 时就是容斥原理本身。

二项式反演：若 $f(n) = \sum_{k=0}^{n} C(n, k) g(k)$f(n)=∑k=0n​C(n,k)g(k)，则 $g(n) = \sum_{k=0}^{n} (-1)^{n-k} C(n, k) f(k)$g(n)=∑k=0n​(−1)n−kC(n,k)f(k)。用法是：某个量「按一部分分类」容易写出总数，就用反演把这一部分解出来。Möbius 反演是它在整除关系上的版本：Möbius 函数 $\mu(1) = 1$μ(1)=1，n 是 r 个不同素数之积时 $\mu(n) = (-1)^r$μ(n)=(−1)r，n 含平方因子时 $\mu(n) = 0$μ(n)=0；若 $f(n) = \sum_{d \mid n} g(d)$f(n)=∑d∣n​g(d)，则 $g(n) = \sum_{d \mid n} \mu(d) f(\frac{n}{d})$g(n)=∑d∣n​μ(d)f(dn​)。