错排问题详解：从递推公式到通项公式

1. 错排问题到底在说什么

先说一个几乎每本组合数学教材都会引用的故事：某人给五个朋友各写了一封信，又写了五个信封，结果装信的时候全部装错——每封信都没有装进对应朋友的信封。问一共有多少种装法？这就是经典的全错位排列问题，也叫错排问题。它研究的是一类“完全乱序”的排列：集合 {1,2,\dots,n} 的一个排列，要求每个元素都不待在原来的位置上，这样的排列数记作 D_n。

我第一次接触这个题，是在大学组合数学课上，老师用它来引出递推关系。当时觉得挺神奇：一个看起来要靠枚举的计数问题，居然能用几步递推解决，而且通项公式还能和自然常数 e 挂上钩。后来自己当博主、给学弟学妹讲题，越讲越觉得这个模型太重要了。它不光是考研、竞赛里的常客，在程序设计、密码学、洗牌算法、婚礼座位安排这些八竿子打不着的场景里，也经常以各种变形出现。

这篇文章，我就把错排问题从定义、递推公式到通项公式的推导过程一步步拆开讲清楚。全程用大白话，把每一步的“为什么”都补上，不需要你提前掌握多少高深数学，只要会排列组合的基本概念就能跟上。如果你正在准备考研数学、算法竞赛，或者纯粹想体会一下“从递推到封闭解”的数学美感，这篇文章都适合你。

2. 先从定义和最简单的几个值上手

2.1 形式化定义和符号约定

我们用 D_n 表示 n 个元素的错排数量，也就是集合 {1,2,\dots,n} 上满足“对任意 i 都有 \pi(i) \ne i”的排列 \pi 的个数。这里 \pi(i) 表示元素 i 在新排列里被放到第几个位置。条件 \pi(i) \ne i 就是“元素不回到原位置”。

举个具体例子。n=3 时，所有 6 个排列是：

123，132，213，231，312，321

其中满足每个数字都不在原位的只有 231 和 312 两个。所以 D_3 = 2。这个例子我建议你亲手写一遍，因为后面递推公式的第一步，就会用到这种“枚举元素去向”的思路。

2.2 先手动算出前几项找感觉

我们手动推一下 D_1 到 D_4，这对后续理解递推关系非常有帮助。

• D_1 = 0：只有一个元素，它没有第二个位置可去，必然在原位，所以错排数为 0。
• D_2 = 1：两个元素的排列只有 12、21，其中 21 是错排。
• D_3 = 2：上面已经数过。
• D_4 = 9：这个数字直接枚举也能数，但我们可以用后文要讲的递推公式验证。

把前几项写出来是：

这个序列看着没什么规律，但如果你算到 D_5=44、D_6=265，再回头对照 D_n 和阶乘 n! 的比值，就能发现一件有趣的事：D_n / n! 越来越接近 1/e ≈ 0.3679。这就是后面通项公式的伏笔。

3. 递推公式：两种思路，同一个结果

错排问题最经典的结论是递推公式：

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

这个公式的推导，网上有很多版本，有的写得很绕。我在这里给你拆成两种视角：一种是“从元素 1 的角度”去分类，另一种是“从排列总数里排除有不动点的情况”。两种方法都能推出同样的式子，但思路完全不同。我建议你至少掌握第一种，因为它在很多变形题里都能直接用。

3.1 从元素 1 出发的分类讨论

假设我们有 n 个元素，第 1 个元素不能待在位置 1。那么元素 1 只能去位置 2, 3, \dots, n，一共有 n-1 种选择。为了便于讨论，设元素 1 放在了位置 k（k \ne 1）。

现在关键的一步来了：看元素 k 放在了哪里。由于 k 的原位就是位置 k，所以有两种情况：

情况一：元素 k 恰好放在了位置 1。这样元素 1 和元素 k 互换，它们两个“互相成全”了对方的错排要求，剩下的 n-2 个元素只需要在它们自己的位置之间做错排，数量就是 D_{n-2}。因为 k 有 n-1 种选法，所以这一类的总数是 (n-1) \cdot D_{n-2}。

情况二：元素 k 没有放在位置 1。这时候我们把位置 1 视为元素 k 的“禁区”——因为它不能待在这里。而元素 1 和元素 k 以外的其他元素，各自仍然不能回到自己的原位。于是问题转化成了 n-1 个元素（把元素 1 和位置 k 这一对“绑定”成一个新元素，元素 k 和位置 1 绑定成另一个新元素）的全错排，数量是 D_{n-1}。同样因为 k 有 n-1 种选法，这一类的总数是 (n-1) \cdot D_{n-1}。

