错位排列

定义

错位排列（derangement）是没有任何元素出现在其有序位置的排列．即，对于 $1 \sim n$ 的排列 $P$ ，如果满足 $P_{i} \neq i$ ，则称 $P$ 是 $n$ 的错位排列．

例如，三元错位排列有 ${2, 3, 1}$ 和 ${3, 1, 2}$ ．四元错位排列有 ${2, 1, 4, 3}$ 、 ${2, 3, 4, 1}$ 、 ${2, 4, 1, 3}$ 、 ${3, 1, 4, 2}$ 、 ${3, 4, 1, 2}$ 、 ${3, 4, 2, 1}$ 、 ${4, 1, 2, 3}$ 、 ${4, 3, 1, 2}$ 和 ${4, 3, 2, 1}$ ．错位排列是没有不动点的排列，即没有长度为 1 的循环．

容斥原理的计算

全集 $U$ 即为 $1 \sim n$ 的排列， $| U | = n!$ ；令 $S_{i}$ 是其中满足 $P_{i} \neq i$ 的排列．运用补集和容斥原理的知识，问题变成求：

\begin{aligned} | ⋂_{i = 1}^{n} S_{i} | & = | U | - | ⋃_{i = 1}^{n} \overset{―}{S_{i}} | \\ = n! - \sum_{k = 1}^{n} (- 1)^{k - 1} \sum_{a_{i} < a_{i + 1}} | ⋂_{i = 1}^{k} \overset{―}{S_{a_{i}}} | \end{aligned}

其中求和的含义是 $1, 2, \dots, n$ 中取 $a_{1}, a_{2}, \dots, a_{k}$ 且满足 $a_{i} < a_{i + 1}$ ．于是

| ⋂_{i = 1}^{k} \overset{―}{S_{a_{i}}} |

表示有 $k$ 个数 $a_{1}, a_{2}, \dots, a_{k}$ 满足 $P_{a_{i}} = a_{i}$ ，而剩下 $n - k$ 个数的位置任意的排列数，因此：

| ⋂_{i = 1}^{k} \overset{―}{S_{a_{i}}} | = (n - k)!

这 $k$ 个数的选择情况共 $(\binom{n}{k})$ 种，对其求和有：

\begin{aligned} \sum_{k = 1}^{n} (- 1)^{k - 1} \sum_{a_{i} < a_{i + 1}} | ⋂_{i = 1}^{k} \overset{―}{S_{a_{i}}} | \\ = & \sum_{k = 1}^{n} (- 1)^{k - 1} (\binom{n}{k}) (n - k)! \\ = & \sum_{k = 1}^{n} (- 1)^{k - 1} \frac{n!}{k!} \\ = & n! \sum_{k = 1}^{n} \frac{(- 1)^{k - 1}}{k!} \end{aligned}

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

D_{n} = n! - n! \sum_{k = 1}^{n} \frac{(- 1)^{k - 1}}{k!} = n! \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}

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

递推的计算

把错位排列问题具体化，考虑这样一个问题：

$n$ 封不同的信，编号分别是 $1, 2, 3, 4, 5$ ，现在要把这五封信放在编号 $1, 2, 3, 4, 5$ 的信封中，要求信封的编号与信的编号不一样．问有多少种不同的放置方法？

假设考虑到第 $n$ 个信封，初始时暂时把第 $n$ 封信放在第 $n$ 个信封中，然后考虑两种情况的递推：

前面 $n - 1$ 个信封全部装错；
前面 $n - 1$ 个信封有一个没有装错其余全部装错．

对于第一种情况，前面 $n - 1$ 个信封全部装错：因为前面 $n - 1$ 个已经全部装错了，所以第 $n$ 封只需要与前面任一一个位置交换即可，总共有 $D_{n - 1} \times (n - 1)$ 种情况．

对于第二种情况，前面 $n - 1$ 个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若 $n - 1$ 个信封中如果有一个没装错，那么把那个没装错的与 $n$ 交换，即可得到一个全错位排列情况．

其他情况，不可能通过一次操作来把它变成一个长度为 $n$ 的错排．

于是可得，错位排列数满足递推关系：

D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})

这里也给出另一个递推关系：

D_{n} = n D_{n - 1} + {(- 1)}^{n}

其他关系

错位排列数有一个简单的取整表达式，增长速度与阶乘仅相差常数：

D_{n} = ⌊ \frac{n!}{e} + \frac{1}{2} ⌋

随着元素数量的增加，形成错位排列的概率 P 接近：

P = lim_{n \to \infty} \frac{D_{n}}{n!} = \frac{1}{e}

本页面最近更新：2026/3/25 06:20:21，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, Great-designer, amlhdsan, BeiChenStanly, Enter-tainer, untitledunrevised, xzdeyg
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用