江苏省南通市如皋市2023-2024学年高三上学期9月诊断测试 T10 相关及补充。
错位排列的定义
错位排列（derangement）是没有任何元素出现在其有序位置的排列。即，对于 1\sim n 的排列 P ，如果满足 P_i\neq i ，则称 P 是 n 的错位排列。
——OI WIKI
记 n 元错排数为 D_n 。
显然，有 D_1 = 0, D_2 = 1 。
错位排列的两种线性递推
对于 n \ge 3 ，有 D_n = (n-1)(D_{n-1} + D_{n-2}) 。
证明：
考虑 新增整数 n 对原来 1 \sim n-1 排列的影响：
先将 n 放到位置 n 上，
-
若前 1 \sim n-1 中，恰有一个数 m 在位置 m 上，其余的数均错排。此时将 m 与 n 交换，满足要求。此时方案数为 (n-1)D_{n-2} 。
-
若前 1 \sim n-1 均错排。此时将 n 与前面任意一个数交换位置，满足要求。此时方案数为 (n-1)D_{n-1} 。
显然的，没有其他情况使得仅通过一次交换满足要求。
两种情况相加，得到 D_n = (n-1)(D_{n-1} + D_{n-2}) 。
对于 n \ge 2 ，有 D_n = nD_{n-1} + (-1)^n 。
证明：
对 D_n = (n-1)(D_{n-1} + D_{n-2}) 变形：
D_n = (n-1)(D_{n-1} + D_{n-2})\\
D_n = (n-1)D_{n-1} + (n-1)D_{n-2}\\
D_n - nD_{n-1} = -D_{n-1} + (n-1)D_{n-2}\\
D_n - nD_{n-1} = (-1)(D_{n-1} - (n-1)D_{n-2})
\end{array}
于是 \{ D_n - nD_{n-1} \} 是首项为 1 ，公比为 -1 的等比数列，故有 D_n - nD_{n-1} = (-1)^n 。
即 D_n = nD_{n-1} + (-1)^n 。
错位排列的通项及其性质
对于正整数 n ， D_n = \sum_{k = 0}^{n} \frac{(-1)^k}{k!} 。
证明：
根据递推式 D_n = nD_{n-1} + (-1)^n ，两边同时除以 n! ，有：
\frac{D_n}{n!} = \frac{D_{n-1}}{(n-1)!} + \frac{(-1)^n}{n!}
累加可得：
\frac{D_n}{n!} = \sum_{k = 0}^{n} \frac{(-1)^k}{k!} \tag{$\mathrm{a}$}
故 D_n = \sum_{k = 0}^{n} \frac{(-1)^k}{k!} 。
注意到 e^x 在 x = -1 处的泰勒展开与 (\mathrm{a}) 式有公共部分：
\frac{1}{e} = \sum_{k=0}^{\infty}\frac{(-1)^k}{k!}
于是有：
\frac{1}{e} = \frac{D_n}{n!} + \sum_{k=n+1}^{\infty}\frac{(-1)^k}{k!}\tag{$\mathrm{b}$}
错位排列的近似估计
观察上一节的公式 (\mathrm{b}) ，随着 n 的增加，后面的和式越来越小。不加证明地给出近似：
\frac{1}{e} \approx \frac{D_n}{n!}
\\
D_n \approx \frac{n!}{e}
事实上，错位排列数有一个简单的取整表达式，增长速度与阶乘仅相差常数：
D_n=\begin{cases}
\left\lceil\frac{n!}{\mathrm{e}}\right\rceil, & \text{if }n\text{ is even}, \\
\left\lfloor\frac{n!}{\mathrm{e}}\right\rfloor, & \text{if }n\text{ is odd}.
\end{cases}
也即：
\lim_{n\to\infty}\frac{D_n}{n!}=\frac{1}{\mathrm{e}}