把两类加起来，就得到：

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

这个推导对初学者的难点，在于“情况二”里 n-1 个元素的错排是怎么来的。我再用更白话的方式描述一遍：我们把“元素 1 放到位置 k、元素 k 不能放到位置 1”这个约束，翻译成了一个新的错排问题——元素 1 不能去位置 1（原本约束）、元素 k 不能去位置 1（因为位置 1 已经被元素 1 占了？不对，这里要换个说法）。

其实更准确的理解是：在这个子问题里，我们把“元素 1”重新命名为“先不管它”，把“元素 k”和“位置 1”单独拿出来构成一对对应关系，使得“元素 k 不在位置 1”正好等价于新问题里的“某个元素不在它的对应位置”。这个对应就是错排问题的本质。如果你一下子没转过来，先记住结论，多套几个具体 n 值验证，慢慢就顺了。

3.2 用容斥思想验证递推公式

第二种思路是从“总数中排除不符合要求的情况”来看。n 个元素的全排列有 n! 个，错排是其中一种特殊情况。但用容斥原理直接计算 D_n，得到的是通项公式，不是递推关系。递推公式的另一种推导方式是利用“第一个元素的位置”结合“总数减去某个子集”的思想，但本质上还是第一步分类。

我在实际教学里发现，绝大部分学生卡住的点不是公式本身，而是理解不了为什么要分“元素 k 是否在位置 1”这两种情况。我给你一个更生活化的类比：想象一排座位，1 号座位是“猫”的专座，但现在猫必须换位置。猫去了 k 座。这时候要看 k 座的“原主人”去了哪里——如果它恰好占了猫的专座，那猫和它完成了一对一对换，剩下的人自己错排；如果它没有占猫的专座，那它也必须“无家可归”，和别的元素形成新的错排关系。这个“一看原主人去向”的思路，就是整个分类的核心。

3.3 另一个实用的递推形式：D_n = n \cdot D_{n-1} + (-1)^n

把刚才的公式稍微变个形，可以得到一个更便于计算的递推式：

D_n = n \cdot D_{n-1} + (-1)^n

这个式子怎么来的？由 D_n = (n-1)(D_{n-1} + D_{n-2})，展开整理：

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

而由原递推式替换 D_{n-1} = (n-2)(D_{n-2} + D_{n-3})，并不容易直接得到这个形式。更自然的证明是用通项公式或者数学归纳法。我们用归纳法快速验证：

已知 D_1 = 0，D_2 = 1。假设 D_{n-1} = (n-1) \cdot D_{n-2} + (-1)^{n-1}，则：

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

由假设，D_{n-2} = \frac{D_{n-1} - (-1)^{n-1}}{n-1}（n>2 时），代入得：

D_n = (n-1)D_{n-1} + D_{n-1} - (-1)^{n-1} = n \cdot D_{n-1} + (-1)^n

这个形式的好处是，做递推计算时只需要知道前一项，不用记住前两项。

用这个式子快速口算：

• D_3 = 3 \times 1 - 1 = 2
• D_4 = 4 \times 2 + 1 = 9
• D_5 = 5 \times 9 - 1 = 44
• D_6 = 6 \times 44 + 1 = 265

又方便又不容易错。这也是我平时给学生推荐的计算方式。

4. 通项公式的完整推导

递推公式适合计算，但不好直接看出 D_n 的量级，也不方便做渐进分析。要得到“封闭形式”，有两条经典路线：容斥原理和指数型母函数。母函数路线稍长，这里重点讲容斥原理，这也是绝大多数教材采用的方法。

4.1 把问题翻译成“没有不动点”

我们把一个排列看成集合 {1,2,\dots,n} 到自身的一个一一映射。位置 i 上的元素恰好等于 i，就叫做“不动点”。错排就是没有不动点的映射。

设 A_i 表示“元素 i 恰好待在原位置”这一事件（或者说集合）。那么“至少有一个元素在原位”对应的事件就是 A_1 \cup A_2 \cup \dots \cup A_n，而错排数 D_n 就是：

D_n = n! - |A_1 \cup A_2 \cup \dots \cup A_n|

用容斥原理展开并集的大小：

|A_1 \cup \dots \cup A_n| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|

