错排问题 · Derangement

帽子错配

一群人各自随机取走一顶帽子，恰好没有人拿到自己那一顶——这个「完美错配」的概率究竟是多少？它和那个著名的常数 1/e 之间，到底是什么关系？

§

游戏规则

  • 目标随机把帽子发回给 n 个人，统计「恰好无人拿到自己帽子」的完美错配局数。
  • 操作点「开始一局」发帽，逐一点击人物或「揭晓全部帽子」查看帽子颜色与匹配。
  • 判定帽子与衣服同色算「匹配」；0 匹配返还你填写的奖励，否则每匹配成功 1 人返还 5 筹码，每局支付 10 筹码。
  • 提示先填写奖励，再用最多 50 局观察盈亏；重新开始一组时恢复 100 筹码。
实验画面

🎩 帽子错配 · 错排实验

每个人随机拿一顶帽子——多少人拿错了？观察「0 匹配」的频率，看它是否稳定在本模式的理论概率附近。

每个人都有自己的颜色

每个人穿不同颜色的衣服，原本的帽子与衣服同色。现在把帽子打乱，每人随机拿一顶。帽子与衣服同色就是匹配；所有人都不同色，就是完美错配。

先了解筹码规则

初始筹码：每组开始时持有 100 筹码。

每局费用：先支付 10 筹码，再随机发帽。

有人匹配：帽子与衣服同色算匹配，每匹配成功 1 人返还 5 筹码。1 人返还 5 筹码，2 人返还 10 筹码，3 人返还 15 筹码，以此类推。

无人匹配：所有人的帽子与衣服都不同色，称为完美错配，返还你填写的奖励。

填写后开始游戏；本组奖励固定，重置后可重新填写并恢复 100 筹码。

挑战：50 局后，筹码最接近 100

从 100 筹码出发，用最多 50 局观察你的奖励设定，让结束时持有的筹码尽量接近初始的 100。

以持平为目标，不以赚得最多为目标。筹码不足 10 时，本组提前结束。

持有筹码
100
总对局
0
完美错配(0匹配)
0
本轮匹配数
—
筹码走势（随对局）
匹配人数分布
最近10局记录净收益(筹码)
⚙

参数说明

  • 模式五人 / 十人，对应人数 n = 5 与 n = 10
  • 错排概率理论值 !n / n!：五人 44/120 ≈ 36.67%，十人 ≈ 36.79%（1/e 是 n → ∞ 的极限）
  • 筹码规则初始 100 筹码；每局支付 10 筹码；0 匹配返还自定奖励，否则每匹配成功 1 人返还 5 筹码
▸

操作指南

  1. 选模式后点「开始一局」随机发帽。
  2. 点击人物揭晓帽子；同色标记代表匹配，全部不同色才是完美错配。
  3. 填写奖励，观察最多 50 局的筹码走势；重置后可尝试新奖励。

一、我们究竟在求什么？

n 个人各有一顶不同的帽子，散场后随机发还，每人恰好得到一顶。给人和帽子分别编号为 1 到 n。第一个人有 n 顶可选，第二个人有 n−1 顶可选，依此类推，所以全部分配共有 n! = n×(n−1)×···×1 种。我们假设每种分配等可能，即每个排列的概率都是 1/n!。

记 X 为拿对帽子的人数。一个人拿到自己的帽子，就是一个“匹配”，数学上叫排列的不动点。我们要问的是 P(X=0)：没有任何人拿对帽子的概率。这样的排列叫作错排（Derangement），其数量记为 D_{n} = !n。

三个量要分清：X 是匹配人数，n−X 是拿错帽子的人数，D_{n} 是“全员拿错”的分配方案数。于是 P_{n} = P(X=0) = D_{n}/n!。衣服颜色标识主人，帽子颜色标识原主；每个人恰好拿一顶帽子，所有分配等可能。

二、先亲手数出 n = 1、2、3

