《组合数学》 §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\) 。