其中，|A_i| 表示固定元素 i 在原位，其余 n-1 个元素任意排列，数量是 (n-1)!。同理，|A_i \cap A_j| = (n-2)!（固定两个元素），一般地，任意 k 个集合的交集大小为 (n-k)!。

一共有 \binom{n}{k} 个这样的交集，所以：

|A_1 \cup \dots \cup A_n| = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} (n-k)!

于是：

D_n = n! - \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} (n-k)!

把 n! 放进求和号里，注意到 \binom{n}{k}(n-k)! = \frac{n!}{k!}，得到：

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

这就是错排问题的通项公式。写完整一点：

D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!} \right)

4.2 通项公式快速验算

• n=3：3! \times (1 - 1 + 1/2 - 1/6) = 6 \times \frac{1}{3} = 2，对。
• n=4：24 \times (1 - 1 + 1/2 - 1/6 + 1/24) = 24 \times \frac{3}{8} = 9，对。
• n=5：120 \times (1 - 1 + 1/2 - 1/6 + 1/24 - 1/120) = 120 \times \frac{11}{30} = 44，对。

用公式手算时，我最常提醒自己的是：括号里的交错级数一定要写到第 n 项，少一项都会错，尤其是偶数 n 和奇数 n 最后一项的正负号不同。

4.3 和自然常数 e 的关系：为什么是 1/e

如果你熟悉 e^x 的泰勒展开 e^x = \sum_{k=0}^{\infty} x^k / k!，把 x = -1 代入，就得到 e^{-1} = 1 - 1 + 1/2! - 1/3! + \dots。

所以 D_n / n! 正好是 e^{-1} 的前 n+1 项截断。当 n 趋向无穷大时：

\frac{D_n}{n!} \to \frac{1}{e} \approx 0.367879

这就是为什么前面说 D_n 大约是 n! 的 36.8%。实际计算中，对于 n \ge 7，D_n 就是 n! / e 四舍五入到最接近整数，误差已经很小。这个性质在算法题里很有用，比如需要估算错排数量级、或者判断某个计数是否值得暴力枚举时，可以直接用 n!/e 做近似，误差在 1 以内。

4.4 用通项公式证明递推公式

有了通项公式，再回头验证递推公式就非常简洁了。由：

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

计算 n \cdot D_{n-1} + (-1)^n，展开后正好等于 D_n。这个过程不复杂，可以作为练习自己推一遍，能加深对两个公式关系的理解。我在专栏里经常强调：递推关系是“计算工具”，通项公式是“分析工具”，两者是等价的，但用起来各有各的顺手之处。

5. 常见的应用场景和变形

错排问题不是一道孤立的数学题，它经常会裹着各种外壳出现在不同领域。我挑几个高频场景，帮你建立“识别错排模型”的直觉。

5.1 经典“装错信封”及各类同构问题

除了装错信封，还有“五个同学参加聚会，进门把帽子放成一排，离开时每人拿了一顶不是自己的帽子，有多少种拿走方式”、“n 对夫妻跳舞，夫妻不共舞的组合有多少种”。这些场景本质完全一致，都是“n 个物体之间一一对应，但每个物体不能对应到自己原本的匹配对象”。考研数学和各类竞赛中出现的概率很高，识别方法就一句话：每个位置都有一个“禁位”，并且禁位互不相同。

5.2 部分错排：“恰好有 m 个不归位”

如果题目问的是“n 个元素排列后，恰好有 m 个元素回到原位（其余全部错排）”怎么办？这就变成先选出 m 个“回原位”的元素，剩下的 n-m 个元素做错排：

计数 = \binom{n}{m} \cdot D_{n-m}

比如“12 个人排队，恰好 3 个人站在自己原来的位置”，答案就是 \binom{12}{3} \cdot D_9。这个变形非常常考，因为你既要处理“定位”的步骤，又要处理“错排”的步骤，二者是一个乘法关系。

5.3 圆桌错排与桥牌中的错排

圆桌错排是另一个方向：n 个人围成一圈，每人不能坐自己原来的位置，有多少种坐法？这种问题和线性错排有相似之处，但因为有旋转对称性，推导要复杂一些，常见于组合数学的进阶内容。再比如桥牌发牌中“庄家没有拿到任何一张给定花色中的指定牌”这类问题，抽象出来也是错排的思路。这类问题在考试里较少出现，但一旦出现，往往会让只背公式的选手直接懵掉。我的建议是：先把线性错排吃透，再往圆桌、多重限制等方向扩展，不要一开始就贪多。

5.4 算法与程序中的错排

在写程序时，错排最常见的两个用途：

