基本形式

两个集合

对于有限集合 A, B，有 |A ∪ B| = |A| + |B| − |A ∩ B|

三个集合

对于有限集合 A, B, C，有 |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

一般形式

对于有限集合 A1, A2, …, An，有

也可以写成

证明

证明

考虑任意一个元素 ，设 x 恰好属于 Ai1, Ai2, …, Aim（m ≥ 1）。

在左边，x 被计数了 1 次。

在右边，x 被计数的次数为 由二项式定理可知 故 因此每个元素在右边也恰好被计数 1 次，左右两边相等。

证毕。

补集形式

在实际应用中，正面计算 往往不太方便。更常见的是已知全集 U，通过容斥原理求不属于任何一个 Ai 的元素个数。

展开即得

其中 S = ⌀ 时 |⋂i ∈ SAi| = |U|。

这个形式又被称为容斥原理的对偶形式，在”至少”与”恰好”之间的转换中非常好用。

例题

不定方程非负整数解计数

例题：洛谷 P2167 [SDOI2009] Bill的挑战。

晚点写。

错排问题

问题描述

n 个元素的排列 {pn} 中，满足 ∀ i，pi ≠ i 的排列称为错排（或称全错位排列）。

设 Dn 为 n 个元素的错排数，求 Dn。

算法分析

令 Ai 表示满足 pi = i 的排列的集合，则错排就是不属于任何一个 Ai 的排列。

由容斥原理的补集形式

对于 |S| = k 的子集 S，|⋂i ∈ SAi| 表示固定 S 中的 k 个元素不动、其余 n − k 个元素任意排列的方案数，即 (n − k)!。

而 |S| = k 的子集有 个，所以

由此也可以得到递推式。

Dn = (n − 1)(Dn − 1 + Dn − 2)

证明

考虑第 n 个元素放在位置 k（k ≠ n），有 n − 1 种选法。

接下来分两种情况：

  • 若第 k 个元素放在位置 n（即 pk = n），那么剩余 n − 2 个元素要形成错排，方案数为 Dn − 2。
  • 若第 k 个元素不放在位置 n（即 pk ≠ n），等价于 n − 1 个元素（将位置 n “重编号”为位置 k）的错排，方案数为 Dn − 1。

故 Dn = (n − 1)(Dn − 1 + Dn − 2)。

证毕。

初始条件 D1 = 0，D2 = 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using lint = long long;
const int MOD = 1e9 + 7;

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  int n;
  std::cin >> n;
  std::vector<lint> D(n + 1);
  D[1] = 0, D[2] = 1;
  for (int i = 3; i <= n; ++i)
    D[i] = (i - 1) * (D[i - 1] + D[i - 2]) % MOD;
  std::cout << D[n] << '\n';
  return 0;
}

欧拉函数的容斥推导

φ(n) 表示 [1, n] 中与 n 互质的数的个数。利用容斥原理可以推导出 φ(n) 的计算公式。

设 ，令 Ai 表示 [1, n] 中 pi 的倍数的集合，则 。

与 n 互质的数就是不被 n 的任何质因子整除的数，即

由容斥原理

最后一步是因为

这与我们熟知的欧拉函数公式一致：

容斥原理与莫比乌斯函数

回顾莫比乌斯函数的性质 ∑d ∣ nμ(d) = [n = 1]，这实际上就是容斥原理在数论中的体现。

当我们将 [gcd (i, j) = 1] 替换为 ∑d ∣ gcd (i, j)μ(d) 时，本质上就是在做容斥： [gcd (i, j) = 1] = ∑d ∣ gcd (i, j)μ(d) 其中 μ(d) 的取值 {0, ±1} 恰好对应了容斥的系数。

这也是莫比乌斯反演能够成立的根本原因。