容斥原理与计数应用

可视化演示

展示容斥原理解决重叠集合计数问题，通过韦恩图、错排问题与欧拉函数三种模式理解交替加减的核心思想。

容斥原理基础

派对主办者把几个圈子的名单叠在一起时，最头疼的事就是“重复”。每个人似乎总有那么几个身份重叠：既是毽球群元老，又是桌游群常客，还可能是烘焙比赛冠军。想要知道“不重不漏”的总人数，主办者必须先理解一个更底层的概念——集合运算：我们把每个圈子想象成一个“箱子”，箱子之间可以有重叠的部分，这份重叠就是交集（取两家名单里共同出现的名字），而所有箱子合在一起就是并集（只要出现在任何一个箱子里就算）。

在数学里，容斥原理关心的是并集的大小。两个集合的并集大小显然不是简单地把各自大小相加，因为交集部分被数了两次。用集合论的记号来表达，对于两个集合 A 和 B，“不重不漏”的并集计数方式为：

回到派对主办者的处境：把毽球群和桌游群合并时，他只需要先相加再减去重叠者，就得到了第一批稳重的来宾预测。这第一步，就是容斥原理这座大厦的第一块砖——两个箱子叠加时，去掉那些“两面派”。

双集合特例

主办者遇到的第一个简化情况，是只有毽球群（A）和桌游群（B）两个“箱子”。如果两个群完全没有交集（没有一个人同时加两个群），那么公式退化为简单的加法。但如果交集不为空，就必须执行“交叠即减”的操作。

这是最直观的特例：两个集合的并集计数，就是“各自的独立人数相加，再减去重叠的那一群人”。用图形来想，就是两个圆叠在一起，中间那一小块月牙形的重叠区被数了两次，所以我们把它挖掉一次。这个过程可以用一个简单的步骤表达：

更一般地，若存在三个或更多的集合，这个公式可以依次推广。比如三个集合 A、B、C 的并集大小是：

主办者手里有两份名单时，这个特例就像一把直尺，量出重叠，立即减去。双集合特例虽简单，却是理解整个容斥原理“加减交替”节奏的起点。

三集合推广

现在派对主办者收到了第三份名单——烘焙群。三份名单两两重叠，甚至还有三个人同时出现在三份名单里的“超级活跃分子”。如果继续用“先加后减”的思路，主办者会遇到一个微妙的问题：当三个集合 A、B、C 都存在时，|A∩B∩C| 在第二轮减法中被减去了整整三次，而这部分人原本应当在最终并集中被保留。

这正是容斥原理的深层智慧：每一项修正都会引入新的“修正偏差”，于是需要交替地加减，直到最内层的所有交集都被处理干净。那三个集合都喜欢的人，在 |A|+|B|+|C| 中被算了 3 次，又在 |A∩B|+|A∩C|+|B∩C| 中被减了 3 次，于是净计数归零。为了把它救回来，我们必须加回一次 |A∩B∩C|。

三份名单的派对预测，让主办者体会到了“交替加减”的节奏——加一次，减一堆，再加回那个被误伤的“核心团体”。这种交替的意识，很快就会延伸到任意数量的集合。

容斥通用形式

当派对主办者意识到自己可能拥有几十个不同的部门、社群或客户群时，双集合和三集合的手工计算就不再可行。他需要的是一条“统一公式”，不管有多少个箱子，都能按同样的节奏算到底。

容斥原理的通用形式正是为这种场景而生：设我们有 n 个集合 A₁, A₂, …, Aₙ，它们的并集大小可以写成对所有非空子集 S 的交替求和。每一项的符号由子集的大小 |S| 决定：奇数个集合取正，偶数个集合取负。最后的收尾项往往是所有集合的交集（|S| = n 时），因此整个序列以一个清晰的符号结束。

这就像主办者终于请到了一位专业的“派对统计师”，他不再需要蹲在地上一项一项地核对，只需把每个子集对应的重叠人数按“奇正偶负”规则排成一列，一加一减，答案自然浮现。

错排问题

派对主办者想把礼物随机分给来宾们，他的要求很特别：每个人都不能拿到写有自己名字的礼物。如果 n 个朋友的礼物被随机打乱，究竟有多少种分配方式能保证“人人拿到的都是别人的礼物”？这种“完全错位”的排列叫做错排。主办者凭直觉意识到，这个问题的答案藏在容斥原理的“排除法”里——先把所有排列都算上，再逐步排除那些有人拿到自己礼物的坏情况。

设 n 个元素的全部排列数为 n!。我们用集合 Aᵢ 表示“第 i 个人拿到了自己的礼物”这一坏事件。那么“没有人拿到自己礼物”的全错排数 Dₙ，就是从总数中排除掉所有 Aᵢ 的并集。这正是容斥原理的经典战场：算出 Aᵢ 的并集大小，再从 n! 中减去，公式推导得到：

派对主办者惊喜地发现，无论来宾有多少，只要随机打乱礼物，保证所有人都拿到别人礼物的概率总是稳定在 36.8% 左右。这份“乱中有序”的奇妙常数，就是错排问题赠送给容斥原理的勋章。

欧拉函数

当派对名单上的所有人都换上了从 1 到 n 的数字编号，主办者想统计其中与 n 互素的编号个数——这些编号与 n 没有大于 1 的公因数。这个统计量在数论中叫做欧拉函数 φ(n)，它也是密码学中 RSA 算法的重要构件。容斥原理在这里扮演的角色，是从 1 到 n 的完整列表里，逐一剔除那些与 n 共享质因子的“坏编号”。

