基础知识：错排问题

什么是错排问题？重排指的是在排列组合中，一个排列的所有的元素都不在原来的位置上；更加地形式化说明的话，就是对于一个包含 $1\cdots n$ 全部 $n$ 个元素的排列 $p$ ，按照 $1$ -下标方法，对于任何 $i \in [1, n]$ 都满足 $p_i \ne i$ ；这类问题常见的应用有信封问题（经典原型），书架问题（换皮原型）等。

那么，这篇文章着眼于如何推出错排问题的式子，以及它的简化式子展开介绍：

递推公式

现在，我们假设有一个包含 $1\cdots n$ 全部 $n$ 个元素的排列 $p$ ，并且按照 $1$ -下标方法定位；最开始时，对于任何 $i \in [1, n]$ 都满足 $p_i = i$ ；那么我们对它进行操作，将它变成一个重排：

首先从原来的序列中取出一个下标；因为不管选择哪个都是等价的，我们选择 $[n]$ 位置，取出 $n$
再从剩下来的 $n - 1$ 个正确的位置中，选择一个位置 $[k]$ ；我们将要把 $n$ 放入 $[k]$ 位置，取出 $k$
显然，这一步对于位置 $[k]$ 的选择有 $n - 1$ 种不同的选择。
接下来，我们要将 $k$ 放回序列中；我们有两种选择：
- 将 $k$ 放入位置 $[n]$ ；这样相当于交换了 $n$ 和 $k$ 的位，使得了这两个位置符合了错排的考虑
  现在还剩下 $n - 2$ 个位置，它们都是有序的；可以被作为一个子问题递归地处理
- 将 $k$ 放入位置 $[i \ne n]$ ，也就是不放入位置 $[n]$ ；这种情况下，我们可以这样考虑：
  - 对于位置 $[k] = n$ ，已经是确定的了，所以可以忽略它
  - 我们暂时将 $k$ 放入 $[n]$ ，因为最终会将 $k$ 放到其他位置上，所以可以认为此时是未重排状态
  - 此时，剩下的排列包含了 $n - 1$ 个元素，它们都“未经过重排”，可看作一个子问题递归
- 综上所述，第一种选择是作为 $n - 2$ 的子问题，第二种选择 $n - 1$ 的子问题递归。
那么，由于乘法法则和加法法则；令 $D_n$ 表示长度为 $n$ 的重排排列的数量，那么可得到：

D_n = (n - 1) \cdot (D_{n - 1} + D_{n - 2})

且特殊地存在 $D_0 = 1$ 和 $D_1 = 0$ ；这就是我们得到的第一个递推式子；

化简

这一步的化简网上一般有两种做法；作者选择了她喜欢的一种详细介绍：

对于上述得到的重排公式，我们在等式的两侧同时减去 $nD_{n -1}$ ，可得：

\begin{aligned} D_n - nD_{n - 1} &= -D_{n - 1} + (n - 1)D_{n - 2} \\ &= -[D_{n - 1} - (n - 1)D_{n - 2}] \\ &= (-1)^2[D_{n - 2} - (n - 2)D_{n - 3}] \\ &= \cdots \\ &= (-1)^{n - 1}(D_1 - D_0) \\ &= (-1)^n \end{aligned}

所以，可以得到化简后的递推公式： $D_n = nD_{n - 1} + (-1)^n$ ，特别地 $D_1 = 0$ ；

另一种的做法假设 $D_n = n!M_n$ ，那么 $M_1 = 0$ ， $M_2 = \frac12$ ；

对于 $n \geq 3$ 的场合，将第一个递推公式 $D_n = (n - 1) \cdot (D_{n - 1} + D_{n - 2})$ 根据定义拆分：

\begin{aligned} n!M_n &= (n - 1)(n - 1)!M_{n - 1} + (n - 1)(n - 2)!M_{n - 2} \\ &= n!M_{n - 1} - (n - 1)!M_{n - 1} + (n - 1)!M_{n - 2} \\ n!M_n - n!M_{n - 1} &= -((n - 1)!M_{n - 1} - (n - 1)!M_{n - 2}) \\ M_n - M_{n - 1} &= -\frac1n(M_{n - 1} - M_{n - 2}) \\ \end{aligned}

其实这种推导和上面的是完全等价的——不如说看起来几乎完全没有怎么化简；只是因为这种推导方法在得到通项公式的时候更加的自然~~再推导一步就得到通项公式了，所以删了（~~。

通项公式

只有递推公式有的时候是不够的，所以我们还需要依据上面求出的递推公式求出通项公式；这里作者提供了三种不同的推导方法：

套公式

对于形如 $f(n) = g(n)f(n - 1) + h(n)$ 的递推方程，经过暴力展开，可以得到下面的公式：

f(n) = \prod_{i = 1}^n g(i) \cdot [f(0) + \sum_{i = 1}^n \frac{h(i)}{\prod_{j = 1}^ig(j)}]

对于我们求得的递推公式 $D_n = nD_{n - 1} + (-1)^n$ ，不难通过观察得出三个部分是 $f(x) = D_x$ 、 $g(x) = x$ 、 $h(x) = (-1)^x$ ；带入上面的暴力公式中，可以求出：

D_n = n! \cdot [1 + \sum_{k = 1}^n \frac{(-1)^k}{k!}] = n! \cdot \sum_{k = 0}^n \frac{(-1)^k}{k!}

