容斥、递推计数与错排

容斥原理：二集、三集与一般式

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

一般地，对 $n\ge1$，

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

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

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

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

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

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

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

直线与平面分割的递推

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

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

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

新平面与已有平面的交线在新平面上形成至多 $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_3=k(k-1)(k-2)$ 归纳得

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

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