容斥原理：正确计算重叠集合中元素个数的强大技巧

1. 引言

在数学和计算机科学中，我们经常会遇到需要计算满足多个条件的元素数量的情况。然而，当存在多个条件时，满足每个条件的元素集合通常会重叠（有交集）。简单地将它们相加会导致元素被多次计算。

一种能准确消除这些重叠并得出正确元素数量的强大方法是 容斥原理 （Inclusion-Exclusion Principle）。

在本文中，我们将全面详细地解释容斥原理，从其基本概念到一般化的数学公式、数学证明以及具体的应用实例（例如欧拉函数和错排问题）。此外，我们还将介绍编程实现示例，以从理论和实践两个角度加深您的理解。

2. 集合与元素数量的基础

在学习容斥原理之前，让我们先回顾一下基本的集合符号。

\(A, B\) ：集合
\(|A|\) ：集合 \(A\) 的元素数量（势）
\(A \cup B\) ：集合 \(A\) 和集合 \(B\) 的并集（属于至少其中一个的元素）
\(A \cap B\) ：集合 \(A\) 和集合 \(B\) 的交集（两者都属于的元素）

我们要寻找的是多个集合的并集的元素数量，即 \(|A \cup B \cup \dots|\) 。

3. 2个集合的容斥原理

让我们考虑最简单的包含两个集合 \(A\) 和 \(B\) 的情况。

3.1 公式

\[ |A \cup B| = |A| + |B| - |A \cap B| \]

3.2 直观理解

  flowchart TD
    U["全集 U"]
    A["集合 A"]
    B["集合 B"]
    AandB["A ∩ B (交集)"]
    U -->|"包含"| A
    U -->|"包含"| B
    A -->|"重叠"| AandB
    B -->|"重叠"| AandB

4. 3个集合的容斥原理

当有三个集合时，它变得稍微复杂一些。考虑集合 \(A, B, C\) 。

4.1 公式

\[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C| \]

4.2 直观理解与证明

首先，将所有单独的元素数量相加： \(|A| + |B| + |C|\)
这样做之后，任意两个集合的交集都被加了两次，因此将它们减去： \(- |A \cap B| - |B \cap C| - |C \cap A|\)
最后，考虑所有三个集合的交集 \(A \cap B \cap C\) 。它在步骤1中被加了3次，在步骤2中被减了3次，导致其当前的计算次数为 \(0\) 。因此，我们在最后再把它加回来一次： \(+ |A \cap B \cap C|\)

4.3 具体示例：1到100中能被2、3或5整除的整数的数量

全集： \(U = \{1, 2, \dots, 100\}\)
2的倍数集合： \(A\)
3的倍数集合： \(B\)
5的倍数集合： \(C\)

让我们计算每个集合的元素数量（其中 \(\lfloor x \rfloor\) 表示向下取整函数）。

\(|A| = \lfloor 100 / 2 \rfloor = 50\)
\(|B| = \lfloor 100 / 3 \rfloor = 33\)
\(|C| = \lfloor 100 / 5 \rfloor = 20\)
\(|A \cap B|\) (6的倍数) \(= \lfloor 100 / 6 \rfloor = 16\)
\(|B \cap C|\) (15的倍数) \(= \lfloor 100 / 15 \rfloor = 6\)
\(|C \cap A|\) (10的倍数) \(= \lfloor 100 / 10 \rfloor = 10\)
\(|A \cap B \cap C|\) (30的倍数) \(= \lfloor 100 / 30 \rfloor = 3\)

\[ |A \cup B \cup C| = 50 + 33 + 20 - 16 - 6 - 10 + 3 = 74 \]

因此，能被2、3或5整除的数字有 74 个。

5. 一般 \(n\) 个集合的容斥原理

将其推广到 \(n\) 个集合 \(A_1, A_2, \dots, A_n\) ，我们得到以下优美的公式。

5.1 公式

