把 n 个不重复的物体排好队，认定不难吧？就像你早上排队买豆浆，前面的人走完了，后面的人接着走，逻辑挺好办。但要是让你把这 n 个人随机分到 n 个座位上，要么把这 n 个物体重新排成一行，难度瞬间就上来了。
这就是经典的错排难题，也就是把 n 个元素全体打乱，没有任何两个按原来的位置不动，与此同时知足一个核心条件：每一个元素的“家”都不在原地。 想象你手里拿着一套西装，这套西装本来分给四个人穿，目前是随机分发，并且规定每个人都不能穿自己原本的那套。
要是 n 是 3 个人，原本 A 穿左胸，B 穿右胸，C 穿后背。错排就是 A 穿后背，B 穿左胸，C 穿右胸。
这时候只有 2 种可能的结局：A 穿后，B 穿左，C 穿右；要么 B 穿左，C 穿右，A 穿后。
哎，如何算出来是 2 种？ 数学上有个公式，跟阶乘有亲戚关系，但比阶乘多了一个除以 n 的运算。
那个公式叫 $D_n$，也就是错排数。直接背公式忒死板，咱们得看看它是如何来的，如何“活”过来的。 这就得靠一个看起来挺抽象的“大 n"来推演了。 当 n 是个特别大的数时，比如 n=4，这时候有个规律特别明显：错排数等于 $n-1$。
为啥？你能够这样想，你随意选一个人，把他和另一个人换一下位置，他就没法再回到原位了。
这就仿佛你扔出一个信封，里面写着“给张三”。你随机抓一个信封塞进去，张三肯定不是那个人。
这时候你手里剩下 3 个信封，相当于剩下 3 个人，新的错排数就是 3。 什么的，这是不是忒好办了？
是不是所有的 $n$ 都等于 $n-1$？显然不是。
那为啥大 n 会如此特殊，而小 n 又不一样呢？ 这就涉及到一个深层的逻辑：奇偶性。错排的本质是在元素之间建立“错位”关系。
这种错位越多，对整体排列的影响就越大。当 n 充足大时，一种巧妙的组合数学技巧能揭开面纱：把 $n$ 个元素分成两组，一组 $n-1$ 个，另一组 1 个。把那个“独眼”元素随意排一下，剩下的 $n-1$ 个元素，恰好就是我们要找的错排结构了，并且数量是 $(n-1)!$。 具体算一下 n=4 的情况： 1.选一个元素单独放，比如 C。 2.剩下 A 和 B 互换，那就是一种错排：A-B-C-D（这里实际上是 A 在第二位，B 在第一位，C 在第三位，D 在第四位，对应的是“奇偶排列”的一种特殊情况）。 3.实际上更严谨的理解是：固定那个单独的元素不动，看剩下 $n-1$ 个元素能排成多少种错排。对于 $n=4$，这相当于对 3 个元素做错排。 再回头看 $n=3$，公式得出来是 2。
如何来的？我们能够枚举一下： - A B C - A C B - B A C - B C A - C A B - C B A 全体排列有 6 种：ABC, ACB, BAC, BCA, CAB, CBA。 去掉 A-B-C 和 C-B-A 这种“相邻换”要么“彻底逆序”的情况？不对，错排的定义是不能有任意一个位置不变。 ABC：A 不动，B 不动，C 不动。
这显然不中。 BAC：A 不动，B 不动。
不中。 CAB：A 不动，C 不动。
不中。 CBA：B 不动，C 不动。
不中。 ACB：A 在 1，B 在 3，C 在 2。都没动。
不中。 BAC：A 在 2，B 在 1。B 动了，A 没动（不对，A 在 2，原在 1，A 动了）。
什么的，我刚刚的定义仿佛有点不清楚。 重新梳理定义：错排要求 $D_n = 0$ 意味着所有元素都务必 $i neq pi(i)$。 对于 $n=3$： - ABC: π(1)=1, π(2)=2, π(3)=3。全对。 - ACB: π(1)=1, π(3)=3。全对。 - BAC: π(2)=2, π(3)=1。π(2)=2。位置 2 的元素在位置 2。全对。 - BCA: π(3)=3, π(2)=1。π(3)=3。位置 3 的元素在位置 3。全对。 - CAB: π(1)=2, π(3)=3。π(3)=3。位置 3 的元素在位置 3。全对。 - CBA: π(2)=2, π(3)=1。π(2)=2。位置 2 的元素在位置 2。全对。 看来 $n=3$ 时，要是要求“任意位置都不动”，那实际上只有 2 种情况：CBA 和 CAB 这种？不对，CBA 是 B 在 2，A 在 3，C 在 1。位置 2 的元素是 B，原在 2。
故此 B 动了。
只有 CBA 和 CAB 这种？ 哦，我搞混了“位置不动”和“元素换”的概念。 标准的错排定义是：$D_n = n! sum_{i=0}^{n} frac{(-1)^i}{i!}$。 对于 $n=3$： $D_3 = 3! times (frac{1}{0!} - frac{1}{1!} + frac{1}{2!} - frac{1}{3!}) = 6 times (1 - 1 + 0.5 - 0.166...) = 6 times (0.333...) = 2$。 这 2 种情况是：CBA, CAB。 让我们验证一下 CBA： 位置 1 是 C（原位置 3，移动了）。 位置 2 是 B（原位置 2，没动）。 位置 3 是 A（原位置 1，移动了）。 哎，B 在位置 2，原在位置 2。
那这算错排吗？不算！错排要求没有任何一个元素在原位。 故此 CBA 是错的。
那为啥公式算出来是 2？ 公式算的是“彻底错排”（derangement），也就是所有位置都不对。 CBA：位置 2 的元素在位置 2。
这是全同排列的一种。 故此 CBA 不应当被计入。 那剩下的 CAB： 位置 1 是 C（原 3，动）。 位置 2 是 A（原 1，动）。 位置 3 是 B（原 2，动）。 全都在动！
这是对的。 那另一个 CBA 呢？ 位置 1 是 C（原 3，动）。 位置 2 是 B（原 2，不动）。 位置 3 是 A（原 1，动）。 这实际上也是全在动！不对，位置 2 的 B 是在位置 2，可是元素 B 本来在位置 2，只是顺序变了？ 啊，我混了“元素”和“位置”。 元素 B 原在位置 2。 在 CBA 中，元素 B 到了位置 2。 故此 CBA 中，元素 B 在原位。 那为啥 $D_3$ 是 2？
难道我的理解还是错了？ 让我查一下标准定义的标准定义。 错排（Derangement）：将 n 个元素排成 $n$ 个位置，使得没有元素留在原来的位置上。 对于 n=3： ABC: 1->1, 2->2, 3->3.(全同) ACB: 1->1, 3->3.(1 和 3 不动) 不中。 BAC: 2->2.(2 不动) 不中。 BCA: 3->3.(3 不动) 不中。 CAB: 1->2, 2->3, 3->1.(1,2,3 全动). OK. CBA: 2->2.(2 不动) 不中。 故此只有 CAB 一种？ 不对，C 和 B 互换，A 不动。 那再试一个： A 在 2，B 在 3，C 在 1。 这就是 CAB。 还有没有别的？ A 在 3，B 在 2，C 在 1。 C 在 1，B 在 2，A 在 3。 这是 CBA。 B 在 2，A 在 3，C 在 1。 B 在 2，A 在 3，C 在 1。 是的，只有 CAB 和 CBA 这两种全动？ 不对，CBA 中 B 在 2，A 在 3，C 在 1。 位置 1: C (原 3). 位置 2: B (原 2). -> 停留了。 位置 3: A (原 1). 故此 CBA 不是错排。 那只有 CAB 吗？ 再试一个： 位置 1: B, 位置 2: C, 位置 3: A. B 在 1 (原 2). OK. C 在 2 (原 3). OK. A 在 3 (原 1). OK. 这是 BCA。 检查位置： 位置 1: B (原 2). 位置 2: C (原 3). 位置 3: A (原 1). 所有位置都不对。 那还有没有其他的？ A 务必在 2 或 3。 要是 A 在 2：那么 1 和 3 务必是 B 和 C。 情况 1: 1=B, 3=C. -> B 在 1, C 在 3, A 在 2.(BCA) 情况 2: 1=C, 3=B. -> C 在 1, B 在 3, A 在 2.(CBA) 这里 B 在 3 (原 2), C 在 1 (原 3). 全对。 哦，CBA 中 B 在 3，A 在 2，C 在 1。 位置 1: C. 原 3.OK. 位置 2: A. 原 1.OK. 位置 3: B. 原 2.OK. 故此 CBA 是错排。 那 BCA 呢？ 位置 1: B. 原 2.OK. 位置 2: C. 原 3.OK. 位置 3: A. 原 1.OK. 故此 BCA 也是错排。 那 ABC, ACB, BAC, BCA, CAB, CBA。 全错排的是：CBA, BCA。 一共 2 种。 确实 $D_3 = 2$。 那为啥我认定公式里的 $n-1$ 是 $n=3$ 时是 2？对了，$3-1=2$。 那啥时候 $D_n = n-1$？ 当 $n=4$ 时，$D_4 = 9$。$4-1=3$。
不相等。 故此大 n 不等于 $n-1$。 那之前的公式推导哪儿错了？ 啊，之前的推导是：把 $n$ 个元素分成 $n-1$ 个和 1 个。 要是那个单独的元素是固定的，剩下的 $n-1$ 个元素做错排，那就是 $(n-1)!$。 这实际上是错排的一个分支，但并不是所有的错排都是这样的。 $n=4$ 时，总共有 9 种。 单独元素固定的那一类是 $(4-1)! = 6$ 种。 剩下的 3 种呢？ 是那些“局部移动”的类型。 比如 A 和 B 互换，C 和 D 互换。 C D A B C B D A C B A D 这是 3 种。 加上 A 单独不动？不中，错排要求全动。 故此 $D_4 = 6 + 3 = 9$。 看 $D_4$ 的公式：$24 times (1 - 1 + 0.5 - 0.166 + 0.0416) = 24 times 0.375 = 9$。 确实是对的。 那为啥之前我认定 $n-1$ 是对的？ 出于那是 $n=1$ 和 $n=2$ 的特例扩展。 对于 $n=3$，$D_3 = 2$。 对于 $n=4$，$D_4 = 9$。 对于 $n=5$，$D_5 = 44$。 序列是 1, 2, 2, 9, 44, ... 没有好办的 $n-1$ 规律。 故此之前那段“大 n 等于 n-1"的描述务必修正。 那目前如何讲清楚呢？ 不要讲公式推导过程，忒枯燥。 要讲“为啥”和“如何算”。 能够拿 $n=4$ 举例，$D_4=9$。 解释：所有情况中，有一种“全错”的情况，有 6 种是“两两互换”的情况，还有 3 种是“局部错”。 这正好把 9 分成了两局部。 这比直接背公式好玩多了。 并且能够引入“奇偶排列”的概念。 $D_n$ 实际上就是奇偶排列数 $E_n$。 对于 $n=4$，奇偶排列 7 种，偶数排列 2 种。 $D_4 = 9$。 这中间有点乱，还是别强行扯出奇偶性，要不就是为了解释公式的系数。 公式的系数 $1/(n-1)!$ 实际上暗示了啥？ 实际上公式能够写成 $D_n = n! sum_{k=0}^{n} frac{(-1)^k}{k!}$。 这实际上是个泰勒级数，跟 $(e - 1)^n$ 有点像。 $e approx 2.718$。 当 $n$ 挺大时，$frac{(-1)^k}{k!}$ 的绝对值加起来趋近于 $1/e$。 故此 $D_n approx n! times frac{1}{e}$。 也就是错排数大约是 $e$ 的倒数乘以全排列数。 全排列 $n!$ 增长极快。除以 $e$ 略微快一点点。 这就解释了为啥错排数不会到 $n!/2$（过半数），也不会到 0。 它一辈子在 $n!/e$ 附近徘徊。 那 $n=4$ 时，$D_4 approx 24/2.718 approx 8.8$。 哦！原来 $e$ 的倒数！ 这就是那个神秘的 $1/e$ 因子。 它让错排数在 $n!$ 的 $1/e$ 倍附近。 这就把“抵制称”和“对称”联系起来了。 全排列是 $n!$。 错排是“不彻底对称”的。 它不是好办的 $n!/2$，也不是 $n!/e^2$。 它是 $n! times (1 - 1/e + 1/(2e^2) - dots)$。 当 $n$ 挺大时，这个级数收敛得挺快。 故此 $D_n approx n! / e$。 这个近似值对于 $n$ 大的时候贼有参考价值。 那对于一般的 $n$，如何具体计算？ 要是 $n$ 不是特别大，就用公式。 要是 $n$ 挺小，就枚举。 要是 $n$ 挺大，就用近似。 实际上有一个递推公式：$D_n = (n-1) (D_{n-1} + D_{n-2})$。 这个递推式挺像斐波那契数列。 $D_4 = 3 times (D_3 + D_2) = 3 times (2 + 1) = 9$。 $D_5 = 4 times (9 + 2) = 44$。 $D_6 = 5 times (44 + 9) = 265$。 这个递推式是如何来的？ 这实际上是插队难题的模型。 想象有一排座位，第一排是 $n-1$ 个，第二排是 1 个。 把那个单独的人插进去，有 $n-1$ 个位置可选。 要是他插在“下一个人后面”的某个位置，那么原来的那个“第一排”就变成一个新的错排难题（大小 $n-1$）。 要是他插在“上一个人后面”的某个位置，那么原来的“第一排”就变成一个新的错排难题（大小 $n-2$）。 这就导出了 $(n-1)(D_{n-1} + D_{n-2})$。 这个递推式贼漂亮，也体现了错排结构的深层逻辑。 它把 $n$ 维的错排难题，转化成了 $(n-1)$ 维和 $(n-2)$ 维小难题的组合。 那对于 $n
