容斥原理的基本形式

减法原理是容斥原理的最简单示例。

定理1 设 为集合，指标集 则 它用来求一些有交集的集合的并集的元素个数。若有全集 ，则可以有另一种表述，即 这是很容易证的，利用 律以及 即可。这个式子可用来求出不具有给定的所有性质的元素的个数。

下面我们来证明容斥原理，这里我们证明另一种表述即式 。

PROOF 设 表示 具有性质 考虑恰好具有 条性质的元素 我们利用 对式 每一部分的“贡献”进行证明，这个贡献的意思是，我们在计数的时候，元素 是否给我们的计数增加了 只要 那么 对 的贡献就为 否则为 由于等式的左边计数了 中不具备所有性质的元素的个数，那么我们只需证明不具备任意一个性质的 给等式右边的贡献为 具备至少一个性质的 给等式右边的贡献为 就能说明等式右边也计数了 中不具备所有性质的元素的个数。

当 一条性质也不具备即 时，它对等式 右边的贡献为 当 时， 对 的贡献为 对和式的第一项的贡献为 对和式的第二项的贡献为 因为满足 的集合 和 要在 个集合中选，数量为 以此类推， 对等式 右边的贡献为 当 时 且 于是 这表明了若 具有至少一个性质，那么它对式 右边的贡献为零；若 不具有任何一个性质，它对式 右边的贡献为 这就是要证的。

倘若 ${1jk} A{i_j}$ 仅依赖于 而不依赖于在交集中使用了哪 个集合，那么我们可以令 那么容斥原理可以有下面的特殊形式： 式中的组合数是和式 ${XIX=k}{iX}A_i$ 项的个数（即 的 子集的个数），且每一项都为

容斥原理的应用（1）

多重集合的组合（2）

在多重集合的组合（1）部分，我们讨论了多重集合 在 时它的 组合的个数。现在我们考虑 的情形，也即不定方程 的部分元有上界时的非负整数解的组数。

我们举一个例子：

例1 求集合 的 组合数目。

SOL 设 的 组合的集合为 的 组合中 的个数至少为 的那部分的集合记作 的个数至少为 的那部分的集合记作 的个数至少为 的那部分的集合记作 则问题转化为求 由容斥原理得 且由已知结论得 对于 容易发现它是 的 组合的集合（倘若我们取出 中的任意一个元素并去掉其中的 个 那么就得到了 的一个 组合；若在 的某个 组合加入 个 便又得到了 中的一个元素），于是 同理有 对于 按照上述的分析思路，可以发现它是 的 组合数目，于是 同理有 代入 计算得 于是 的 组合有 个。

如果没有直接设出 而是直接设出它们在 中的补集，像下面这样：

的 组合的集合为 的 组合的集合为 的 组合的集合为 那么问题转化为求 且由容斥原理得

且

求 还算简单，但是 计算起来就略有些麻烦，更不要说多重集合的元素更多的题目了。

错位排列

错位排列的意思是，将给定的没有重复元素的字符串进行重新排列，使得每一个元素都不在原来的位置上。比如对于 它的一个错位排列就是 设含有 个不重复元素的字符串的错位排列的数目为 下面给出 的通项公式。

SOL 记第 个元素在第 个位置（即它原来的位置）的排列的集合为 那么问题就转化为求 从而可以直接使用容斥原理。注意到 仅仅依赖于 而不依赖于在交集中使用了哪 个集合，此时是我们在上面介绍过的容斥原理的特殊形式，且 于是直接使用式 得

于是给出下面的定理：

定理2 对于 有 若从 的排列中中任意取出一个排列，则它是错位排列的概率 且 这可对 作估计。实际上， 是最接近 的整数。

除了利用容斥原理求出 的方法，还有一种利用递推公式求通项公式的方法。

SOL 注意到 的 个错位排列按照第一个位置为 这 中的一个可划分为 个部分，且这 个部分每一部分的数量都相等，设为 有 考虑 在第一个位置的错位排列 它又可以根据 和 划分为两个子部分，设 的部分的数目为 的部分的数目为 对于 它等于 的错位排列数目，即 而对于 不考虑最左边的 这相当于 不能在第一个位置，剩下的数字不能在各自原来的位置，于是它是 共 个数字的错位排列数目，即 这就得到了

若设 则可以求出 于是就有 即 两边同时除以 有 再利用迭代即得通项公式。

这是不借助容斥原理求出错位排列通项公式的做法。想起来了做过的一道类似借助等式两边除以阶乘的求通项公式的题目：

数列 满足 且 求其通项公式。

SOL 于是 即

倘若还有数列 满足 且 那么就有 则显然有 即 看上去似乎没那么显然。

莫比乌斯反演

我们在这里讨论更一般的容斥原理。容斥原理是莫比乌斯反演（Möbius Inversion）在有限偏序集上的一个实例。 为了给莫比乌斯反演的一般性设置一个好的平台，我们先讨论某种程度上更具有一般性的容斥原理。

引子：偏序集

设 为正整数且 以及偏序集 定义实值函数 其中 为 的幂集。同时利用 定义实值函数 且 上式中， 是 的一个子集， 是函数 在 的所有子集 处的函数值的和。若已知函数 莫比乌斯反演可求出函数 由下面的关系式确定： 其中二元函数 称为偏序集 上的莫比乌斯函数，等式 即为偏序集 上的莫比乌斯反演公式，我们会在后面给出这个式子的证明。

现在我们给出 的更确切的定义，并借助等式 推导出更一般的容斥原理 。设 是有限集 的子集，对于 我们定义 其中对于集合 有 上面 的定义用语言描述就是： 为 中恰好 属于所有 的集合 的元素的个数。若 表明 具有性质 则 计数了恰好具有 个性质的元素的个数，且这 个性质为 下面我们证明 为了体现证明的思想，我们先举一个实例。

假设 以及 那么 为属于 且不属于 的元素的个数，即 计数了恰好具有 这两条性质的元素。 时， 计数了恰好具有 这四条性质的元素； 时， 计数了恰好具有 这三条性质的元素； 时， 计数了恰好具有 这三条性质的元素； 时， 计数了恰好具有 这两条性质的元素。 在具有 这两条性质的元素中，根据它们是否具有性质 可以划分为四部分，这刚好是上面的四个 于是 计数了 中的元素的个数。

对于 的情况，设 在同时具有 这 个性质的元素中，根据它们是否具有性质 可以划分为 个部分，这恰好是 的个数，且每一部分的元素所具有的性质的指标集恰好与这 个 的子集一一对应，而 将这 个 进行求和，所得到的刚好是具备 这 个性质的元素的个数，这就表明了 现在我们用式 来得到更一般的容斥原理。将 代入式 得 其中 是 在 中的补集，最后两个和式之间可以一一对应。而 计数了恰好具有 个性质的元素的个数即不具备所有性质的元素的个数，于是 式 与式 显然是等价的。这就是更为一般的容斥原理。

更一般的偏序集 的莫比乌斯反演公式

现在我们讨论更一般的偏序集 设所有只要满足 就有 的实值函数 的集合为 若 定义 和 的卷积为 卷积运算不具有交换律，但是它具有结合律：

定理3 卷积满足结合律

我们关注 里的三种特殊函数。

Kronecker delta function zeta function 在介绍第三种函数之前，我们先根据 函数的特殊性质给出一些新的定义。对于 函数而言，我们可以验证它满足 都有 这表明对于卷积运算而言， 是一个恒等函数，它是一个恒等元（Identity）。于是借助恒等元，我们可以定义逆元。即对于函数 若存在 使得 我们称 是 的左逆函数；同理可以定义右逆函数。有下面的定理：