错位排列入门:装错信封问题与子阶乘 !n 怎么算

写好 n 封信,再写好 n 个信封,如果闭着眼睛把信塞进信封,要求每封信都没进对应的那个信封,一共有多少种塞法?这个问题在概率课本里叫装错信封问题,它的答案就是错位排列数,记作 !n,读作子阶乘 n。错位排列说的是一种排列:里面没有任何一个元素停在自己原来的位置上。下面把它的算法、规律和那个反直觉的 1/e 结论一次讲清楚。

什么是错位排列

把座位从 1 编到 n,重新安排所有人,让谁都不坐回自己原来的座位,这样得到的一个排列就是一个错位排列。关键词是"全部移位":只要有一个人没动,它就不算。

举 n = 3 的例子。1,2,3 这三个元素一共有 3! = 6 种排列,但其中只有 231 和 312 让每个数字都离开了自己的位置,所以 !3 = 2。剩下四个排列里,123 全员不动,132、213、321 各自至少留下一个元素在原位,都不符合要求。

错位排列在数学里也叫全错位排列,无不动点排列,对应的数列在 OEIS 里是 A000166,历史上又称 de Montmort 数或 rencontres 数。

递推公式:错排数怎么一步步算出来

手算错排数最顺手的是递推式:

!n =(n − 1)×(!(n − 1)+ !(n − 2)),基例 !0 = 1,!1 = 0。

这个式子的直觉是:第 n 个元素不能待在第 n 位,它有 (n − 1) 个落脚点;落定之后,剩下的部分要么是一个规模小一号的错位排列,要么是规模小两号的,合起来就是括号里那一项。

按它往上推,前几个错排数依次是:

!0 = 1,!1 = 0,!2 = 1,!3 = 2,!4 = 9,!5 = 44,!6 = 265,!7 = 1854,!8 = 14833。

很多人第一次看到 !1 = 0 会愣一下。道理其实简单:只有一个元素时,根本没有别的位置能挪过去,所以一种合法排法都没有,数目是零。而 !0 = 1 来自空积约定,空排列算作一种。

一个能验算的真实例子

拿四封信来试。!4 = 9,意思是四封信全部装错信封,正好有 9 种装法。你也可以自己列:把 1234 写成所有满足"每位都错"的排列,数一数,刚好九个。和阶乘对照一下,4! = 24 是四封信的全部装法,其中只有 9 种是全错的,剩下 15 种里至少有一封碰巧装对了。

我自己第一次手推这串数,是因为不信"只有一个元素时答案是 0"这件事,反复在草稿纸上摆了好几遍才认账。后来用工具一输 n 就能看到精确整数,省去了来回数的功夫,也帮我抓出过一次容斥求和里漏掉的符号。你可以直接打开 错位排列计算器,输入 n 看 !n 的精确值,再和手算对照。

为什么概率会趋近 1/e

错位排列还有一个闭式:

!n = n! ×(1 − 1/1! + 1/2! − 1/3! + … ±1/n!)

括号里那串交错和,正是 e 的负一次方级数的部分和。把两边同除以 n!,就得到随机打乱 n 个元素后没有一个落回原位的概率:

!n / n! = 1 − 1/1! + 1/2! − 1/3! + … ≈ 1/e ≈ 0.3679

这个级数收敛极快,到 n = 7 时,!n / n! 就已经四舍五入到 0.3679 了。换句话说,无论你洗一副 13 张、52 张还是 520 张的牌,没有任何一张回到起始位置的概率,都死死贴在 36.8% 附近,几乎和牌的数量无关。这正是装错信封问题和帽子寄存问题共享的那个反直觉答案。从形状上看,!n 就约等于 n! / e。

抽签:谁都不抽到自己

把这套数学搬到日常,最常见的就是礼物交换抽签。n 个人写好名字放进盒子,各抽一张,要求谁都不抽到自己的名字,合格的全抽方式数就是 !n,而随机抽一次正好合格的概率是 !n / n!。

对 8 个人的小组,工具会显示 8! = 40320 种抽法里有 !8 = 14833 种合格,约 36.8%。这意味着如果你的抽签程序"抽到自己就重抽",平均三次里就有一次直接过关,几乎不会卡很久。想把这套规则落到一次真实的抽签上,可以用 Secret Santa 抽签生成器 直接生成一份谁都不抽到自己的名单,省得自己写脚本去重试。

几个容易踩的坑

第一,别把 !n 和 n! 搞混。感叹号在 n 前面是子阶乘,在 n 后面是阶乘,!4 = 9 而 4! = 24,完全是两个数。第二,别想当然以为 !1 = 1,它其实是 0。第三,对大的 n 别用 n! / e 在表格里硬算再手动取整,位数一旦不够,n 超过 18 左右结果就会偏掉,在精确整数上跑递推才稳。

弄懂了错位排列,你就握住了装错信封、帽子寄存、洗牌不归位、抽签不撞自己这一整类问题的钥匙,而它们背后其实是同一个 1/e。

---

Made by Toolora · Updated 2026-06-13