若一个对象可以同时违反多个条件,分别减去每个坏集合时,它便会被减去多次。容斥原理通过追踪单个对象的贡献来修正,而不依赖只有特定区域数目的图。
计算用尽所有标签的分配
定义 1.1.1
(满射分配)
从任务集合到标签集合的函数,若每个标签都至少被一个任务使用,就称为满射。
例题 1.1.2
(四个任务与三个标签)
四个互异任务各分配三个互异标签之一,有多少种分配用尽三个标签?不加限制共有 种。令 为完全没有使用第 个标签的分配,。答案是 的补集大小。
每个 有 个元素;任意两集合的交集只有一种分配,即所有任务使用剩下的标签。三者交集为空:四个任务不可能在没有任何可用标签时完成分配。因此
这里 ,无须约定 。任务与标签均可区分:改变哪个任务取得某标签,或交换两个标签,均得到不同分配。
一般公式与边界情况
定理 1.1.3
(满射数目的交替和)
对 个互异任务及 个互异标签,从任务集合到标签集合的满射数目是
若 ,此数为零。
证明
(每个函数贡献一次或零次)
对标签集合 ,令 为完全不使用 中任何标签的函数集合。若 ,每个任务可取其余 个标签之一,故 。对全部 个大小为 的 求和,就得到第 项 ,整个式子就是 。
现在固定一个函数,设它没有使用的标签共有 个。它属于 ,当且仅当 包含于这 个未使用的标签之中;大小为 的这类 共有 个。若 ,只有 符合,该函数恰好贡献 。若 ,它的总贡献为
因此,这个和对每个满射恰好计一次,对其他函数计零次,即使多个坏集合互相重叠也是如此。若 ,答案为零有直接的理由:每个任务最多提供一个标签,不可能出现全部 个标签。即使公式中的个别项不为零,其总和仍须与这个论证一致。
证明透视
为何修正不能止于两两交集
这个证明把计数由集合改为逐一检视对象:不去度量交集的大小,而是问同一个函数被计算了多少次,答案由二项式定理给出 。交替和的每一项都在修正前面各项。过早停止一般是错的:恰好缺少三个标签的函数,在两两交集项之后的贡献为 ,即它虽然不是满射仍会被计算。在四个任务、三个标签的例子中,没有函数缺少三个标签,所以最后一项为零;有四个或更多标签时,这一项不能省略。
例题 1.1.4
(任务少于标签)
取 个任务及 个标签。和为 。大部分项并不为零,但总和与直接论证一致:两个任务不可能用尽三个标签。
例题 1.1.5
(五个任务与四个标签)
和为 。直接验算:恰有一个标签被使用两次,故先选出共用同一标签的两个任务,有 种;再把四个标签一一分配给所得的四组任务,有 种;。
常见错误
(不可只减去单一标签缺失)
太小。只使用标签 1 的分配同时缺少标签 2 和 3,因此被减去两次。三个两两交集各补回一个分配,得到 。若把整个修正项的正负号反转,或把标签视为不可区分,便是在计算另一个问题。
练习
快速检查
(由 构成的长度三字符串中,有多少个使用全部三种符号?)
解答 · 答案
每个符号恰出现一次,故有 个;容斥也给出 。
快速检查
(从两元素集合到三元素集合有多少个满射?不用交替和解释。)
解答 · 答案
零个:两个输入无法产生三个不同输出。
快速检查
(四个互异任务分配两个互异标签,有多少种分配使用两个标签?)
解答 · 答案
共有 种;排除两种常值分配,余 种。