聊组合数学绕不开错排问题。n个人交换礼物最后谁也没拿到自己的礼物这样的分配方式一共有多少种经典的递推公式D(n)(n-1)(D(n-1)D(n-2))大家应该都见过但它到底怎么推出来的通项公式为什么是n!Σ(-1)^k/k!今天我一次讲透顺便把竞赛和算法题里经常踩的坑也一起说了。这篇文章适合准备算法竞赛、考研复试、期末考试的读者也适合单纯想搞明白“为什么错排概率趋近于1/e”的好奇派。我会从定义、递推、通项一路推到落地实现每一步都给出能复现的推理过程而不是扔一个公式让你死记。1. 全错位是什么帽子问题、定义与边界条件1.1 一个帽子问题引出的概念假设有n个人参加聚会进门时把各自的帽子挂在衣帽架上。离开时每人随手拿一顶帽子问有多少种拿法能让所有人都拿到别人的帽子这就是“全错位排列”也叫derangement记作D(n)有些教材里写成!n读作subfactorial。严格定义是这样的1到n的一个排列a₁, a₂, ..., aₙ如果对每一个i都满足aᵢ≠i也就是说没有任何一个数字停留在它原本的位置上那么这个排列就叫错排。比如n3时123的全排列里只有231和312是错排231表示1跑到2号位、2跑到3号位、3跑到1号位312表示1跑到3号位、3跑到2号位、2跑到1号位。这个“没有元素留在原位”的条件看起来很简单但数起来会迅速爆炸。n3只有2种n4变成9种n5直接到44种。手算很快到头必须找到规律。错排问题在组合数学里的地位很特殊它几乎无处不在信封与信、帽子与主人、抽签互送礼物、甚至密码学里的某些排列约束都能抽象成这个模型。1.2 边界值为什么规定D(0)1很多初学者第一个卡住的地方就是D(0)。个子阶乘表格一般长这样n012345678D(n)1012944265185414833D(1)0很好理解唯一一个元素摆在唯一的位置上不可能错。D(2)1也好理解两个元素互换位置只有一种错排。但D(0)1是什么意思0个元素的排列只有“空排列”这一种而这个空排列里没有任何元素待在原位所以它满足错排条件记作1。这个约定不是拍脑袋定的。一方面通项公式在n0时自然给出1另一方面递推公式D(2)(2-1)(D(1)D(0))要成立就必须有D(0)1。如果你强行把D(0)定义成0后面D(2)会算成0整条链全崩。记住D(0)1不是直觉问题是数学内部一致性的要求。1.3 置换视角把错排看成无不动点的映射排列可以看成集合{1,2,...,n}到自身的一个一一映射。一个排列π有不动点就是指存在某个i使得π(i)i。错排就是这个映射没有任何不动点。这种视角在后续推导里很有用尤其在容斥原理那一步因为我们要讨论的“第i个元素留在原位”本质上就是“置换π满足π(i)i”也就是i是不动点。于是错排问题等价于统计无不动点的置换个数。从图论角度看一个置换可以分解成若干循环错排就是不允许出现长度为1的循环。这个理解方式在n4时很直观24个置换里含有1-循环的全部剔除剩下的就是错排。后面讲递推公式时这个“循环分解”的想法也能帮你验证答案。2. 递推公式怎么来的从“n号元素去哪了”分两枝2.1 核心思想抓住第n个元素的位置递推公式D(n)(n-1)(D(n-1)D(n-2))是错排问题最常用的公式但很多人只会背不会推。推导的关键是盯住“数字n最后放到了哪个位置”。数字n不能放在位置n所以它有n-1个选择。假设n放到了位置k其中k∈{1,2,...,n-1}。现在数字k就被挤出来了它有两个去向这两个去向对应两种完全不同的子问题情况一数字k正好放在位置n。这时候数字n和k互换了位置形成了一个长度2的循环。剩下的n-2个数字在剩下的n-2个位置上必须全部错排所以方案数是D(n-2)。情况二数字k没有放在位置n。这意味着k被n抢了位置但k又不去n的位置于是k也要“去一个不属于自己的位置”。把数字n和位置n同时从问题里删掉后数字k的“禁位”就变成了原来的位置n其他数字的禁位还是各自的原位。整个系统等价于一个规模为n-1的错排问题方案数是D(n-1)。因为数字n挑位置k有n-1种选择而每种选择下两种情况互斥且全覆盖所以D(n)(n-1)[D(n-2)D(n-1)]2.2 为什么不是简单的D(n)(n-1)D(n-1)初学者最容易犯的错误是以为“n去一个别的位置剩下n-1个人错排”于是写成D(n)(n-1)D(n-1)。这个思路忽略了那个“被抢位置的人”之后怎么办。打个比方n去占了k的座位此时k不能坐原位但也不一定非要去坐n的座位。如果k直接坐n的位子那这两个人是两两交换其余人错排是D(n-2)如果k不去n的位子那k就和其余人一起陷入一个n-1规模的错排是D(n-1)。两种可能都存在不能只取一种。为了验证这个分类没有遗漏可以检查n4的枚举结果。用递推公式算D(4)3×(D(3)D(2))3×(21)9。实际枚举四个元素的全排列符合“没有人待在自己位置”的确实正好9个2143、2341、2413、3142、3412、3421、4123、4312、4321。一个不多一个不少。2.3 另一种等价推导从“排列中有没有2-循环”去理解如果你熟悉置换的循环分解上面两种情况其实对应“数字n参与的循环长度是2”和“数字n参与的循环长度大于2”。n-1种方式选择k如果k和n构成一个2-循环剩n-2个元素全错排是D(n-2)。如果k不在n的位置上相当于把k合并进了一个更大的循环剩下的n-1个元素错排是D(n-1)。这两种理解殊途同归。我个人更喜欢第一种“抢座位”的讲法因为它不需要你事先知道循环分解的概念在考场上也最容易现场推出来。3. 通项公式推导容斥原理一次到位3.1 全集、坏事件与容斥雏形递推公式虽然好用但D(n)依赖前两项必须从头算起。如果想知道D(100)哪怕用递推也要循环100次。通项公式的价值在于直接给出闭式就算不用于计算也能让我们看到错排数和阶乘之间的本质联系。推导通项公式最干净的方法就是容斥原理。我们考虑所有n!个排列要排除掉“至少有一个元素在原本位置”的排列。记事件Aᵢ为“第i个元素停在位置i”那么全错排就是不属于任何Aᵢ的排列数量为D(n)n!-|A₁∪A₂∪...∪Aₙ|容斥原理告诉我们并集的大小等于所有单项事件大小之和减去两两交集之和加上三三交集之和依此类推正负交替。3.2 每个交集大小都是(n-k)!关键在于组合数现在关键是计算任意k个事件同时发生的交集大小。例如A₁∩A₂∩A₄意思是第1、2、4个元素都停在原位其余元素完全不管。那么第1、2、4这三个位置已经固定了是1、2、4剩下的n-3个元素任意排列所以数量是(n-3)!。推广到一般情况任意选k个下标这k个元素停在原位其余n-k个元素任意排数量永远是(n-k)!。由于从n个下标里选出k个共有C(n,k)种方式所以“恰有这k个元素在原位”的排列总数是C(n,k)×(n-k)! n!/k!最后那个等号很关键C(n,k)×(n-k)! n! / (k!×(n-k)!) × (n-k)! n!/k!。正是这个化简让后面的公式变得异常优雅。3.3 写出通项公式把容斥原理完整展开D(n)∑_{k0}^{n} (-1)^k × [所有k个不动点的排列数] ∑_{k0}^{n} (-1)^k × C(n,k) × (n-k)! ∑_{k0}^{n} (-1)^k × n! / k! n! × (1 - 1/1! 1/2! - 1/3! ... (-1)^n/n!)这就是错排问题的通项公式。它的结构非常漂亮前面是n的阶乘后面是1/e的泰勒展开前n1项。注意k0时对应“0个元素固定位置”的情况贡献是C(n,0)×n!n!这正好是全集大小。所以公式里的k0项不是多余的它是容斥展开的起点。3.4 和递推公式互相印证用通项公式算一下n55!120后面那串求和是1-11/2-1/61/24-1/12044/120乘起来正好是44。这和递推公式D(5)4×(D(4)D(3))4×(92)44完全一致。更妙的是这个公式在n0时给出1在n1时给出0自动覆盖了边界条件。递推公式和通项公式不是互相孤立的它们可以从对方推导出来后面第4部分会展示其中一条路。3.5 一个极其好用的推论D(n)是最接近n!/e的整数注意到∑_{k0}^{∞}(-1)^k/k! e^{-1}所以D(n)n!×e^{-1}会有一个很小的尾项误差。具体地说D(n) round(n! / e)这里round表示四舍五入到最接近的整数。原因是交错级数的误差小于被丢掉的第一项1/(n1)!这个误差相对于n!来说微乎其微永远不会大到改变四舍五入方向。这个性质在估算和验算时特别好用。比如n66!/e≈264.87四舍五入得到265与表格一致。我在做题时经常先用这个式子估一个模再核对递推结果能抓出一大半低级错误。4. 通往通项的另外两条路比值递推与生成函数4.1 从二阶递推化出一阶递推有递推公式D(n)(n-1)(D(n-1)D(n-2))能不能直接推出通项可以。先做一个辅助数列F(n)D(n)-nD(n-1)然后把二阶递推代进去F(n)(n-1)(D(n-1)D(n-2))-nD(n-1) -D(n-1)(n-1)D(n-2) -[D(n-1)-(n-1)D(n-2)] -F(n-1)也就是说F(n) -F(n-1)。初始值F(1)D(1)-D(0)0-1-1所以F(n)(-1)^n。于是得到一个一阶递推式D(n)nD(n-1)(-1)^n这个形式比二阶递推更适合编程也更容易通向通项。注意这里的(-1)^n就是那个“正负交替”的修正项它反映了错排数在n!周围波动的现象。4.2 两边除以n!再累加通项自然浮出把D(n)nD(n-1)(-1)^n两边同时除以n!D(n)/n! D(n-1)/(n-1)! (-1)^n/n!令S(n)D(n)/n!就得到相邻两项的差S(n)-S(n-1)(-1)^n/n!从n2一直累加到nNS(N)-S(1)∑_{k2}^{N}(-1)^k/k!因为S(1)D(1)/1!0所以D(N)/N! ∑_{k2}^{N}(-1)^k/k!注意到∑_{k0}^{N}(-1)^k/k! 1-1∑_{k2}^{N}∑_{k2}^{N}因此D(N)/N! ∑_{k0}^{N}(-1)^k/k!这就又一次得到了通项公式。整个推导只需要代数操作不需要背容斥原理的复杂逻辑适合在考场上临时回忆。4.3 指数生成函数的“高级视角”如果你对生成函数有了解还可以用指数生成函数在两步之内得到通项。定义E(x)∑_{n0}^{∞}D(n)x^n/n!利用一阶递推D(n)nD(n-1)(-1)^n两边乘以x^n/n!并对n≥1求和。左边等于E(x)-1右边第一项等于xE(x)第二项等于e^{-x}-1。整理得E(x)-1xE(x)e^{-x}-1于是(1-x)E(x)e^{-x}即E(x)e^{-x}/(1-x)把右边的函数展开成幂级数x^n的系数恰好是∑_{k0}^{n}(-1)^k/k!再乘上n!就得到D(n)。这个角度揭示了错排数为什么和e有这么深的渊源——指数母函数里天然带着阶乘倒数。当然生成函数对初学者可能有点抽象。如果你暂时不熟悉跳过这一节不影响后续阅读。只要知道“错排数的本质是e^{-x}/(1-x)的指数生成函数系数”这个事实等你学到生成函数时自然会觉得亲切。4.4 三条路线的对比总结路线优点缺点适用场景递推公式简单、稳定、适合编程要知道前两项无法直接算大n算法题、竞赛代码容斥原理逻辑清晰一步到位需要排列组合基础笔试推导、教学设计比值累加从递推自然过渡到通项中间步骤略绕理解递推与通项关系指数生成函数最深刻看到全局门槛高概念多进阶组合数学学习我个人最推荐理解顺序是先掌握“抢座位”推出递推再用容斥推通项最后用比值累加把两者串起来。生成函数作为加分项学有余力再掌握。5. 落到代码与试卷取模实现、边界处理和经典错法5.1 竞赛题里最常见的错排题型错排很少单独考它通常会和组合数嵌套。最经典的考法是“n个人恰好有k个人拿到自己的帽子或者停在原位有多少种方案”答案是C(n,k)×D(n-k)。思路分两步先选出哪k个人是幸运儿有C(n,k)种选法剩下n-k个人的帽子必须全部错开有D(n-k)种方案。两件事独立相乘收工。另一种常见考法是“至少有一个人拿到自己的帽子”答案用补集n!-D(n)。还有变体比如“第i个人不能坐第i个座位”本质就是错排再叠加其他限制条件时通常先处理其他约束最后单独处理错排部分。我在牛客和力扣上见过不少这类题模式感很强识别出“不允许任何元素待在原位”之后剩下的就是套公式。5.2 取模递推的Python实现实际竞赛中n通常很大答案要模一个素数MOD。递推公式实现起来最稳MOD 10**9 7 def derangement(n: int) - int: if n 0: return 1 # d0 表示 D(i-2)d1 表示 D(i-1) d0, d1 1, 0 for i in range(2, n 1): d0, d1 d1, (i - 1) * (d0 d1) % MOD return d1注意循环里同时更新d0和d1右边的d0和d1都是旧值Python会先算完右边再赋值所以不会出现脏数据。如果换用C记得把中间乘积转成long long否则(i-1)*(d0d1)在n一大时会溢出int。这里还有一个小坑如果n1直接返回d10如果n0也要单独返回1。千万别把n0漏掉否则边界值就错了。5.3 用通项公式做模运算阶乘逆元路线通项公式里有除以阶乘的项在整数域上直接用会得到浮点数在取模环境下就必须用逆元。如果模数是素数费马小定理给出逆元a^{-1} ≡ a^{MOD-2} (mod MOD)。实现如下def derangement_mod(n: int, mod: int) - int: # 预处理阶乘和阶乘逆元 fact [1] * (n 1) for i in range(1, n 1): fact[i] fact[i - 1] * i % mod inv_fact [1] * (n 1) inv_fact[n] pow(fact[n], mod - 2, mod) for i in range(n, 0, -1): inv_fact[i - 1] inv_fact[i] * i % mod total 0 for k in range(n 1): term inv_fact[k] if k 1: total (total - term) % mod else: total (total term) % mod return fact[n] * total % mod这个实现的好处是当你需要C(n,k)×D(n-k)这种组合表达式时阶乘和逆元都预处理好了直接复用。缺点是代码比递推长。通常我建议如果题目只需要D(n)用递推如果题目还要频繁算组合数就预处理阶乘和逆元顺带用通项公式算错排。5.4 高频错误对照表错误操作后果正确做法把D(0)初始化为0D(2)算成0全线崩溃D(0)1单独处理n0递推时只取模不加MOD减法可能产生负数结果加上MOD再取模用double算n!/e直接取整n≥20时浮点精度不足改用递推或模逆元把“恰好k个人原位”写成D(k)×D(n-k)漏了选人的组合数先C(n,k)选出原位者再D(n-k)忘了通项公式的k从0开始丢掉了全集n!这一项k从0到n求和第4条是我见过最频繁的错误。很多同学知道错排后一看到“恰好k个”就直接套错排完全忘了还要从n个人里选出这k个幸运儿。做题时先写“C(n,k)”再乘“D(n-k)”逻辑自然就顺了。6. 错排的变体、概率直觉与应用场景6.1 部分错排不是所有人都不在原点比全错排更一般的问题是n个元素里恰好有k个不在原位。这个数记为P(n,k)它等于C(n,k)×D(n-k)。你先决定哪k个元素“参与”错排剩下n-k个元素老老实实待在原位。注意这里的角色分配和上一节“恰好k个人原位”是对称的上面是“原位k个错排n-k个”这里是“错排k个原位n-k个”本质相同使用时别搞反。还有一类问题是“至少k个不在原位”那就需要分段求和P(n,k)P(n,k1)...P(n,n)。这种类型在概率题里很常见比如“全班40个人随机换礼物至少30个人拿到别人礼物的概率是多少”。到这一步组合数学的工具就开始真正发挥作用了。6.2 意外而稳定的概率约等于1/e随机生成一个n个元素的排列它是错排的概率是D(n)/n!。用通项公式看D(n)/n! ∑_{k0}^{n}(-1)^k/k! → e^{-1} ≈ 0.3679也就是说不管n多大随机排列中“没有任何人待在原位”的概率都稳定在36.8%左右。这个结论违反不少人的直觉——n很大的时候大家会觉得“所有人都错开”应该越来越难但实际上它收敛到一个不为0的常数。这个性质在现实中有很直接的应用。比如n个人玩“秘密圣诞老人”抽签约定不能抽到自己如果完全随机抽每次大约有36.8%的概率一次成功其余63.2%的概率需要重新抽。知道这个概率后你就能估计重试次数期望约1/0.368≈2.72次这本质上又是一个e的化身。6.3 生活中的错排模型从换礼物到出题除了抽签换礼物错排还藏在很多场景里老师把n份试卷混合后随机发回给学生没有学生拿到自己试卷的概率约36.8%。餐厅寄存的雨伞随机归还所有人都拿错的概率同样是约36.8%。某些随机洗牌算法要求结果里没有元素留在原位比如为了避免连续重复轮换这时候就相当于生成一个随机错排。工程上真要生成一个均匀随机的错排常见做法是先均匀生成一个随机排列如果它恰好是错排就保留否则重新生成。因为成功概率是常数1/e所以期望重试次数只有约2.72次效率完全可接受。这个思路被很多抽签小程序用到代码写起来也很简单。6.4 圆桌上的错排与禁位排列如果再加一个限制问题就会变得非常棘手。比如n个人围成一圈要求每个人不能坐在自己的原座位这看起来像“圆错排”但圆对称性让计数变得复杂没有一个像线性错排那样简洁的闭式公式。更特别的“夫妻入座问题”ménage problem甚至还需要容斥加积分表示。这些进阶变体说明一个道理错排的简单性非常依赖“全排列”和“全禁位”的对称结构。一旦破坏对称性同样的直觉往往不再适用谨慎起见不要在考试时想当然地把D(n)套进圆排列或其他带额外约束的场景。我在实际做题中还有一个习惯遇到错排题型先写下基础公式D(n)n!Σ(-1)^k/k!再写下递推式D(n)(n-1)(D(n-1)D(n-2))两边一对照基本能确认自己的推导没有串味。如果时间紧张用D(n)≈n!/e做估算也能快速排除明显不合理的选项。这套“定义-递推-通项-实现-变体”的链条把错排问题每个层面都过了一遍。下次再看到这类题希望你能先想到“n号元素去了谁的位置”而不是对着公式发愣。如果还想深入可以试试把指数生成函数的方法用到“恰好k个不动点”的计数上那里还有不少值得琢磨的展开。