【汉化】筛分法

MichaelWong - 二两碘酊 / 2023-05-10 / 原文

5 筛分法

筛分法本质上有两个变体。为确定一个集合的大小，我们会多算，然后从这个数中减去，再加上，再减去……直到元素的个数最终被精确确定。一个典例就是 容斥原理。在第二个变体中，我们会通过合适的权重筛掉不想要的元素。这就是对合原理背后的本质思路。

5.1 容斥

考虑一个有限集 \(X\) 和三个子集 \(A,B,C.\) 要算出 \(|A \cup B \cup C|\)，我们会求和 \(|A|+|B|+|C|.\) 除非 \(A,B,C\) 互无交集，否则我们就多算了，因为 \(A \cap B,A \cap C,B \cap C\) 被算了两次。所以我们减去 \(|A \cap B|+|A \cap C|+|B \cap C|.\) 现在这个数就对了，除了 \(A \cap B \cap C\) 里的元素。他们被加上了三次，又被减去了三次。因此答案为

或者说，

下面是通式。

使 \(A_1,A_2, \dots ,A_n\) 为 \(X\) 的子集，那么

\[\left| X \setminus \bigcup \limits_{i=1}^{n} A_i \right| = \left| X \right|- \sum \limits_{i=1}^{n} \left| A_i \right| + \sum \limits_{i<j} \left| A_i \cap A_j \right| \mp \cdots + (-1)^n \left| A_1 \cap \cdots \cap A_n \right|. \quad (1) \]

为证明，我们检查一个元素 \(x \in X\) 被算重了几次。如果 \(x \not \in \bigcup_{i=1}^n A_i\)，那么它在方程的两边都算了一次。假设 \(x \in \bigcup_{i=1}^n A_i\)，更精确来说， \(x\) 恰好在 \(A_i\) 的 \(m\) 个中。方程左边为 \(0,\) 对右边，由于 \(m \geq 1,\) 我们由 \((1)\) 得

\[1 - \dbinom{m}{1} + \dbinom{m}{2} - \dbinom{m}{3} \pm \cdots + (-1)^m \dbinom{m}{m}=0. \]

由这个基本的解释可得容斥原理。假设给定一个集合 \(X,\) 称为总集，和一个属性集 \(E=\{ e_1, \dots ,e_n \},X\) 可能有，也可能没有这些属性。使 \(A_i\) 为享有属性 \(e_i\)（可能还有其他属性）的元素的集合。那么 \(\left| X \setminus \bigcup_{i=1}^n A_i \right|\) 就是不拥有任何属性的元素的数量。现在考虑 \((1)\) 右边的写法。显而易见，\(A_{i_1} \cap \cdots \cap A_{i_t}\) 就是拥有属性 \(e_{i_1}, \dots, e_{i_t}\) （可能还有其他属性）的集合。使用如下记法：

\[\begin{aligned} N_{\supseteq T} := \# \{ x \in X : x \text{ 至少拥有 } T \textsf{ 中的属性} \}, \\ N_{= T} := \# \{ x \in X : x \text{ 有且仅有 } T \textsf{ 中的属性} \}, \end{aligned} \quad (2) \]

我们得到了容斥原理。

容斥原理. 使 \(X\) 为一个集合，且 \(E= \{ e_1, \dots , e_n \}\) 为属性集。那么

\[N_{= \varnothing} = \sum \limits_{T \subseteq E} (-1)^{\left| T \right|} N_{\supseteq T} = \sum \limits_{k=0}^{n} (-1)^k \sum \limits_{T: \left| T \right| = k} N_{\supseteq T}. \quad (3) \]

在 \(N_{\supseteq T}\) 只取决于集合大小 \(\left| T \right| = k\) 时，这个方程甚至会变得更简单。由于 \(\left| T \right| = k,\) 我们就可以写作 \(N_{\supseteq T} = N_{\geq k},\) 并称呼 \(E\) 为同质属性集。我们马上可得在这种情况下 \(N_{=T} = N_{=k}\) 也只取决于 \(T\) 的势。因此对于同质属性集，有

\[N_{=0} = \sum \limits_{k=0}^{n} (-1)^k \dbinom{n}{k} N_{\geq k}. \quad (4) \]