\[ \left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} \left( \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} \left| A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \right| \right) \]

用文字表达，该操作重复了“加上奇数个集合交集的元素数量，减去偶数个集合交集的元素数量”。

5.2 数学证明概要

我们将证明任何元素 \(x \in \bigcup_{i=1}^n A_i\) 在右侧的计算中被准确计算了1次。

假设某个元素 \(x\) 恰好包含在 \(m\) 个集合中（ \(1 \le m \le n\) ）。元素 \(x\) 在右侧被计算的次数可以使用二项式系数表示如下：

\[ \text{计算次数} = \binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \dots + (-1)^{m-1} \binom{m}{m} \]

根据二项式定理，已知 \((1 - 1)^m = \binom{m}{0} - \binom{m}{1} + \binom{m}{2} - \dots + (-1)^m \binom{m}{m} = 0\) 。将其变形：

\[ \binom{m}{0} - \left( \binom{m}{1} - \binom{m}{2} + \dots + (-1)^{m-1} \binom{m}{m} \right) = 0 \]

由于 \(\binom{m}{0} = 1\) ，括号内的表达式（即 \(x\) 被计算的次数）的值正好是 \(1\) 。这证明了每个元素都恰好被计算一次，没有重复。

6. 应用示例1：欧拉函数

欧拉函数 \(\varphi(N)\) 表示从 \(1\) 到 \(N\) 中与 \(N\) 互质的整数的数量。这也可以使用容斥原理来计算。

设 \(N\) 的质因数为 \(p_1, p_2, \dots, p_k\) 。设全集为 \(U = \{1, 2, \dots, N\}\) ， \(A_i\) 为“ \(p_i\) 的倍数的集合”。我们要寻找的是不属于任何 \(A_i\) 的元素数量。

\[ \varphi(N) = N - \left| \bigcup_{i=1}^k A_i \right| \]

应用容斥原理并进行化简可得出这个著名的公式：

\[ \varphi(N) = N \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_k}\right) \]

7. 应用示例2：错排问题

错排是指将数字 \(1\) 到 \(n\) 进行排列，使得没有任何第 \(i\) 个数字在第 \(i\) 个位置上。例如，这等同于在交换礼物时分配礼物的总方式，使得没有人在其中收到自己的礼物。

设 \(A_i\) 为“ \(i\) 在第 \(i\) 个位置的排列的集合”。全集的元素数量为 \(n!\) 。我们想要求的是 \(n! - |A_1 \cup A_2 \cup \dots \cup A_n|\) 。

任何 \(k\) 个集合交集的元素数量是 \((n-k)!\) ，而选择这些 \(k\) 个集合的方法有 \(\binom{n}{k}\) 种。应用容斥原理，错排的数量 \(D_n\) 如下：

\[ D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \]

8. 通过编程计算和实现

容斥原理在编程中非常有用。特别是当结合位运算全排列搜索（二进制枚举）时，\(n\) 个条件的容斥原理可以被简洁地实现。

以下是使用 Python 来寻找“在1到 \(M\) 之间能被给定列表中的任何素数整除的整数数量”的代码。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def count_multiples(M: int, primes: list[int]) -> int:
    n = len(primes)
    total_count = 0
    
    # 使用从1到 2^n - 1 的位掩码遍历所有子集
    for i in range(1, 1 << n):
        lcm = 1
        set_bits = 0
        
        # 计算所选素数的乘积（最小公倍数）
        for j in range(n):
            if (i >> j) & 1:
                lcm *= primes[j]
                set_bits += 1
                
        # 如果选择了奇数个素数则相加，如果是偶数则相减（容斥原理）
        if set_bits % 2 == 1:
            total_count += M // lcm
        else:
            total_count -= M // lcm
            
    return total_count

# 执行示例
M = 100
primes = [2, 3, 5]
# 预期输出: 74
print(f"结果: {count_multiples(M, primes)}")