容斥原理

并集按层变号#

两个集合是整条公式的第一层，也是最容易被当成全部内容的一层。有限集合的并，等于两个基数相加，再减去交：

$$|A\cup B|=|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|.$$

一般情形是同一句话。设 $A_1,\ldots,A_n$ 有限。并集的基数等于各单集之和，减去两两交，加回三重交，此后每一层继续变号。恰由 $k$ 个集合作成的交，符号是 $(-1)^{k+1}$。$k=1$ 时符号为正，$k=2$ 时为负，$k=3$ 时又为正。写成一层一层的和，就是

$$\left|\bigcup_{i=1}^{n}A_i\right|=\sum_{k=1}^{n}(-1)^{k+1}\sum_{1\le i_1<\cdots<i_k\le n}\bigl|A_{i_1}\cap\cdots\cap A_{i_k}\bigr|.$$

$k$ 跑到 $n$ 时，最后一项只剩全体的交，符号 $(-1)^{n+1}$。少写任何一层，一般就不再是这个基数。集合必须有限，基数才是普通的非负整数。下面的指示函数不要求先把元素排成一张可以逐行打勾的表。

内层求和的下标写成严格递增，是为了每一组集合只出现一次。$k$ 个集合若按有序下标跑遍所有不同的取法，同一组交会进入 $k!$ 次。那时右边必须再除以 $k!$，才和现在这条基数相同。省略号省去的是更高的层，不是把同一层按不同次序再加几遍。

两个集合先算完#

指示函数 $1_A(x)$ 在 $x$ 属于 $A$ 时取 $1$，否则取 $0$。有限集合的基数，就是把这个函数在论域上加起来。两个集合时，展开式给 $x$ 的次数是

$$1_A(x)+1_B(x)-1_{A\cap B}(x).$$

四种归属都要写完。$x$ 不在 $A$ 也不在 $B$：三项都是 $0$，次数是 $0$。只在 $A$：第一项是 $1$，后两项是 $0$，次数是 $1$。只在 $B$：同样得到 $1$。同时在 $A$ 和 $B$：交的指示函数也是 $1$，于是 $1+1-1=1$。次数等于 $1$，恰好在 $x$ 属于并集的时候。不属于并集的时候，次数是 $0$。所以这个带号和就是 $1_{A\cup B}$，不是一个近似。

两边对论域求和，左边加出 $|A\cup B|$，右边加出 $|A|+|B|-|A\cap B|$。少减那一项，同时属于两边的元素会被数成 $2$。把交再减一次，它又会被数成 $0$。两种改法都不再等于并集的指示函数，求和以后也不再等于并集的基数。两个集合的公式到这里结束。它是整条原理在 $n=2$ 时的全部，不是一条只许有两个集合的特殊窍门。

交并没有另一套指示函数。$x$ 属于 $A\cap B$，当且仅当它既属于 $A$ 也属于 $B$，所以 $1_{A\cap B}(x)$ 就是两个指示函数的乘积。带号和因此可以写成 $1-(1-1_A(x))(1-1_B(x))$。把右边乘开，得到 $1$ 减去两个单集、再加上乘积项。与前面那个 $1$ 相减，剩下的仍是 $1_A+1_B-1_{A\cap B}$。下一节只是把括号从一个增加到 $n$。负号在两个集合时已经出现，不是等集合变多以后才临时规定的。

一般项的符号从哪里来#

更多集合时，仍旧先看每个 $x$ 被数了几次，而不是先去枚举并集里的元素。$x$ 不属于任何一个 $A_i$，当且仅当每个因子 $1-1_{A_i}(x)$ 都等于 $1$，这些因子的乘积等于 $1$。只要 $x$ 属于至少一个集合，对应的那个因子就是 $0$，乘积就是 $0$。因此并集的指示函数可以写成

$$1_{\bigcup_i A_i}(x)=1-\prod_{i=1}^{n}\bigl(1-1_{A_i}(x)\bigr).$$

