derangement · Dₙ ≈ n!/e

错排

$n$ 个人各交一顶帽子，主持人洗乱后随机发回。没有一个人拿回自己那顶的发法数记作 $D_n$ ，称错排（derangement）。它的定义是减法式的：从全排列 $n!$ 里扣掉「至少有一人拿对」的发法。可这些发法按「谁拿对了」分类时互相重叠，同一种发法可能被两三个人同时认领，两条计数原理里的加法原理要求各类互斥，此处并不满足，扣除只能交给容斥原理。

1 · 不动点与错排

derangement · Dₙ / n! → 1/e

把一种发法看成排列 $\pi$ ：第 $i$ 人拿到第 $\pi(i)$ 顶帽子。满足 $\pi(i) = i$ 的位置称不动点（fixed point），错排即没有不动点的排列。 $n = 1$ 时唯一的排列全是不动点， $D_1 = 0$ ； $n = 2$ 时只有互换一种发法， $D_2 = 1$ ； $n = 3$ 的六个排列里合格的是两个三轮换， $D_3 = 2$ 。空排列没有位置可违约，约定 $D_0 = 1$ ，这条约定让后面的递推与求和式在起点处也成立。

图 1-1 · 帽子发还的全部发法与其中的错排。可调人数

n

并切换只列错排，单击任一发法查看它的不动点。

2 · 容斥求和式

Dₙ = Σ (−1)ᵏ C(n,k)(n−k)!

设 $A_i$ 是「第 $i$ 人拿到自己帽子」的全部排列构成的集合。给定下标集合 $S$ ，交集 $\bigcap_{i \in S} A_i$ 要求 $S$ 里每人都拿对，其余 $n - |S|$ 人随意排列，于是

\left| \bigcap_{i \in S} A_i \right| = (n - |S|)!

这个大小只取决于 $|S|$ ，与具体是哪几个人无关。大小为 $k$ 的下标集合有 $C(n, k)$ 个，容斥的第 $k$ 层因而合并成单独一项：

D_n = \sum_{k=0}^{n} (-1)^k C(n, k)\,(n-k)! = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}

第二个等号只需代入 $C(n, k)\,(n-k)! = n!/k!$ 。

例 2.1 $n = 4$ 时逐层相消： $24 - 4 \times 6 + 6 \times 2 - 4 \times 1 + 1 \times 1 = 9$ ，与枚举 24 个排列筛出的 9 个错排吻合。

警示 · 把求和式照抄成浮点代码，在 $n = 18$ 上会给出错的整数。derangementSeries 按 $n! \sum (-1)^k/k!$ 计算， $n = 4$ 的结果已经是 9.000000000000002；取整后两式一直吻合到 $n = 17$ ，而 $n = 18$ 时双精度给出 2355301661033953.5，取整得 2355301661033954，递推与 BigInt 精确值则都是 2355301661033953。再往上递推自己也失守： $D_{19}$ 的精确值是 44750731559645106，双精度递推给出 44750731559645100，此处 $D_n$ 已越过 Number.MAX_SAFE_INTEGER。交错级数的逐项相消是数值上的经典陷阱，需要精确整数时应走 BigInt。

3 · 递推与组合解释

Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂)

求和式给出闭式，递推给出更快的算法。考察第 1 人：他拿到的帽子有 $n-1$ 种可能，设为第 $j$ 顶。再看第 $j$ 人的去向，两种情形互斥且穷尽：

第 $j$ 人拿了第 1 顶，两人互换退出，剩下 $n-2$ 人自成一个错排问题，有 $D_{n-2}$ 种；
第 $j$ 人没拿第 1 顶，此时把第 1 顶帽子改称「第 $j$ 人的帽子」，剩下的 $n-1$ 人（含第 $j$ 人）恰好构成一个不许拿到自己帽子的错排问题，有 $D_{n-1}$ 种。

乘上第 1 人的 $n-1$ 种选择：

D_n = (n-1)\,(D_{n-1} + D_{n-2})

与求和式对照还能整理出一条只回溯一步的形式， $D_n = n D_{n-1} + (-1)^n$ ：整个交错级数被压成一个 $\pm 1$ 的修正项。本页的测试对 $1 \le n \le 17$ 逐项断言了这条恒等式，超出这个范围两边都已不是精确整数。

4 · 与 1/e 的距离

Dₙ/n! → 1/e ≈ 0.367879

$D_n/n!$ 就是随机发帽子时无人拿对的概率。按求和式，它等于交错级数 $\sum_{k=0}^{n} (-1)^k/k!$ 的部分和， $n$ 趋于无穷时收敛到 $e^{-1} \approx 0.367879$ 。交错级数的截断误差不超过首个被丢弃的项 $1/(n+1)!$ ，收敛因而快得不像话：实测截到 $k = 8$ 时与 $1/e$ 的差是 $2.50 \times 10^{-6}$ ，截到 $k = 9$ 就降到 $2.52 \times 10^{-7}$ ，即从第 9 项起差已小于 $10^{-6}$ 。

图 4-1 · 交错级数部分和向

1/e

的收敛。可调截断项数观察部分和如何在

1/e

两侧交替逼近，右列是它与

1/e

的差。

由此得到一个与直觉相左的结论：无人拿对的概率几乎不随人数变化。 $n = 4$ 时是 $9/24 = 0.375$ ， $n = 100$ 与 $n = 10^6$ 时仍在 $0.3679$ 附近，差别落在小数点后一百多位。排列 P(n, k) 与 $n!$ 本身随 $n$ 爆炸式增长，两个爆炸量的比值却稳定在一个常数上。收敛之快还带来一条工程上的便利： $D_n$ 等于 $n!/e$ 四舍五入的结果，即 $D_n = \lfloor n!/e + 1/2 \rfloor$ ，对一切 $n \ge 1$ 成立。

5 · 参考文献

Derangement. Wikipedia. 错排的容斥推导、两条递推与取整公式 $D_n = \lfloor n!/e + 1/2 \rfloor$ 。https://en.wikipedia.org/wiki/Derangement
Inclusion–exclusion principle. Wikipedia. 容斥原理的一般形式，错排是它最标准的应用。https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
Rencontres numbers. Wikipedia. 恰有 $k$ 个不动点的排列数，错排是 $k = 0$ 的那一列。https://en.wikipedia.org/wiki/Rencontres_numbers