用 (a₁,a₂,…,aₙ) 表示第 i 个人拿到编号 aᵢ 的帽子。

1 个人：只有 (1)，一定拿对。因此 D₁=0，P₁=0。
2 个人：共有 (1,2)、(2,1) 两种，只有 (2,1) 是错排。因此 D₂=1，P₂=1/2。
3 个人：六种排列为 (1,2,3)、(1,3,2)、(2,1,3)、(2,3,1)、(3,1,2)、(3,2,1)。只有加粗的两种没有匹配，所以 D₃=2，P₃=2/6=1/3。

人数增加时，逐个列举很快就不方便了。我们需要一种能一次性排除所有“有人拿对”的计数方法。

三、容斥原理：为什么减了还要加回来？

令 Aᵢ 表示“第 i 个人拿对帽子”。从全部 n! 个排列开始，排除 A₁、A₂、…、Aₙ 的并集，就留下了所有人都拿错的排列。

第 1 步：减去每个人拿对的情况。固定某个人拿自己的帽子，剩余 n−1 顶帽子任意分配，有 (n−1)! 种。这样的人有 n 个，因此先减去 n(n−1)!。
第 2 步：加回两个人同时拿对的情况。一个恰好有两人拿对的排列，在上一步被减了两次，实际只应排除一次，所以要加回。选一对人有 C(n,2) 种，固定他们后有 (n−2)! 种分配，因此加回 C(n,2)(n−2)!。
第 3 步：再减去三个人同时拿对的情况。一个恰好有三人拿对的排列，从总数中的 1 次开始，先被减 3 次，再按三对人加回 3 次，净计数为 1−3+3=1，所以还要减去 1 次。对应项为 −C(n,3)(n−3)!。
第 k 步：选定 k 个人有 C(n,k) 种选择，固定他们拿对后，剩余帽子有 (n−k)! 种排列。因此第 k 项是 (−1)ᵏC(n,k)(n−k)!。一直算到 k=n，规定 0!=1。
“指定 k 人拿对”不等于“恰好 k 人拿对”。剩下的人仍然可能拿对，正因为存在这些重叠，才需要容斥。对于恰好有 m≥1 人拿对的一个排列，最终计数为 Σᵐₖ₌₀(−1)ᵏC(m,k)=(1−1)ᵐ=0；没有人拿对的排列则保留 1 次。这就说明交替加减确实恰好留下所有错排。
D_{n} = n! − C(n,1)(n−1)! + C(n,2)(n−2)! − ··· + (−1)^{n}C(n,n)0!

四、从计数公式化简到概率公式

组合数 C(n,k)=n!/[k!(n−k)!]，所以每一项中的 (n−k)! 都可以约掉：

C(n,k)(n−k)! = n!/[k!(n−k)!] × (n−k)! = n!/k!

把公共因子 n! 提出来，再除以样本空间大小 n!，得到：

!n = n! · Σ^{n}_{k=0} (−1)^{k}/k!
P_{n} = D_{n}/n! = 1 − 1 + 1/2! − 1/3! + ··· + (−1)^{n}/n!

例如 n=4 时，D₄=24−4×6+6×2−4×1+1=9，所以 P₄=9/24=3/8。n=5 时，D₅=120−5×24+10×6−10×2+5×1−1=44，所以 P₅=44/120=11/30。

不能把每个人的“拿错”当成独立事件。每个人拿错的概率虽然都是 1−1/n，但 P_{n} 并不等于 (1−1/n)ⁿ。例如两人时，一人拿错就意味着另一人也拿错，实际概率为 1/2，而独立相乘会错误地得到 1/4。

五、逐步计算：每增加一个人，多出哪一项？

比较相邻两个有限和，只多出了最后一项。因此可逐步计算，无须每次从头求和：

P_{n} = P_{n−1} + (−1)^{n}/n!
D_{n} = nD_{n−1} + (−1)^{n}（n≥1，D₀=1）

