跳转至

# 错位排列

### 定义

错位排列（derangement）是没有任何元素出现在其有序位置的排列．即，对于 1 ∼𝑛 1∼n 的排列 𝑃 P，如果满足 𝑃 𝑖 ≠𝑖 P i≠i，则称 𝑃 P 是 𝑛 n 的错位排列．

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

### 容斥原理的计算

全集 𝑈 U 即为 1 ∼𝑛 1∼n 的排列，|𝑈| =𝑛!|U|=n!；令 𝑆 𝑖 S i 是其中满足 𝑃 𝑖 ≠𝑖 P i≠i 的排列．运用补集和 容斥原理 的知识，问题变成求：

∣𝑛⋂𝑖=1 𝑆 𝑖∣=|𝑈|−∣𝑛⋃𝑖=1――𝑆 𝑖∣=𝑛!−𝑛∑𝑘=1(−1)𝑘−1∑𝑎 𝑖<𝑎 𝑖+1∣𝑘⋂𝑖=1―――𝑆 𝑎 𝑖∣|⋂i=1 n S i|=|U|−|⋃i=1 n S i―|=n!−∑k=1 n(−1)k−1∑a i<a i+1|⋂i=1 k S a i―|

其中求和的含义是 1,2,⋯,𝑛 1,2,⋯,n 中取 𝑎 1,𝑎 2,⋯,𝑎 𝑘 a 1,a 2,⋯,a k 且满足 𝑎 𝑖 <𝑎 𝑖+1 a i<a i+1．于是

∣𝑘⋂𝑖=1―――𝑆 𝑎 𝑖∣|⋂i=1 k S a i―|

表示有 𝑘 k 个数 𝑎 1,𝑎 2,⋯,𝑎 𝑘 a 1,a 2,⋯,a k 满足 𝑃 𝑎 𝑖 =𝑎 𝑖 P a i=a i，而剩下 𝑛 −𝑘 n−k 个数的位置任意的排列数，因此：

∣𝑘⋂𝑖=1―――𝑆 𝑎 𝑖∣=(𝑛−𝑘)!|⋂i=1 k S a i―|=(n−k)!

这 𝑘 k 个数的选择情况共 (𝑛 𝑘)(n k) 种，对其求和有：

𝑛∑𝑘=1(−1)𝑘−1∑𝑎 𝑖<𝑎 𝑖+1∣𝑘⋂𝑖=1―――𝑆 𝑎 𝑖∣=𝑛∑𝑘=1(−1)𝑘−1(𝑛 𝑘)(𝑛−𝑘)!=𝑛∑𝑘=1(−1)𝑘−1 𝑛!𝑘!=𝑛!𝑛∑𝑘=1(−1)𝑘−1 𝑘!∑k=1 n(−1)k−1∑a i<a i+1|⋂i=1 k S a i―|=∑k=1 n(−1)k−1(n k)(n−k)!=∑k=1 n(−1)k−1 n!k!=n!∑k=1 n(−1)k−1 k!

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

𝐷 𝑛=𝑛!−𝑛!𝑛∑𝑘=1(−1)𝑘−1 𝑘!=𝑛!𝑛∑𝑘=0(−1)𝑘 𝑘!D n=n!−n!∑k=1 n(−1)k−1 k!=n!∑k=0 n(−1)k k!

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

### 递推的计算

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

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

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

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

对于第一种情况，前面 𝑛 −1 n−1 个信封全部装错：因为前面 𝑛 −1 n−1 个已经全部装错了，所以第 𝑛 n 封只需要与前面任一一个位置交换即可，总共有 𝐷 𝑛−1 ×(𝑛 −1)D n−1×(n−1) 种情况．

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

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

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

𝐷 𝑛=(𝑛−1)(𝐷 𝑛−1+𝐷 𝑛−2)D n=(n−1)(D n−1+D n−2)

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

𝐷 𝑛=𝑛 𝐷 𝑛−1+(−1)𝑛 D n=n D n−1+(−1)n

### 其他关系

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

𝐷 𝑛={⌈𝑛!e⌉,i f 𝑛 i s e v e n,⌊𝑛!e⌋,i f 𝑛 i s o d d.D n={⌈n!e⌉,if n is even,⌊n!e⌋,if n is odd.

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

𝑃=l i m 𝑛→∞𝐷 𝑛 𝑛!=1 e P=lim n→∞D n n!=1 e

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