那么就得到了错排数量的通项公式。

继续推导

在板块一提到的第二种方法化简得到的： $M_n - M_{n - 1} = -\frac1n(M_{n - 1} - M_{n - 2})$ ；我们将代入多个 $n$ 并将得到的式子的左侧和右侧全部相加，可以得到：

\begin{aligned} M_n - M_1 &= (-1)^2\frac1{2!} + (-1)^3\frac1{3!}+\dots+(-1)^n\frac1{n!} \\ M_n &= \sum_{k = 2}^n (-1)^n\frac1{k!} + 1 + (-1)\frac1{1!} \\ M_n &= \sum_{k = 0}^n (-1)^n\frac1{k!} \end{aligned}

又因为 $D_n = n!M_n$ ，所以 $D_n = n!\cdot\sum_{k = 0}^n (-1)^n\frac1{k!}$ ，和上面的化简结果一样。

容斥定理

对于长度为 $n$ 的排列，一共有 $n!$ 种不同的排列；我们要求的重排排列是它的子集；因此我们考虑，如果我们将所有不是重排排列的情况去除，那么剩下的就全部是重排排列了！

假定排列的长度为 $n$ ，我们令 $A_i$ 为满足 $p[i] = i$ 的排列种数，那么显然可以得到：

\begin{aligned} |A_i| &= (n - 1)! \\ |A_i \cap A_j| &= (n - 2)! \\ |A_i \cap A_j \cap A_k| &= (n - 3)! \\ &\vdots \end{aligned}

因此，每个元素都不在对应位置的时间就是对于 $1 \leq i \leq n$ 的 $\overline{A_i}$ ：

\begin{aligned} \bigcap_{i = 1}^n \overline{A_i} &= n! - \mathbf{C}_n^1(n - 1)! + \mathbf{C}_n^2(n - 2)! - \cdots \mp \mathbf{C}_n^{n - 1}2! \pm \mathbf{C}_n^n1! \\ &= \sum_{k = 0}^n (-1)^k \cdot \mathbf{C}_n^k(n - k)! \\ &= n!\sum_{k = 0}^n (-1)^k \cdot \frac1{k!} \end{aligned}

显然，这也和之前的推导结果是一致的；

那么我们可以怎么理解式子中的加加减减呢？我们首先删除以每一个 $i$ 不满足的位置，但是这样对于排列中出现了两个不满足的位置的情况额外减了一次，所以要加回来——首先组合选出两个位置，然后其他的位置全排列；但是这样又会导致有三个不满足的位置的情况多加了…… 以此类推直到所有的位置都不正确的唯一情况。

母函数方法

百度百科的证法实在是太过玄妙，，如果有看懂了的欢迎讲给博主听（

化简公式

但是在算法竞赛中使用这样的超级复杂的多项式通项公式约等于没有，甚至效率不如直接递推；所以我们需要使用起来更加方便的通项公式：

首先我们考虑 $e^x$ 的幂级数展开（麦克劳林公式/泰勒展开）：

\forall x \in \mathbb{C}, \ e^x = \sum_{n = 0}^{+\infty}\frac{x^n}{n!} \approx 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots + \frac{x^n}{n!}

泰勒展开后面还带一个余项，不过这我就真的不会了~~高数早就还给微积分老师力~~（

对于 $x = -1$ ，我们可以得到如下的泰勒展开式：

e^{-1} = \sum_{i = 0}^n \frac{(-1)^i}{i!} + R_n \ , \ R_n = \frac{e^{-c}(c - 1)^n}{(n + 1)!} \ , \ c \in [0, 1]

所以，我们可以认为： $e^{-1} = \frac{D_n}{n!} + R_n$ ，或者 $n!e^{-1} - D_n = n!R_n$ ；又因为余项 $R_n$ 在 $c$ 取 $c = 0$ 时取到上界 $\frac1{(n + 1)!}$ ，因此可以得到：

|n!\cdot e^{-1} - D_n| = |n!\cdot R_n| \leq \frac{n!}{(n + 1)!} = \frac1{n + 1}

在我们的通项公式的可行域 $n \geq 1$ 中，显然满足 $\frac1{n + 1} \leq \frac12$ ；因此我们可以认为 $D_n$ 和最接近 $\frac{n!}e$ 的整数相同；所以最后我们可以将化简后的通项公式写成下面这样：

D_n = \lfloor \frac{n!}e + \frac12\rfloor

向下取整在代码中实现也非常方便，就达到化简通项公式的目的。

练习题

这种裸题应该还是挺多的；所以我就随便挂一个经典原型了：

`cses.fi` 1717

有 $n$ 个小盆友，每个小盆友都买了一个圣诞礼物与其他的小盆友交换；要求每个小盆友都要得到来自其他小盆友的礼物；问一共有多少种交换方式。

const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int ans[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int n; input, n;
    ans[0] = ans[2] = 1, ans[1] = 0;
    for (longs i = 3; i <= n; ++ i)
        ans[i] = int((ans[i - 1] + ans[i - 2])
                        % mod * (i - 1) % mod);
    output, ans[n], endl;

    return 0;
}

因为数据范围很小，所以只需要使用递推公式就可以通过此题了。

后记

虽然推的时候还是很痛苦的，但是写博文的时候又觉得言之无物，，看来还是昨天晚上睡少了（

如果有机会的话再完善一下关于错排生成算法的东西吧……