D₀=1 是“没有帽子时只有一种空分配”的计数约定。计算时从 D₁=0 开始即可：

D₂=2×0+1=1；D₃=3×1−1=2；D₄=4×2+1=9。
D₅=5×9−1=44；D₆=6×44+1=265；D₇=7×265−1=1 854。
D₈=8×1 854+1=14 833；D₉=9×14 833−1=133 496；D₁₀=10×133 496+1=1 334 961。

概率的变化也很直观：P₂=1/2；P₃=1/2−1/6=1/3；P₄=1/3+1/24=3/8；P₅=3/8−1/120=11/30；P₆=11/30+1/720=53/144。每一步交替加减，而调整幅度 1/n! 越来越小。

人数 n错排数 Dₙ全部排列 n!概率（约）
1010%
21250%
32633.333333%
492437.500000%
54412036.666667%
626572036.805556%
71 8545 04036.785714%
814 83340 32036.788194%
9133 496362 88036.787919%
101 334 9613 628 80036.787946%
1114 684 57039 916 80036.787944%
12176 214 841479 001 60036.787944%
n → ∞——1/e ≈ 36.787944%

每行的精确概率都是第二列除以第三列，百分比作了舍入。n=11、12 与极限显示相同的小数，并不表示它们完全相等。这些数值提示我们可能存在极限；下面用公式证明它。

六、为什么极限是 1/e？

指数函数有对所有实数 x 成立的展开 eˣ=Σ^{∞}_{k=0}xᵏ/k!。取 x=−1：

1/e = e^{−1} = 1 − 1 + 1/2! − 1/3! + 1/4! − ···

P_{n} 正是这个无穷级数截至 k=n 的部分和。对从 k=1 开始的交错级数，项的绝对值 1/k! 严格递减到 0，因此交错级数余项定理给出：

0 < |P_{n} − 1/e| < 1/(n+1)! → 0（n≥1）
所以 lim_{n→∞} P_{n} = 1/e ≈ 0.3678794412

余项的符号由第一项被略去的项决定：奇数 n 时 P_{n} 小于 1/e，偶数 n 时大于 1/e。而且 P_{n+2}−P_{n}=(−1)^{n+1}[1/(n+1)!−1/(n+2)!]，所以奇数项逐渐上升，偶数项逐渐下降，两边共同夹住同一个极限：

P₁ < P₃ < P₅ < ··· < 1/e < ··· < P₆ < P₄ < P₂

n=5 时，误差小于 1/6!=1/720，换成百分比差距是小于 0.138889 个百分点；实际相差约 0.121277 个百分点。n=10 时，误差小于 1/11!，即小于 0.000002506 个百分点。阶乘增长很快，所以不需要很大的 n 就能得到非常接近 1/e 的概率。

从概率还能反推计数：把误差界乘以 n!，得到 |Dₙ−n!/e|<1/(n+1)≤1/2（n≥1）。因此 Dₙ 就是 n!/e 的最近整数。有限 n 时应使用 Dₙ/n! 作为精确概率，1/e 则提供非常方便的近似。

七、拓展：恰好 r 人拿对，怎样计算？

先从 n 人中选出拿对的 r 人，有 C(n,r) 种选择；剩下 n−r 人必须全部拿错，否则拿对人数就超过 r。因此对整数 0≤r≤n：

P(X=r) = C(n,r)D_{n−r}/n!

例如 n=5 时，X=0、1、2、3、4、5 对应的排列数依次为 44、45、20、10、0、1，合计 120。恰好 4 人拿对是不可能的：前四人拿走自己的帽子，最后那顶也只能属于第五人。这个规律对任意人数都成立：不可能恰好只有一个人拿错。

八、人数 n 与实验次数 N：两种不同的极限

增加人数 n，改变的是模型本身，理论概率 P_{n} 趋近 1/e；固定人数、增加独立实验次数 N，改变的是估计精度，完美错配的实验频率趋近该人数对应的 P_{n}。例如五人模式重复再多次，目标仍是 44/120，而不是恰好 1/e。

