错排公式

定义

错排研究的是这样一类排列：把 n 个元素重新排序后，任何一个元素都没有停在它原先占据的位置上，也就是整个排列不含不动点^[1]。满足这一条件的排列叫作错排，也译作更列，其个数称为错排数。

错排数用 D(n) 表示，另有 Dn、dn、!n 等写法，在文献中亦称次阶乘或德·蒙特莫特数^[1]。以 4 个元素为例，全排列共有 24 种，其中符合要求的错排只有 9 种^[2]。错排公式就是刻画这一数量的递推式与通项式。

原理

错排数之间满足递推关系 $D(n)=(n-1)(D(n-1)+D(n-2))$，初始值为 $D(1)=0$、$D(2)=1$。推导的思路是先安置第 n 个元素，由于它不能回到原位，可选的落点共有 n-1 个^[3]。接着考察原本位于该落点的那个元素：若两者互换位置，则余下 n-2 个元素构成错排，有 $D(n-2)$ 种；若该元素没有进入第 n 位，问题就等同于 n-1 个元素的错排，有 $D(n-1)$ 种。两类情形相加再乘以 n-1，即得到上述递推式^[4]。

通项公式可由容斥原理推出：先从 n! 个全排列中扣去至少有一个元素在原位的排列，再补回至少有两个元素在原位的排列，如此正负交替，得到 $D(n)=n!\sum_{k=0}^{n}(-1)^k/k!$^[5]。求和号内的式子正是 e 的负一次方幂级数的前 n+1 项，所以错排数约等于 n! 除以 e^[5]。更严格地说，D(n) 等于 n!/e 取最接近整数所得的值^[2]。

依次计算可得前几项错排数为 0、1、2、9、44、265、1854、14833，与逐一枚举的结果一致^[2]。若把 n 个元素随机打乱，结果恰好是错排的概率为 D(n)/n!，它随 n 增大迅速趋近 1/e，约等于 0.3679^[6]。随机排列中留在原位的元素个数则近似服从均值为 1 的泊松分布^[6]。

发展历程

错排问题在 18 世纪进入数学家的视野。德·蒙特莫特于 1708 年提出该问题，并在 1713 年给出解答^[2][1]。尼古拉·伯努利大约在同一时期用容斥原理也解决了它^[2]。欧拉后来对这一计数问题产生兴趣，并把它称作组合数学中的一个奇妙问题。由于这些早期工作，错排问题在历史上又称伯努利-欧拉装错信封问题。

欧拉在 1779 年前后通过计数论证写下 D(n) 的表达式，而棣莫弗在此前若干年已得到相同结果^[7]。该表达式即 $D(n)=n!(1-1/1!+1/2!-\cdots+(-1)^n/n!)$，也就是后来通行的错排公式^[7]。此后，错排问题成为组合计数中运用容斥原理与递推方法的典型教学范例^[8]。

应用

错排公式最典型的用途是解决装错信封问题：若 n 封信分别写给 n 个不同的人，问全部装错信封的装法有多少种，答案就是 D(n)^[8]。贺年卡互赠属于同一模型，每张卡由他人收到，自己写的那张不能落到自己手中。学生之间交换试卷批改、聚会中随机取伞而无人取回自己的物品，同样可以化为错排计数^[2]。

在考试测评中，错位重排的常用结论被用于快速作答相关的排列组合题目。在计算机科学里，错排对应不含不动点的置换，可用于构造随机置换，研究者还提出了借助卡片协议均匀生成随机错排的方法^[9]。错排概念也出现在概率论与统计物理等领域的问题中^[6]。

局限

错排公式直接给出的只是「一个都不在原位」这一种情形的数目；若要统计恰好有 k 个元素保持原位的情况，还需另行作组合分析^[6]。通项公式是一个含 n 项的阶乘倒数交错和，n 很大时逐项计算并不方便，通常改用 n!/e 取最接近整数的近似式。

元素个数较少时可以把排列逐一列出核对，但这一办法随 n 增长很快失去可行性，只能依靠递推关系或通项公式^[3]。此外，错排公式处理的是禁止位置恰好构成对角线的排列计数；遇到禁止位置更一般的排列问题，需要借助棋盘多项式或更一般的容斥计算^[8]。

参见

• 容斥原理 —— 由它可以直接导出错排数的通项公式。

• 排列 —— 错排是排列中不含不动点的一类。

• 不动点 —— 错排的定义要求排列没有不动点。

• 德·蒙特莫特 —— 最早提出并解决错排问题的数学家。

• 组合数学 —— 错排问题是其中的经典计数问题。