错排问题

错排是把 $n$ 个互不相同的对象重新放入 $n$ 个原位置，要求没有任何对象留在自己的位置。比如四封写好地址的信装入四个已贴收件人姓名的信封，每封都装错。不能把每一步都看成“剩 $n - 1$ 个可选”，因为后面的选择相互牵制。

从全部排列减去固定点

总排列数为 $n!$ 。令 $E_{i}$ 是第 $i$ 个对象放对位置的事件；指定 $k$ 个对象必须放对后，剩下有 $(n - k)!$ 种排列。按容斥原理，无固定点的排列数 $D_{n} = \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) (n - k)! = n! \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!} .$ 取 $n = 4$ ，得到 $D_{4} = 24 (1 - 1 + 1 / 2 - 1 / 6 + 1 / 24) = 9$ 。若随意均匀打乱四封信，全部装错的概率是 $9 / 24 = 3 / 8$ 。公式中的“加回”不是把漏掉的排列凭空造出，而是修正同时被多个 $E_{i}$ 扣除的重叠部分。

一个能递推的分类

看对象 1 被放到位置 $j \neq 1$ 。若对象 $j$ 被放到位置 1，它们成一个二循环，剩下 $n - 2$ 个对象需错排，有 $D_{n - 2}$ 种。否则对象 1 所在循环至少有三个元素；从这个循环删掉 1、把它前后两个元素直接接起来，得到 $n - 1$ 个对象的错排。反向把 1 插回循环中紧邻 $j$ 的指定位置，可恢复原排列，故此类有 $D_{n - 1}$ 种。 $j$ 有 $n - 1$ 种选择，故 $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ ，初值 $D_{0} = 1, D_{1} = 0$ 。于是 $D_{2} = 1, D_{3} = 2, D_{4} = 9$ ，与容斥相符。

随着 $n$ 增大，错排概率 $D_{n} / n!$ 趋向 $e^{- 1}$ ，因为它正是 $e^{- 1}$ 的交错级数前 $n + 1$ 项；余项绝对值小于 $1 / (n + 1)!$ 。这里是均匀随机排列的结果；若现实中某些信封更容易拿错，概率便不再由 $D_{n} / n!$ 给出。

参考资料与相关词条

MIT 6.042J：容斥与排列计数。
相关：排列与组合、容斥原理、可重复排列与组合。