这是每个 $x$ 上的数值恒等式。把乘积按子集展开。选定子集 $S$，属于 $S$ 的每个集合贡献一个 $-1_{A_i}$，不属于 $S$ 的集合贡献 $1$。这一项等于 $(-1)^{|S|}$ 乘上 $S$ 中那些集合之交的指示函数。空集的项是 $1$，因为空的乘积按约定是 $1$，而且空交可以看成整个论域。前面的 $1$ 与这项相减，空集消去。非空的 $S$ 还要再承受这个减号，符号从 $(-1)^{|S|}$ 变成 $(-1)^{|S|+1}$。令 $k=|S|$，一般项的符号就是 $(-1)^{k+1}$。

符号不是在两个集合的公式后面临时添上的口诀。两个集合恰好是这个展开的短形式：单集对应 $|S|=1$，符号为正。两集合之交对应 $|S|=2$，符号为负。没有第三层，所以看不到加回来的那一项。三个集合时，三重交对应 $|S|=3$，符号是 $(-1)^{3+1}=1$，于是加回来。层数增加，变号的理由不变。

把同一恒等式读成次数。$x$ 若不属于任何集合，每个非空交的指示函数都是 $0$，次数是 $0$。$x$ 若恰好属于其中 $r$ 个集合，而且 $r\ge 1$，那么只有从这 $r$ 个里取出来的交才会把它算进去。取出 $k$ 个，有 $\binom{r}{k}$ 种，每种的符号是 $(-1)^{k+1}$。次数等于

$$\sum_{k=1}^{r}(-1)^{k+1}\binom{r}{k}.$$

二项式定理用在 $1$ 与 $-1$ 上：$(1-1)^r=\sum_{k=0}^{r}\binom{r}{k}(-1)^k$。$r\ge 1$ 时左边是 $0$。其中 $k=0$ 的项是 $1$，所以从 $k=1$ 起的那些项加起来等于 $-1$。每一项再变一次号，和就等于 $1$。因此次数等于 $1$，当且仅当 $x$ 至少属于一个集合。$r=1$ 时和就是 $1$。$r=2$ 时是 $2-1=1$。$r=3$ 时是 $3-3+1=1$。这三行就是两个集合、以及三个集合那两条公式在一个元素上的样子。对论域求和，左边是并集的基数，右边是各层交的基数配上同样的符号。论域比并集大也没有关系，多出来的元素贡献 $0$。

把基数换成概率，并不产生第二条原理。有限论域里若每个元素等可能，概率就是基数除以论域的大小。带号求和的两边除以同一个正整数，符号不变。元素并不等可能时，逐点恒等式仍然先成立。再对两边取同一个测度，等号还在，因为两边在每个样本点上已经相等。权重大小不改变这个逐点的 $0$ 或 $1$。因此并集的概率等于各层交的概率配上同样的符号。这一步不代替概率页上的极限定理，也不把错排比例的极限写成有限排列上的概率。

三十与十五#

$1$ 到 $30$ 里能被 $2$ 或 $3$ 整除的数，就是两个集合的并。设 $A$ 是其中 $2$ 的倍数，$B$ 是 $3$ 的倍数。$1$ 到 $N$ 里 $m$ 的倍数有 $\lfloor N/m\rfloor$ 个。这里 $N=30$，而 $2$、$3$、$6$ 都整除 $30$，所以下取整与普通的商重合：

$$\lfloor 30/2\rfloor+\lfloor 30/3\rfloor-\lfloor 30/6\rfloor=15+10-5=20.$$

