容斥、递推计数与错排

重复计数与状态递推分别解决“类别重叠”和“规模增长”两个常见困难。

类别重叠时为什么需要容斥

若两个有限集合有共同元素，直接相加 $|A|+|B|$ 会把交集中的元素数两次；减去一次 $|A\cap B|$ 后，每个并集元素才恰被计数一次。多个集合时，不同元素的重复次数可能不同，须逐层加减交集，而不能统一除以某个“重复次数”。

使用时先定义待统计集合或需要排除的坏事件，再确定每类交集的含义与大小。下一节列出二集、三集及一般公式；随后用错排说明“指定若干条件成立”如何参与容斥。

以下集合均有限。完整公式为

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

\begin{aligned} |A\cup B\cup C| ={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|. \end{aligned}

一般地，对 $n\ge1$ ，

\left|\bigcup_{i=1}^n A_i\right| =\sum_{\varnothing\ne I\subseteq\{1,\ldots,n\}} (-1)^{|I|+1}\left|\bigcap_{i\in I}A_i\right|.

即先加所有单集基数，减所有两两交，再加所有三重交，依此交替，最后一项符号为 $(-1)^{n+1}$ ，也等于 $(-1)^{n-1}$ 。

逐元素证明。 若某元素在 $k\ge1$ 个集合中，它在右侧被计入

\binom k1-\binom k2+\cdots+(-1)^{k+1}\binom kk=1

次；这是 $(1-1)^k=0$ 移去常数项后的结果。不在任何集合中的元素被计零次。所以右侧恰好对并集每个元素计一次。

例一：排除若干整除条件。 $1$ 至 $100$ 中被 $2,3,5$ 至少一者整除的个数为

50+33+20-16-10-6+3=74.

故三者都不能整除的有 $100-74=26$ 个。两条件的交用最小公倍数计，不是任意把除数相乘。

例二：每个符号至少出现一次。 长为 $n\ge1$ 的三符号串共有 $3^n$ 个，缺某个符号有 $2^n$ 个，缺指定两个符号有 $1$ 个。容斥得

3^n-3\cdot2^n+3.

对 $n=1,2$ 结果为零，符合无法容纳三个不同符号；若符号包括数字零且统计的是整数，还须另处理首位不能为零。

$n$ 个对象均不放回原位置的排列数 $D_n$ 可由容斥得到

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

固定指定的 $k$ 个位置后其余有 $(n-k)!$ 种；乘上选位置数 $\binom nk$ 并交替求和即得。比如 $D_3=6-6+3-1=2$ 。本式是有限和，不使用无穷级数。

令 $D_0=1,D_1=0$ 。对 $n\ge2$ ，先将对象 $n$ 放在位置 $i\ne n$ ，有 $n-1$ 种选择。

若对象 $i$ 放在位置 $n$ ，其余形成 $n-2$ 个对象的错排；否则，把位置 $n$ 的标签改为 $i$ ，剩余排列与 $n-1$ 个对象的错排一一对应。因此

D_n=(n-1)(D_{n-1}+D_{n-2}).

得到 $D_2=1,D_3=2,D_4=9,D_5=44$ ，与容斥公式一致。容斥中的 $\binom nk(n-k)!$ 数的是“指定的 $k$ 个位置固定”，允许其他位置也固定；它不是“恰好 $k$ 个位置固定”的数量。混淆这两个对象会破坏容斥的逻辑。

记长度 $n$ 的二进制串中不含相邻两个 $1$ 的数量为 $a_n$ 。末位为 $0$ 时可接在任意合法长度 $n-1$ 串后；末位为 $1$ 且 $n\ge2$ 时末两位必须是 $01$ ，前面可取任意合法长度 $n-2$ 串。

因此 $a_n=a_{n-1}+a_{n-2}$ ，初值 $a_0=1$ （空串）， $a_1=2$ 。依次得到 $a_2=3,a_3=5,a_4=8$ 。

$n$ 条直线将平面分成的区域数至多为

L_n=1+n+\binom n2.

加入第 $n$ 条直线时，它与已有直线有至多 $n-1$ 个不同交点，故被分成至多 $n$ 段，每段至多增加一个区域。于是 $L_n=L_{n-1}+n,L_0=1$ 。无平行、无三线共点时可以同时取到这些上界。

类似地， $n$ 个平面将空间分成的区域数至多为

P_n=1+n+\binom n2+\binom n3.

新平面与已有平面的交线在新平面上形成至多 $L_{n-1}$ 块，每块至多增加一个空间区域。因此 $P_n=P_{n-1}+L_{n-1},P_0=1$ 。选择一般位置的平面可取到上界；平行、多个交线共点等退化可能减小区域数。上述公式是最大可能值，不能直接用于任意指定的多面体面平面。

设圆环上有 $n\ge3$ 个有编号的位置，用 $k\ge2$ 种颜色染色，相邻位置异色，旋转后编号改变视为不同方案。记方案数为 $a_n$ 。

先染一条含 $n$ 个位置的链，有 $k(k-1)^{n-1}$ 种。首尾异色的恰是 $a_n$ ；首尾同色的将两端合并，得到 $a_{n-1}$ 。对 $n\ge4$ 有

a_n+a_{n-1}=k(k-1)^{n-1}.

由 $a_3=k(k-1)(k-2)$ 归纳得

a_n=(k-1)^n+(-1)^n(k-1).

若还有一个与外圈所有位置相邻的中心，先选中心颜色，再用其余 $k-1$ 色染环，得到

k\bigl[(k-2)^n+(-1)^n(k-2)\bigr].

例如三色染四环有 $2^4+2=18$ 种；加上中心后有 $3(1+1)=6$ 种。若旋转等同，不能直接使用这些答案，也不能不检查对称性就除以 $n$ 。

求 $1\le a\le b\le100$ 且 $57$ 整除 $ab$ 的整数对数。因为 $57=3\cdot19$ ，且 $3,19$ 为不同素数，条件等价于乘积同时含因子 $3$ 和 $19$ 。

先允许 $(a,b)$ 有序。至少一个数被 $19$ 整除的有 $100^2-95^2=975$ 对。扣去其中两个数都不被 $3$ 整除的：不被3整除的数有67个，其中被19整除的有4个（19,38,76,95），所以应扣 $67^2-63^2=520$ 对。合格有序对共有 $455$ 对。

非对角 $(a,b)$ 与 $(b,a)$ 两两配对；对角 $a=b$ 要 $57\mid a^2$ ，在范围内只有 $a=57$ 。所以 $a\le b$ 的个数为

\frac{455-1}{2}+1=228.

这里没有直接把455除以二，因为对角元素在交换下只有一个表示。遇到交换对称的计数，先区分固定点与二元组。