《组合数学》 §3.1 学习笔记

前言：本章节主要讲述容斥原理。可参考容斥原理学习笔记

3.1.1 ~ 3.1.3

略。

定理 3.1.4 （容斥原理）

设 $S$ 为一有限集，$\mathcal{P} = \{P_1,P_2,\cdots,P_m\}$ 为一族性质。

对 $[m]$ 的任一子集 $I$ ，令 $X_I$ 表示 $S$ 中满足性质 $P_i$ （对于所有 $i \in I$ ）的那些元素构成的集合。

特别地，当 $I=\{i\}$ 时，简记 $X_{\{i\}}$ 为 $X_i$ 。记 $\overline{X_I} = S \setminus X_I$ 。

则集合 $S$ 中不具有 $\mathcal{P}$ 中任何一种性质的元素个数由下式给出

$\begin{aligned} \left|\overline{X_1}\cap\overline{X_2}\cdots\cap\overline{X_m}\right| &= |S| - \sum_i |X_i| + \sum_{i < j}|X_i\cap X_j| - \sum_{i < j < k}|X_i\cap X_j\cap X_k| + \cdots + (-1)^m|X_1\cap X_2 \cap \cdots X_m| \\&= \sum_{I \subseteq [m]}(-1)^{|I|}|X_I| \end{aligned}$

证明对任意 $x \in S$ ，记 $J_x = \{i \in[m] \mid x \in X_i\}$ 。按 $J_x$ 是否为空集讨论：

$J_x = \varnothing$ ，即 $x$ 不在任意一个 $X_i$ 中。

此时 $x$ 对原式左端的贡献为 $1$ ；对于右端，$x$ 仅对 $|S|$ 贡献 $1$ ，对其余和式贡献为 $0$ ，

从而对右端贡献也为 $1$ ，故此时原式成立。

$J_x \ne \varnothing$ ，即 $x$ 在某些 $X_i$ 中。设 $j = |J_x|$ ，则 $j > 0$ 。

此时 $x$ 对原式左端的贡献为 $0$ ；对于右端，注意到 $x \in X_I$ 等价于 $I \subseteq J_x$ ，从而 $x$ 对原式右端贡献为
$\sum_{I \subseteq J_x}(-1)^{|I|} = \sum_{i=0}^{j}\binom{j}{i} = (1-1)^j = 0$
故此时原式成立。

综合以上两点，有原式成立。 $\square$

容斥原理是一个很有用的计数原则，它的另一表述为：

设 $S$ 是一个 $n$–集合，$E_1,E_2\cdots E_m$ 是 $S$ 的子集（不一定互不相同）

对任意 $M \subseteq [m]$ 及 $0 \le j \le m$ ，定义

$n(M) = \left|\bigcap_{i \in M} E_i\right|,\quad n_j = \sum_{|M| = j}n(M)$

则 $S$ 中不在每个 $E_i~(1 \le i \le m)$ 中的元素个数为

$n - n_1 + n_2 - n_3 + \cdots + (-1)^m n_m$

例 3.1.5

用容斥原理计算 $n$ 元错位排列的个数 $d_n$ 。

解对于 $n$ 元置换及 $1 \le i \le n$ ，定义性质 $P_i$ 为 $i$ 在置换下保持不变（即 $i$ 为不动点）。

定义 $A_i$ 为 $n$ 元对称群 $S_n$ 中（即 $n$ 元置换群）所有满足性质 $P_i$ 的置换组成的子集，则

$d_n = \left|\overline{A_1}\cap\overline{A_2}\cap\cdots\overline{A_n}\right|$

对任意 $1 \le i_1 < \cdots < i_k \le n$ ，$|A_{i_1}\cap\cdots \cap A_{i_k}|$ 为 $S_n$ 中具有不动点 $i_1,\cdots,i_k$ 的置换个数，即 $(n-k)!$

根据定理 3.1.4 得到

$\begin{aligned} d_n &= \left|\overline{A_1}\cap\overline{A_2}\cap\cdots\overline{A_n}\right| \\[6pt] &= |S_n| - \sum_{i} |A_i| + \sum_{i < j} |A_i \cap A_j| - \sum_{i < j < k}|A_i\cap A_j\cap A_k| + \cdots + (-1)^n|A_1 \cap A_2 \cap \cdots \cap A_n| \\[6pt] &= n! - n(n-1)! + \binom{n}{2}(n-2)! - \binom{n}{3}(n-3)! + \cdots + (-1)^n \binom{n}{n} \\[6pt] &= n! - \frac{n!}{1!} + \frac{n!}{2!}-\frac{n!}{3} + \cdots (-1)^n\frac{n!}{n!} \\[6pt] &= n!\sum_{k=0}^n\frac{(-1)^k}{k!} \end{aligned}$

例 3.1.6

略。

例 3.1.7

从 $[n]$ 到 $\{y_1,\cdots,y_k\}$ 的满射有多少个？给出一个较为简便的公式即可。

解设 $S$ 为所有 $[n]$ 到 $\{y_1,\cdots,y_k\}$ 的映射的集合，则 $|S| = k^n$ 。定义性质 $P_i$ 为 $y_i$ 不是映射的像，

$A_i$ 为满足性质 $P_i~(1\le i \le k)$ 的所有从 $[n]$ 到 $\{y_1,\cdots,y_k\}$ 的映射的集合，则对任意 $1 \le i \le k$ 有

$|A_i| = (k-1)^n$

对任意 $1 \le i_1 < \cdots < i_j\le k$ ，有

$|A_{i_1}\cap \cdots \cap A_{i_j}| = (k - j)^n$

这样，所求的满射的个数为

$\begin{aligned} &\left|\overline{A_1}\cap \overline{A_2}\cap\cdots \overline{A_k}\right| \\[6pt] &= |S_n| - \sum_{i} |A_i| + \sum_{i < j} |A_i \cap A_j| - \sum_{i < j < k}|A_i\cap A_j\cap A_k| + \cdots + (-1)^n|A_1 \cap A_2 \cap \cdots \cap A_n| \\[6pt] &= \sum_{j=0}^k(-1)^j\binom{k}{j}(k-j)^n = \sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n \end{aligned}$

注 3.1.8

由 3.1.7 本身的组合意义可知，若 $k > n$ ，则不存在这样的满射；

若 $k = n$ ，则满射的个数是 $n! = k!$ 。由此可知

$\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}j^n = \begin{cases} 0, &k > n \\[6pt]n!, &k = n \end{cases}$

同时可以看出，出现 $(-1)^i$ 这样的形式往往是可以用容斥原理帮助计数的象征。（~~啊对对对~~）

例 3.1.9 ~ 3.1.11

略。自己看书吧，~~太多了不想打了~~。

定理 3.1.12

与定理 3.1.4 等价的对偶形式是下述定理。

集合 $S$ 的具有 $P_1,P_2,\cdots P_m$ 中至少一种性质的元素个数由下式给出：

$\begin{aligned} &|X_1 \cup X_2\cup \cdots \cup X_m| \\[6pt]&= \sum_{i=1}^m|X_i| - \sum _{i < j}|X_i \cap X_j| + \sum_{i < j < k}|X_i \cap X_j \cap X_k| - \cdots + (-1)^{m-1}|X_1 \cap X_2 \cap \cdots \cap X_{m}| \end{aligned}$

其中第 $j$ 个和式是对 $[m]$ 的所有 $j$–子集 $\{i_1,i_2,\cdots,i_j\}$ 得到的

$(-1)^{j-1}|X_{i_1} \cap X_{i_2}\cap \cdots X_{i_j}|$

进行求和， $1 \le j \le m$ 。