减掉的五个数是 $6$、$12$、$18$、$24$、$30$。$6$ 同时属于 $A$ 和 $B$，次数是 $1+1-1=1$，不是 $2$。$2$ 只属于 $A$，次数是 $1$。$15$ 只属于 $B$，次数是 $1$。$1$ 两个集合都不属于，次数是 $0$，不进入这 $20$。不把这二十个数逐个抄出来，因为带号和已经把重复的那五个只留了一次。$15+10=25$ 是只加单集、还没减去交的数，它不是并集的基数。这里的或是并集，五个交里的数都算。若把或听成恰好被其中一个整除，交要减两次，得到 $15+10-10=15$。那是只属于一个集合的个数。并集比它多出的，正是 $6$、$12$、$18$、$24$、$30$。它们被减去一次以后仍然留在并里。

另一个计数是补集，仍然用的是两个集合。设 $p$ 与 $q$ 是不同的素数。$1$ 到 $pq$ 里与 $pq$ 互素，就是既不被 $p$ 整除、也不被 $q$ 整除。令 $U$ 是这 $pq$ 个数，$A$ 是其中 $p$ 的倍数，$B$ 是 $q$ 的倍数。补集的基数是 $|U|-|A\cup B|$。把已经证完的两个集合公式代进去，减号后面的交要变号，得到

$$|U|-|A|-|B|+|A\cap B|=pq-\lfloor pq/p\rfloor-\lfloor pq/q\rfloor+\lfloor pq/(pq)\rfloor.$$

$p$ 整除 $pq$，所以 $\lfloor pq/p\rfloor=q$。同样 $\lfloor pq/q\rfloor=p$，而 $\lfloor pq/(pq)\rfloor=1$。$p=3$、$q=5$ 时，$pq=15$，式子变成 $15-5-3+1=8$。这八个数是 $1$、$2$、$4$、$7$、$8$、$11$、$13$、$14$。$15$ 自己被 $3$ 和 $5$ 整除，不在里面。$1$ 与 $15$ 的最大公因数是 $1$，要算进去。最后的加一，不是把 $15$ 当成与自己互素。它在总数里出现一次，又作为 $3$ 的倍数和 $5$ 的倍数各被减一次。若不加回，它被减了两次，剩下 $7$。加回以后，次数是 $1-1-1+1=0$，于是被排除。其余互素的数仍各算一次，一共是 $8$。加号恢复的是被减多的那一次。

欧拉定理页已经写过 $\varphi(15)=8$，也写过两个不同素数时，互素剩余有 $(p-1)(q-1)$ 个。$3$ 与 $5$ 给出 $2\times 4=8$，与这里的 $8$ 是同一个数。本页这一步只是容斥在数数。那一页拥有的是互素幂次同余：底数与模互素时，底数的欧拉函数次幂在模下回到一。同余问的是一个已经互素的底数，乘够那么多次会不会回到一。计数问的是这样的剩余一共有几个。两句都碰到 $15$ 和 $8$，不能互相代替。这里不把两个素数的这个计数推广成反演公式。

错排只推导一次#

$n$ 个不同元素的排列一共 $n!$ 个。令 $A_i$ 是第 $i$ 个位置仍然放着 $i$ 的那些排列。$|A_i|=(n-1)!$，因为其余位置可以任意排。指定 $k$ 个不同的位置都被固定时，剩下 $n-k$ 个位置任意排，个数是 $(n-k)!$。哪 $k$ 个位置被指定，有 $\binom{n}{k}$ 种。这些交的大小只依赖 $k$，不依赖具体是哪些下标。

全错排是不落在任何一个 $A_i$ 里的排列。它的个数 $D_n$ 是排列总数减去并集的个数。并集用上面的带号求和：

$$\left|\bigcup_{i=1}^{n}A_i\right|=\sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}(n-k)!.$$

于是错排个数等于排列总数减去上面这个并集，也就是 $n!-\sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}(n-k)!$。组合数的定义把每一层收成 $n!/k!$。减去并集时，原来的符号再变一次，从 $k=1$ 起的系数成为 $(-1)^k$。还要补上 $k=0$ 的项。它等于 $1$，因为 $0!=1$。这一项就是还没有扣掉任何固定位置时的全部排列。合在一起，

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