一是在密码学或随机化算法里，需要生成一个“没有固定点”的排列，比如某些洗牌算法要求每个人都不能拿到自己带来的物品。可以用错排的递推公式做概率分析，判断随机洗牌多少次才能得到满意的结果。

二是在动态规划或计数类算法题中，错排经常作为子问题出现。比如 LeetCode 上一些“所有人都不坐自己座位”的变种题，本质上就是 D_n。你需要快速写出递推方程，然后根据 n 的量级决定用 O(n) 递推还是 O(1) 通项公式。我在做算法题时，遇到这类题目，第一反应都是先把 D_n 的通项写出来，再用容斥或者递推去验证边界。

6. 常见误区与排查技巧

6.1 误区一：把 D_n 和 n! 的关系搞混

很多初学者会误以为 D_n = n! - 1（即只有原排列不行），或者 D_n = (n-1)!。这两种都是错的。正确的是 D_n / n! 的理论值约等于 1/e，不是 1 - 1/n，也不是 1/2。验证方法很简单：n=4 时 D_4=9，而 4! - 1 = 23，差异巨大。经典的排查手段是取 n=3、n=4 这样的小数代进去验算，如果公式给出的是整数且和枚举一致，通常就没问题。

6.2 误区二：递推公式的下标和初值搞错

D_1=0、D_2=1 这两个初值一旦搞错，后面全错。尤其是 D_1=0，看起来像废话，但在用程序写递推时，如果循环从 i=1 开始、初始值设错了，结果会偏得很厉害。我见过很多次有人把 D_0 也定义成 0，但按通项公式 D_0 = 1（空排列不算错排，但按公式规定），这在某些递推中会带来完全不一样的结果。更安全的做法是：统一按 D_0=1, D_1=0, D_2=1 来初始化，再套公式。

6.3 误区三：通项公式的符号错位

通项公式中的交错符号 (-1)^k，以及最后一项到底是加还是减，取决于 n 的奇偶。用容斥推导时，很多人在求和符号里丢项，或者把 \sum_{k=0}^n 写成 \sum_{k=1}^n，导致结果差一个 n!。我的排错技巧是：如果算出的 D_n 不是整数，或者 D_n / n! 大于 1，那一定是符号或者求和范围错了。

6.4 误区四：分不清“全错排”和“限制排列”

有一些题目虽然也有“禁位”，但禁位数不是 n 个，而是 m 个（m<n），或者禁位有重叠，这类题目不能直接套 D_n，需要重新建模。典型例子是“n 个男生、n 个女生排队，女生不能站在某个特定男生旁边”这类问题，禁位并不是“一一对应”的，计数模型完全不同。做题前先画一张简单的匹配图，确认“每个元素是否恰好有一个禁位”，再决定用不用错排公式。

结合我个人的刷题经验，我再分享一个通用排错流程：第一步，写出 n=1,2,3,4 的枚举结果；第二步，用递推公式计算同一组值；第三步，用通项公式计算同一组值；最后，三个结果比对，如果一致，公式和程序基本可信。这个方法我用了很多年，能过滤掉绝大多数粗心错误。

7. 一点点学习体会，送给你

这篇文章把错排问题从定义、递推公式到通项公式的完整推导过程都过了一遍，顺便介绍了几个常见变形和错坑点。我个人学组合数学的最大感受是：很多看似高深的结论，起点往往很简单——一个元素有几个选择？另一个元素又有几个选择？把它们分类讨论清楚，公式自然就长出来了。错排问题就是一个极好的例子，它既锻炼分类讨论能力，又展示了一一映射和容斥原理的威力。

如果你刚开始学，我建议你亲手完成三件事：第一，用枚举法列出 n=3 和 n=4 的所有错排，体会一下“结构”；第二，自己独立从“元素 1 放位置 k”开始推一遍递推公式；第三，用容斥原理推一遍通项公式，再把通项公式代入递推公式验证。这三步走完，你对错排问题的理解会超过绝大多数只背公式的人。

另外，你可能会在 B 站或知乎上看到各种组合数学课程，比如有些老师讲计数专题讲得特别细，像“排列组合与概率统计”这类课程一般都会专门讲错排。如果你偏好更系统的讲解，可以找 卢光辉 老师的组合数学课程来配合参考，他在计数问题上的板书推导非常仔细，适合巩固基础。不过看课只是辅助，最终还是要自己动笔推。数学这东西，光看不练，永远只是“看懂了”；动手推一遍，才叫“学会了”。