对预先确定的 N 次独立实验，记完美错配的频率为 p̂，则 E(p̂)=P_{n}，标准差为 √[P_{n}(1−P_{n})/N]。用 P_{n}≈0.368 估算：100 局时标准差约 4.8 个百分点，1000 局约 1.5 个百分点，10000 局约 0.48 个百分点。用正态近似，100 局的频率约有 95% 落在 27.3%～46.3% 范围内；这不是每次都必须满足的界限。

实验次数增加到原来的四倍，标准差才减半。频率不会保证每一步都更接近理论值，但整体波动会缩小。还要留意：页面的筹码不足会使批量实验提前停止，实际局数可能小于按钮标注的局数；上述固定 N 的波动计算不能直接当作这种随机停止过程的保证。

九、每匹配一人返还 5 筹码：不同人数的公平奖励

记匹配人数为 X，完美错配概率为 P_{n}=D_{n}/n!。每局支付 10 筹码；X≥1 时返还 5X 筹码，X=0 时返还 R_{n} 筹码。奖励是返还额，不是额外净赚；下文奖励金额的单位均为筹码。

第一步：平均匹配人数。每个人拿对帽子的概率都是 1/n。把 n 个“是否匹配”的指示变量相加，得到 E(X)=n×(1/n)=1。期望的可加性不要求各人是否匹配相互独立。
第二步：平均返还额。按人数返还的部分平均为 5E(X)=5；完美错配的奖励平均为 P_{n}R_{n}。二者不重叠，因为 X=0 时 5X 也为 0。
第三步：平均持平。令平均返还等于支出：P_{n}R_{n}+5=10，得到下式。
R_{n} = 5/P_{n} = 5n!/D_{n}（n≥2）

两人时 P₂=1/2，所以 R₂=10；三人时 P₃=1/3，所以 R₃=15；四人时 P₄=3/8，所以 R₄=40/3≈13.333333。完美错配越少见，公平返还额越高。

人数 n精确概率 Pₙ概率（约）公平返还 Rₙ（约）
1 人0/10.000000%不存在
2 人1/250.000000%10.000000
3 人2/633.333333%15.000000
4 人9/2437.500000%13.333333
5 人44/12036.666667%13.636364
6 人265/72036.805556%13.584906
7 人1854/504036.785714%13.592233
8 人14833/4032036.788194%13.591317
9 人133496/36288036.787919%13.591418
10 人1334961/362880036.787946%13.591408
11 人14684570/3991680036.787944%13.591409
12 人176214841/47900160036.787944%13.591409
n → ∞1/e36.787944%13.591409

1 人时必定匹配，只能返还 5 筹码，每局损失 5 筹码；完美错配永不发生，因此没有有限的公平奖励。

五人：R₅=5÷(44/120)=150/11≈13.636364。十人：R₁₀=5÷(1334961/3628800)≈13.591408。

P_{n} → 1/e，因此 R_{n} → 5e ≈ 13.591409

奇数人数 n≥3 的概率低于 1/e，所以奖励高于 5e，并从上方下降；偶数人数的奖励从下方上升。表内小数经过舍入，相同显示值不代表精确相等。五人和十人模式若只允许整数奖励，13 偏低、14 偏高。

50 局后的筹码：若完整完成 50 局，其中 K 局完美错配、所有局匹配人数合计为 S，最终筹码为 100−50×10+KR+5S=KR+5S−400。固定 50 次独立实验中 E(K)=50P_{n}、E(S)=50，因此采用 R=5/P_{n} 时，最终筹码的期望为 100。实际的 K、S 有随机性，平均持平不保证每组恰好回本，也不保证每组与 100 的差距最小。筹码不足提前结束时，应记录实际局数。

More Experiments

探索其他实验

💸 破产清算

筹码耗尽，无法继续下注。