$n=4$ 时可以用两条算术互相核对，不必把 $24$ 个排列逐个划掉。第一条走交的个数。$\binom{4}{1}\cdot 3!=24$，$\binom{4}{2}\cdot 2!=12$，$\binom{4}{3}\cdot 1!=4$，$\binom{4}{4}\cdot 0!=1$。并集是 $24-12+4-1=15$。错排是 $24-15=9$。第二条走上面的和。公分母取 $24$：$1-1+1/2-1/6+1/24=(24-24+12-4+1)/24=9/24$。再乘 $4!=24$，仍得 $9$。所以 $D_4=9$。两条路用的是同一个带号求和，不是两个彼此独立的定义。

比 $4$ 更小的 $n$ 可以用来核对，这仍然不是另起一次推导。$n=2$ 时，$2!\bigl(1-1+1/2\bigr)=1$，比例是 $1/2$。两个元素的错排只有互相交换这一种。$n=3$ 时，$6\bigl(1-1+1/2-1/6\bigr)=2$，比例是 $1/3$。三个元素按两个方向轮换，得到的两个排列都不固定任何位置。其余排列至少固定一处。$1/2$、$1/3$ 和 $9/24$ 都不是 $1/e$。总览说的是 $n$ 增大以后靠近，不是这几个有限的比已经等于那个常数。

总览已经写了 $D_n/n!$ 随 $n$ 增大逼近 $1/e$。本页只把界线画清楚：有限的 $n$ 把和停在 $k=n$，后面的项还没有进入这个比，所以 $D_n/n!$ 不是 $1/e$。$n=4$ 时这个比是 $9/24$。总览用帽子把全错排说成每人都不拿回自己的那一顶，也就是任何一个 $A_i$ 都不发生。图像留在总览，推导停在这一次。

截断一般不再是等式#

只加到某一层，意思是 $k$ 的和在某个 $m<n$ 处停住，后面的交即使不是空的也不再写入。一个恰好属于 $r$ 个集合的元素，次数变成 $\sum_{k=1}^{\min(m,r)}(-1)^{k+1}\binom{r}{k}$。$r>m$ 时，二项式和没有加完，次数不必是 $1$。对所有元素加起来，得到的数就不必等于并集的基数。所以截断一般是不等式，不是本页这条等式。更高层的交若恰好全是空的，被丢掉的项本来就是 $0$，截断会碰巧仍等于并集。两个集合的公式减到两两交为止，那是最后一层，不是半路停下。

用 $1$ 到 $30$ 里能被 $2$、$3$ 或 $5$ 整除的数看一次。单集是 $\lfloor 30/2\rfloor=15$，$\lfloor 30/3\rfloor=10$，$\lfloor 30/5\rfloor=6$，加起来是 $31$。两两交是 $\lfloor 30/6\rfloor=5$，$\lfloor 30/10\rfloor=3$，$\lfloor 30/15\rfloor=2$，和为 $10$。三重交是 $\lfloor 30/30\rfloor=1$。三层都写上，是 $31-10+1=22$。只留单集，得到 $31$，不是 $22$。单集再减去两两交，得到 $21$，也不是 $22$。

$30$ 同时属于三个集合。只加单集时它被数了三次。减去三对两两交以后，次数是 $3-3=0$。并集仍应把它数一次，所以还要加回三重交。少了这一步，$21$ 比 $22$ 少的那一个，就是这个元素还没被加回来。恰好属于一个或两个集合的元素，在减完两两交时次数已经是 $1$，它们不是这个差额的来源。文献里把只保留前若干层时所得到的那一族不等式叫作 Bonferroni 不等式。这个名字指的是界，不是本页这条等式。本页不证明那族界的一般方向，也不给它编页码。这里只需要看见，$31$ 和 $21$ 都不是 $22$。等式要求每一层都在，或者被略去的层确实是空的。

名字与算术版本都停在界外#