例如 n = 12，质因子是 2 和 3。我们想统计 1 到 12 中既不能被 2 整除、也不能被 3 整除的数。先用容斥原理：12 中所有数减去 2 的倍数，再减去 3 的倍数，最后加回“既是 2 的倍数又是 3 的倍数”（即 6 的倍数）：

派对主办者看着这份编号表，突然觉得容斥原理不只是记人数的工具——它像一台筛子，把“不想要的分子”一层层筛走，只保留那些与 n 互素的忠实宾客。这也正是欧拉函数被称为“筛出来的计数”的原因。

满射函数计数

如果派对主办者想把 m 件不同的礼物分给 n 个朋友，规则是每位朋友至少得到一件礼物，那么他要统计的就是“满射函数”的数量——每个收到礼物的人都不能空手而归。这是一个更复杂的计数问题，因为礼物是互不相同的，而每位朋友的“名额”没有上限。

满射函数计数的本质，是从所有 m 个礼物到 n 个朋友的函数总数 nᵐ 中，剔除掉那些“至少有一位朋友没有收到礼物”的情况。令 Eᵢ 表示“第 i 位朋友没收到任何礼物”这一坏事件。用容斥原理，逐个排除坏事件，得到：

主办者看着这个公式，回想起自己从“两份名单”一路走到“分礼物”的历程。容斥原理的本质始终如一：从一个“粗略的全体”出发，用交替加减的方式，精确剥离掉所有不需要的情况，直到每一个细节都恰到好处。

应用与编程

容斥原理从派对名单中诞生，却绝不止于派对。在计算机科学里，它到处“兼职”：数据库查询中统计满足多个条件之一的行数时，可以用容斥原理去重；概率论中计算多个事件至少一个发生的概率时，同样可以套用容斥的框架；而欧拉函数更是 RSA 加密算法中密钥生成的核心步骤。主办者把记账经验写成代码，就是希望让计算机也学会这种“先加后减”的智慧。

编程实现容斥原理最直接的方式，是用二进制枚举所有非空子集。比如对于 n 个集合，用一个整数的二进制位表示“选择了哪些集合”，然后按奇偶符号累加交集大小。这是一个广泛应用于算法竞赛、数据去重和概率模拟的可复用套路：

派对主办者终于释然：无论是手动记账还是编写程序，容斥原理的思想始终如一——先把所有可能都纳入，再一重重减去重复，最后把减过头的救回来。这就是“计数不漏”的终极心法。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-"""容斥原理演示：1. 通用并集大小计算（二进制枚举子集）2. 错排数 D_n 计算3. 欧拉函数 phi(n) 计算"""from math import gcd, prod  def union_size_intersection(func_intersection, n):    """通用容斥原理：并集大小 = 交替加减所有子集交集大小    func_intersection(mask) 返回下标集合 mask 的交集大小    """    total = 0    for mask in range(1, 1 << n):        bits = bin(mask).count("1")        inter = func_intersection(mask)        if bits % 2 == 1:            total += inter        else:            total -= inter    return total  def derangement(n):    """错排数：D_n = n! * sum_{k=0}^{n} (-1)^k / k!"""    fact = 1    for i in range(2, n + 1):        fact *= i    d = 0    for k in range(n + 1):        term = fact        for i in range(2, k + 1):            term //= i        d += term if k % 2 == 0 else -term    return d  def euler_phi(n):    """欧拉函数 phi(n)：与 n 互素的正整数个数    使用容斥原理: phi(n) = n * prod(1 - 1/p)    """    result = n    temp = n    p = 2    while p * p <= temp:        if temp % p == 0:            while temp % p == 0:                temp //= p            result -= result // p        p += 1    if temp > 1:        result -= result // temp    return result  def disjoint_union_example():    """用具体集合验证容斥原理（数字集合）"""    A = {1, 2, 3, 4, 5}    B = {4, 5, 6, 7}    C = {5, 7, 8, 9}    union = A | B | C    # 手工套用容斥公式    calc = len(A) + len(B) + len(C) \        - len(A & B) - len(A & C) - len(B & C) \        + len(A & B & C)    print("实际并集大小:", len(union))    print("容斥计算并集:", calc)    assert len(union) == calc  if __name__ == "__main__":    # 直观验证    disjoint_union_example()     # 错排数    for n in range(1, 8):        print(f"D_{n} = {derangement(n)}")     # 欧拉函数    for n in [6, 12, 15, 30]:        print(f"phi({n}) = {euler_phi(n)}")        # 暴力验证互素个数        brute = sum(1 for x in range(1, n + 1) if gcd(x, n) == 1)        assert brute == euler_phi(n)    print("所有断言通过，容斥原理实现正确！")

1. for mask in range(1, 1 << n):用二进制枚举所有非空子集，mask 的每一位代表是否选择对应集合。
2. if bits % 2 == 1: total += inter奇数个集合取正号，偶数个取负号，这就是容斥的“交替加减”。
3. fact预计算 n!，后续每一项都从它出发除以 k!，避免浮点误差。
4. result -= result // p等价于 result *= (1 - 1/p)，用整数运算消除分数，是容斥在欧拉函数中的实现。
5. while p * p <= temp:只需遍历到 sqrt(n) 即可提取所有质因子，体现算法效率。
6. assert len(union) == calc用实际集合的并集验证容斥公式计算正确。

常见误区

面试题