@

声明:此博客被海盗队长信奥怪猫侠攻击了!!! 这就是为什么你能看见惊人的300+浏览量(doge)

此博客内容曾被编者手滑删除(本想点取消的呢)，要重新打了呜呜呜┭┮﹏┭┮。

为了深入理解，咱先举个栗子。

现有15人爱吃土豆，8人爱吃马铃薯，而爱吃土豆和马铃薯的共有4人，问只爱吃一种的人共有多少人。

只要你今天带了脑子看此博客， 你就会惊奇的发现:这个问题的答案不就是$15+8+4=27$吗？(当然不是，真要较真扣题目字眼我也没办法doge)

好吧言归正传，答案便是$15+8-4=19$人。

如果我再加一个番茄呢？

为了叙述方便，我们把喜欢土豆、马铃薯、番茄的$person$集合分别用 $A,B,C$表示，则$person$总数等于 $|A\cup B\cup C|$。刚才已经讲过，如果把这三个集合的元素个数 $|A|,|B|,|C|$直接加起来，会有一些元素重复统计了，因此需要扣掉 $|A\cap B|$,$|B\cap C|$,$|C\cap A|$，但这样一来，又有一小部分多扣了，需要加回来，即 $|A\cap B\cap C|$。即

把上述问题推广到一般情况，就是我们熟知的容斥原理。

全集 $U$ 即为 $1\sim n$ 的排列，$|U|=n!$；属性就是 $P_i\neq i$. 套用补集的公式，问题变成求 $\left|\bigcup_{i=1}^n\overline{S_i}\right|$ .

可以知道，$\overline{S_i}$的含义是满足 $P_i=i$的排列的数量。用容斥原理把问题式子展开，需要对若干个特定的集合的交集求大小，即：

其中省略了 $a_i<a_{i+1}$ 的条件以方便表示。上述 $k$ 个集合的交集表示有 $k$ 个变量满足 $P_{a_i}=a_i$ 的排列数，而剩下 $n-k$ 个数的位置任意，因此排列数：

那么选择 $k$个元素的方案数为 $\dbinom{n}{k}$，因此有：

因此 $n$ 的错位排列数为：

错位排列数列的前几项为 $0,1,2,9,44,265（OEIS A000166）$。

接着我们尝试抽象出容斥原理的模型：

• 全集 $U$：不定方程 $\sum_{i=1}^nx_i=m$ 的非负整数解

• 元素：变量 $x_i$.

• 属性：$x_i$的属性即 $x_i$ 满足的条件，即 $x_i\leq b_i$的条件

目标：所有变量满足对应属性时集合的大小，即 $|\bigcap_{i=1}^nS_i|$.

这个东西可以用 $\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right| $求解。 |U| 可以用组合数计算，后半部分自然使用容斥原理展开。

那么问题变成，对于一些 $\overline{S_{a_i}}$的交集求大小。考虑 $\overline{S_{a_i} }$的含义，表示 $x_{a_i}\geq b_{a_i}+1$的解的数目。而交集表示同时满足这些条件。因此这个交集对应的不定方程中，有些变量有 下界限制，而有些则没有限制。

能否消除这些下界限制呢？既然要求的是非负整数解，而有些变量的下界又大于 $0$，那么我们直接 演都不演了，把这个下界减掉，就可以使得这些变量的下界变成 $0$，即没有下界了。

因此对于$\left|\bigcap_{a_i<a_{i+1} }^{1\leq i\leq k}S_{a_i}\right|$的不定方程形式为$\sum_{i=1}^nx_i=m-\sum_{i=1}^k(b_{a_i}+1)$

于是这个也可以组合数计算啦。这个长度为 $k$ 的 $a$ 数组相当于在枚举子集。

bro以为容斥原理就这么结束了？哈哈，这个错位排列是假的，用来补全上述(以后认准 权威 字眼)。

容斥原理定义

证明

补集

错位排列定义