inclusion–exclusion · 交错加减

容斥原理

加法原理的前提是各类互斥。一旦两类之间有共同的方案，直接相加会把交集里的东西数两遍，减掉一次就得到最小的修正式 $|A \cup B| = |A| + |B| - |A \cap B|$ 。把这套记账推广到 $n$ 个集合，即容斥原理（inclusion–exclusion）：奇数个集合的交加进来，偶数个集合的交减出去，一共 $2^n - 1$ 项。

1 · 相交时的重复计数

两个集合时 $|A| + |B|$ 把 $A \cap B$ 里的元素各数了两遍，减去一次即可。三个集合时先减掉三个两两交，但落在三重交里的元素原本被加过三次、又被减了三次，净计零次，须再加回一次：

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

两条计数原理 §2 的加法原理是它在各交集皆空时的特例，基数：有限、可数无限与不可数 §1 只做到两集合的版本。

2 · 一般式的逐项展开

2ⁿ − 1 项 · 奇加偶减

把下标集 $\{1, \dots, n\}$ 的全部非空子集 $S$ 各出一项，符号由 $|S|$ 的奇偶决定：

\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \neq S \subseteq \{1, \dots, n\}} (-1)^{|S|+1} \left|\bigcap_{i \in S} A_i\right|

项数 $2^n - 1$ 增长得很快： $n = 4$ 是 15 项， $n = 10$ 是 1023 项， $n = 20$ 已超过一百万。式子本身不挑 $n$ ，能否落地取决于各个交集是否比原集合更好算——整除、互素这类条件下交集仍是同一形状的集合，容斥才划算。

图 2-1 · 1 到

N

中被 2、3、5、7 整除的数的容斥展开。可调上界

N

与除数个数

n

观察

2^n-1

项如何交错累加，单击某一项高亮它数到的元素。

$N = 120$ 、除数取 $2, 3, 5$ 时，三个单集合各有 60、40、24 个元素，三个两两交是 20、12、8，三重交是 4，交错加减得 88。三个除数正是 120 的全部不同素因子，落在并集之外的 $120 - 88 = 32$ 个数与 120 互素，也就是欧拉函数 $\varphi(120) = 32$ 。

3 · 交错系数的抵消

Σ (−1)ᵏ⁺¹ C(m, k) = 1

一般式成立与否，逐个元素核账即可。

证明设某元素恰属于其中 $m$ 个集合（ $m \ge 1$ ）。它出现在这 $m$ 个下标的每一个非空子集所对应的交里，大小为 $k$ 的子集共 $\binom{m}{k}$ 个，各带符号 $(-1)^{k+1}$ ，其余的项都不含它。它被计的总次数是

\sum_{k=1}^{m} (-1)^{k+1} \binom{m}{k} = 1 - \sum_{k=0}^{m} (-1)^{k} \binom{m}{k} = 1 - (1-1)^m = 1

中间一步取Pascal 三角与二项式定理的展开式在 $x = -1$ 处的值。不属于任何 $A_i$ 的元素在每一项里都缺席，计零次。于是并集内的元素各净计一次、并集外的各计零次，右端就是并集的大小。∎

图 3-1 · 恰属于

m

个集合的元素在各层被计的带号次数。可调

m

观察部分和如何在正负之间振荡，最终收在 1。

4 · 满射的容斥计数

从 $n$ 元集到 $m$ 元集的映射共 $m^n$ 个，其中满射（surjection）要求每个像点都被取到。取 $A_i$ 为「漏掉第 $i$ 个像点」的那些映射，则 $|A_i| = (m-1)^n$ ，而 $k$ 个这样的集合求交就是把像集砍到 $m - k$ 个点，大小 $(m-k)^n$ ，与漏掉的是哪 $k$ 个无关。全体减去坏映射的并：

\sum_{k=0}^{m} (-1)^{k} \binom{m}{k} (m-k)^n

它除以 $m!$ 即第二类 Stirling 数 $S(n, m)$ ——像点若不可辨，就只剩下把 $n$ 个元素划成 $m$ 个非空块的方式数。把「像点」换成「原位」，同一套记账给出错排的公式。

警示 · 交错求和的中间项可以远大于结果，双精度会在结果尚未溢出时就先失准。combinatorics/core/inclusion.ts 里的 surjections 按上式用 number 逐项累加，与 BigInt 精确式逐格对照，首次出错在 $n = 15$ 、 $m = 11$ ：精确值 59056027430400，浮点式给出 59056027430401。此处最大的一项 $\binom{11}{1} \cdot 10^{15} \approx 1.13 \times 10^{16}$ 已越过 Number.MAX_SAFE_INTEGER，而结果本身要到 $n = 17$ 才越线。同一个 $m$ 下，「算错」比「装不下」早整整两档。

5 · 参考文献

Inclusion–exclusion principle. Wikipedia. 容斥原理的一般式、几种证明与在计数中的典型应用。https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
Surjective function. Wikipedia. 满射的定义与满射数的容斥表达。https://en.wikipedia.org/wiki/Surjective_function
Euler's totient function. Wikipedia. 欧拉函数按不同素因子做容斥的算法。https://en.wikipedia.org/wiki/Euler%27s_totient_function