数论页把 Möbius 函数称作容斥的算术版本，并说反演公式是数论中的容斥。本页承认这句分工。正整数的因子上那种变号，和这里按集合交的重数变号，是同一类抵消的两种标签。反演公式本身不在这里重证，也不把 $\varphi$ 的一般乘积式从反演里推出来。两个互异素数上的那一次减法，已经是本页需要的全部算术例子。

带号求和在不同讲义里会被安到不同的人身上。de Moivre 与 Sylvester 都曾出现在这条公式旁边。本页不指定单一发现者，因此不设 mathematician，也不设 year，也不给这两个名字编页码。欧拉的名字会出现，是因为欧拉函数页已经把 $\varphi(15)=8$ 写下来，本页的计数要与那个数对齐。对齐的是个数，不是把这条原理记成他一个人的发现。顶点减棱加面那种交错和，加的是三种几何计数，不是同一批集合按交的层数变号。它不是本页的公式。

跨域连接#

• 组合数学：总览已经把并集写成带号求和，把错排写成 $D_n=n!\sum_{k=0}^{n}(-1)^k/k!$，并写明 $D_n/n!$ 随 $n$ 增大逼近 $1/e$。那些句子是本页的起点。总览紧接着把筛法、错排、覆盖和若干数论恒等式收成同一类加减，又把鸽巢、二项式系数和 Ramsey 式的存在陈述放在别的小节。本页不把那段应用散文再写一遍，也不用并集的基数去代替「足够大就一定出现某种子结构」。留在这里的是指示函数：每个元素被数到的次数为何是 $1$，以及 $30$、$15$ 和 $4$ 这三处核对。总览里容斥对上 Möbius 的那一行只是口号。反演不在这里重证。截到半路得到的不等式也不是总览那一行等式。
• 概率论：概率页把概率定义成事件上的测度，并讨论大数定律和中心极限定理。那些不是本页。并集的概率和基数用同一套符号，是因为概率读的是指示函数：在有限而且等可能的样本空间里，只是把基数等式两边除以样本点的个数。样本点并不等可能时，仍是对同一个逐点恒等式取测度，不是另找一条加减口诀。错排比例只有在全体排列上取均匀测度时才是一个概率。$n=4$ 时这个概率是 $9/24$，不是 $1/e$。逼近已经写在总览里。有限排列上的精确值仍是求和停在 $n$ 的那一条，不是把后来才靠近的数提前写成每一个 $n$ 的值。
• 数论：数论页把 Euler 函数和 Möbius 函数对列，写明后者是容斥的算术版本，反演公式是数论里的容斥。本页使用这句分工，但不把反演的两边再推一遍，也不把因子上的函数逐个改写成集合。两个互异素数上，$1$ 到乘积之中与乘积互素的个数，是补集的带号计数。$15-5-3+1=8$，与欧拉函数在 $15$ 处的值一致。一般的乘积式留在那一页。本页的符号只对集合的交变号。把正整数的全部因子都配上符号，已经越出这条并集等式的证明。
• 欧拉定理：那一页的陈述是，底数与模互素时，底数的欧拉函数次幂在模下回到一。它也直接数过两个不同素数的乘积：被每个素数整除的个数减去同时被两个整除的个数，剩下的与乘积互素，$3$ 与 $5$ 时得到 $8$，与 $\varphi(15)=8$ 一致。本页把这个 $8$ 写成 $15-5-3+1$，说明它是容斥在数数。那一页拥有的是互素幂次同余，不是这条计数。同余问一个互素底数乘够函数值那么多次会不会回到一。计数问这样的剩余一共有几个。两边都用到 $15$ 和 $8$。读幂次的时候离开本页，读交的符号的时候不必回到那条同余。

参考文献#

• Stanley, Richard. Enumerative Combinatorics. 两卷，1997 与 2001。总览已列此书。本页用它作带号求和的课程来源，不编定理号。
• Van Lint & Wilson. A Course in Combinatorics. 第二版，2001。总览已列此书。本页同样不编页码。