错位排列
2huk
·
·
算法·理论
求有多少 1 \sim n 的排列 p 满足 p_i \ne i。
递推
令 d_n 表示答案。我们考虑 n - 1 和 n 的排列的关系。
这样思考。假如此时我们已经获得了一个 n - 1 的排列。现在在这个排列的后面添加一个值 n。这就是一个 n 的排列。
显然此时这个排列并不是错位排列，因为 p_n = n。我们尝试将 p_n 和某个 p_i（1 \le i \le n - 1） 交换，并希望交换这一次后新排列是一个错位排列。
此时分类讨论：
- 若原 n - 1 排列是错位排列，即不存在 p_i = i（1 \le i \le n - 1），那么显然我们可以与任意一个交换。交换的选择有 n - 1 个，前 n - 1 个位置的错排有 d_{n - 1} 种方案。即总方案为 (n - 1)d_{n - 1}。
- 若原 n - 1 排列不是错位排列，存在且仅存在一个 p_i = i（1 \le i \le n - 1）。那么很固定，我们只能与这个 i 交换。这个 i 的取值有 n - 1 个，除去这个 i 外，剩下的 n - 2 个位置的错排有 d_{n-2} 种方案。即总方案为 (n - 1)d_{n-2}。
- 若原 n - 1 排列不是错位排列，存在至少两个 p_i = i（1 \le i \le n - 1）。显然的是，我们无法通过一次交换，使这些不满足条件的位置同时满足条件。即方案数为 0。
综上 d_n = (n-1)d_{n-1} + (n-1)d_{n-2} = (n-1)(d_{n-1} + d_{n - 2})。
容斥
对于这种限制类的问题，直接考虑容斥。
若我们能求出：$f(i)$ 表示有多少个 $n$ 的排列，存在**至少** $i$ 个 $p_j \ne j$（$1 \le j \le n$），那么容斥就有：
$$
d_n = f(0) - f(1) + f(2) - f(3) + \dots
$$
形式化即：
$$
d_n = \sum_{i=0}^n (-1)^i f(i)
$$
考虑求解 $f(i)$。
考虑一般的 $i$。我们给 $f(i)$ 的定义里写存在**至少** $i$ 个 $p_j \ne j$，那不妨我们先把这 $i$ 个找出来。有 $\dbinom ni$ 种选择。对于剩下的 $n - i$ 个位置，我们对其不做限制，因为即使不做限制，我们也能保证错误的位置至少有刚才选出的 $j$ 个。即剩下的位置有 $(n - i)!$ 种方案。
于是：
$$
f(i) = \dbinom ni (n-i)! = \dfrac{n!}{i!(n-i!)} \cdot (n-i)! = \dfrac{n!}{i!}
$$
因此：
$$
d_n = \sum_{i=0}^n (-1)^i f(i) = \sum_{i=0}^n (-1)^i \dfrac{n!}{i!}
$$
## 二项式反演
令 $f(n)$ 表示有恰好 $n$ 个位置填错的方案数，也就是答案。
考虑设 $g(n)$ 表示有至多 $n$ 个位置填错的方案数。不难发现 $g(n) = n!$。
考虑 $f, g$ 的关系：
$$
g(n) = \sum_{k=0}^n \dbinom nk \times f(k)
$$
二项式反演得：
$$
\begin{aligned}
f(n) &=\sum_{k=0}^n \dbinom nk(-1)^{n-k}g(k) \\
&= \sum_{k=0}^n\dbinom nk(-1)^{n-k}k! \\
&= \sum_{k=0}^n \dfrac{(-1)^{n-k}n!}{(n-k)!} \\ &=
\sum_{k=0}^n \dfrac{(-1)^k n!}{k!}
\end{aligned}
$$