错位排列

错位排列

定义

错位排列（derangement）是没有任何元素出现在其有序位置的排列。即，对于 的排列 ，如果满足 ，则称 是 的错位排列。

例如，三元错位排列有 和 。四元错位排列有 、、、、、、、 和 。错位排列是没有不动点的排列，即没有长度为 1 的循环。

容斥原理的计算

全集 即为 的排列，；属性就是 . 套用补集的公式，问题变成求 .

可以知道， 的含义是满足 的排列的数量。用容斥原理把问题式子展开，需要对若干个特定的集合的交集求大小，即：

其中省略了 的条件以方便表示。上述 个集合的交集表示有 个变量满足 的排列数，而剩下 个数的位置任意，因此排列数：

那么选择 个元素的方案数为 ，因此有：

因此 的错位排列数为：

错位排列数列的前几项为 （OEIS A000166）。

递推的计算

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

封不同的信，编号分别是 ，现在要把这五封信放在编号 的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法？

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

• 前面 个信封全部装错；
• 前面 个信封有一个没有装错其余全部装错。

对于第一种情况，前面 个信封全部装错：因为前面 个已经全部装错了，所以第 封只需要与前面任一一个位置交换即可，总共有 种情况。

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

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

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

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

其他关系

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

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