文末有一道与本文内容相关的高中计数原理题目。
交换礼物
故事要从 2023 年底前说起。
班级同学进行元旦礼物交换，每人准备一个礼物。
交换规则：每人抽取一个名字（不放回），把自己准备的的礼物送给抽到的人。
问题：有人无法成功送出礼物 （即抽到自己的名字）的概率为多少？（那天成功用这个问题让几个同学在晚自习失去写作业的兴趣。）
你的第一反应或许是：没说班级人数，条件不够！这正是这个问题的有趣之处，实际上，没有班级人数同样可以得出结果，读到后面你就能明白这么说的原因。
总之，让我们先把问题翻译成更数学的语言。
假设班里有 \(n\) 个学生，依次记为 \(S_1, S_2, \ldots, S_n\)，对应地将他们准备的礼物分别记为 \(g_1, g_2, \ldots, g_n\)。
\[ \begin{array}{c} S_1 & S_2 & S_3 & \cdots & S_{n-1} & S_n \\ \hline g_1 & g_2 & g_3 & \cdots & g_{n-1} & g_n \\ \end{array} \]
随机抽取的过程就是将礼物随机分配给每位同学，即将 \(g_1\) 到 \(g_n\) 所有礼物以任意顺序重新排列。某个学生 \(S_i\) 抽到自己的礼物，就意味着在重新排列后，\(g_i\) 的位置没有变——还在 \(S_i\) 下面。例如，假设班里一共有 \(3\) 个学生 \(S_1, S_2, S_3\)，那么：
\[ \begin{array}{ccc:c} S_1 & S_2 & S_3 & \\ \hline g_1 & g_2 & g_3 & \text{每个人都抽到了自己的礼物} \\ \hdashline g_1 & g_3 & g_2 & S_1\text{抽到了自己的礼物} \\ \hdashline g_2 & g_3 & g_1 & \text{没有人抽到自己的礼物} \\ \end{array} \]
我们有
\[\boxed{\text{所求概率} = \frac{\text{满足要求的排列方式数}}{\text{所有排列方式数}}}\]
分母是简单的，就是 \(n\) 的阶乘，即\(n!\)。
阶乘是什么？
正整数 \(n\) 的阶乘是所有小于等于该数的正整数的积，记作 \(n!\)
例如 \[5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\]
关键在于分子的计算方法。要求有人抽到自己的礼物，具体来说包含以下情况：
- 有 \(1\) 个人抽到自己的礼物
- 有 \(2\) 个人抽到自己的礼物
- ……
- 有 \(n\) 个人抽到自己的礼物
分别计算以上 \(n\) 种情况后求和会十分困难。正难则反，因为 \[\boxed{\text{满足要求的排列方式数} = \text{所有排列方式数} - \text{没有人抽到自己礼物的排列方式数}}\] 所以只需计算没有人抽到自己礼物的排列方式数。
我们把这样“没有人抽到自己礼物”的排列称为错位重排。
错位重排
错位重排的具体定义
请读者确认以下两种定义方式是等价的，这对后文的理解很重要。
表述一：考虑按一定顺序排列好的
表述二：将 \(n\)个元素分别放到 \(n\)个不同的位置，每个元素有且只有一个位置不能去，同时每个位置有且只有一个元素不能放置。
我们先讨论班级总人数很少的情况，看看能不能找到规律。为了方便，记 \(n\) 个元素错位重排的方法数为 \(D_n\)。
若 \(n=1\)，即班级只有 \(1\) 个人，那么显然这位同学的准备礼物永远在自己手上，不可能实现错位，故 \(D_1=0\)。
若 \(n=2\)，一共有 \(2\) 种排列方式
\[ \begin{array}{c} S_1 & S_2 \\ \hline g_1 & g_2 \\ \hdashline g_2 & g_1 \\ \end{array} \]
其中 \(g_2,g_1\) 是错位排列的，故 \(D_2=1\)。
若 \(n=3\)，一共有 \(6\) 种排列方式
\[ \begin{array}{c} S_1 & S_2 & S_3 \\ \hline g_1 & g_2 & g_3 \\ \hdashline g_1 & g_3 & g_2 \\ \hdashline g_2 & g_1 & g_3 \\ \hdashline g_2 & g_3 & g_1 \\ \hdashline g_3 & g_1 & g_2 \\ \hdashline g_3 & g_2 & g_1 \\ \end{array} \]
其中\(g_2,g_3,g_1\) 和 \(g_3,g_1,g_2\) 是错位排列的，故 \(D_3=2\)。
若 \(n=4\)，一共有 \(4!=24\) 种排列方式，全部列出后一一验证不太现实，合理的选择是按照以下方法研究。
\(g_1\) 不能在 \(S_1\) 下面，不妨先把它放在 \(S_2\) 下面。
\[ \begin{array}{c} S_1 & S_2 & S_3 & S_4 \\ \hline & \color{red}g_1 & & \\ \end{array} \]
此时 \(g_2\) 可以放在剩下空位中的任何一个位置，即以下 \(3\) 种情况。
\[ \begin{array}{c} S_1 & S_2 & S_3 & S_4 \\ \hline \color{blue}g_2 & \color{red}g_1 & & \\ \hdashline & \color{red}g_1 & \color{blue}g_2 & \\ \hdashline & \color{red}g_1 & & \color{blue}g_2 \\ \end{array} \]
然后在空位中填入 \(g_3, g_4\)，第一种情况下只有 \(g_2,g_1,g_4,g_3\) 是错位排列的，第二种情况下只有 \(g_4,g_1,g_2,g_3\) 是错位排列的，第三种情况下只有 \(g_3,g_1,g_4,g_2\) 是错位排列的，共 \(3\) 种方法。
类似地，最初将 \(g_1\) 放在 \(S_3\)、\(S_4\) 下面也会分别得到 \(3\) 种错位重排的方法，所以 \(D_4=3 \times 3=9\)。
若 \(n=5\)，同样先将 \(g_1\) 固定在一个位置：
\[ \begin{array}{c} S_1 & S_2 & S_3 & S_4 & S_5 \\ \hline & \color{red}g_1 & & & \\ \end{array} \]
于是 \(g_2\) 可以放在剩下空位中的任何一个位置。
情况一：\(g_2\) 放在 \(S_1\) 下面。
\[ \begin{array}{c} S_1 & S_2 & S_3 & S_4 & S_5 \\ \hline \color{blue}g_2 & \color{red}g_1 & & & \\ \end{array} \]
此时只需要在空位中错位地填入 \(g_3,g_4,g_5\) 三个元素，我们已经算过方法数了，就是 \(D_3=2\)
情况二：\(g_2\) 不放在 \(S_1\) 下面。
这时如果模仿 \(n=4\) 时的处理方式分 \(3\) 类也过于麻烦，最需要注意力的一步出现了：
我们的需求是将 \(g_2,g_3,g_4,g_5\) 四个元素分别放入 \(4\) 个空位，要求 \(g_2\) 不能放在 \(S_1\) 下面，\(g_3\) 不能放在 \(S_3\) 下面，\(g_4\) 不能放在 \(S_4\) 下面，\(g_5\) 不能放在 \(S_5\) 下面。这符合前文错位重排定义的第二种表述，所以方法数就是 \(D_4=9\)。
综合以上讨论，得到结论：\(g_1\) 放在 \(S_2\) 下面的前提下，一共有 \(D_3+D_4=2+9=11\) 种错位的排列方式。
类似地，\(g_1\) 还可以放在 \(S_3,S_4,S_5\) 下面，分别对应 \(11\) 种排列方式。所以总的排列方式数 \(D_5=4(D_3+D_4)=44\)。
用类似的方法，可以得到递推式：
\[\boxed{D_n=(n-1)(D_{n-2}+D_{n-1})}\]
这里给出前几项的计算结果：
| 项 | 数值 | 项 | 数值 | 项 | 数值 |
|---|---|---|---|---|---|
| \(D_1\) | \(0\) | \(D_5\) | \(44\) | \(D_9\) | \(133496\) |
| \(D_2\) | \(1\) | \(D_6\) | \(265\) | \(D_{10}\) | \(1334961\) |
| \(D_3\) | \(2\) | \(D_7\) | \(1854\) | \(D_{11}\) | \(14684570\) |
| \(D_4\) | \(9\) | \(D_8\) | \(14833\) | \(D_{12}\) | \(176214841\) |
计算概率
回到送礼物的问题，如果班级有 \(n\) 个人，根据之前的分析，没有人抽到自己礼物的概率为 \(\frac{D_n}{n!}\)，有人抽到自己礼物的概率为 \(1 - \frac{D_n}{n!}\)。
通过计算器计算，得到下表（有人抽到自己礼物的概率，保留 \(10\) 位小数）
| 班级人数 | 概率 | 班级人数 | 概率 |
|---|---|---|---|
| \(1\) | \(1.0000000000\) | \(7\) | \(0.6321428571\) |
| \(2\) | \(0.5000000000\) | \(8\) | \(0.6321180556\) |
| \(3\) | \(0.6666666667\) | \(9\) | \(0.6321208113\) |
| \(4\) | \(0.6250000000\) | \(10\) | \(0.6321205357\) |
| \(5\) | \(0.6333333333\) | \(11\) | \(0.6321205608\) |
| \(6\) | \(0.6319444444\) | \(12\) | \(0.6321205587\) |
在保留 \(10\) 位小数的前提下，班级人数更多时对应的概率都是 \(0.6321205588\)。
你可能会惊叹于两件事。概率竟然这么大？随着班级人数增加概率竟然几乎无变化？
事实上，可以证明（但超出本文讨论范围）
\[D_n = \left\lfloor\frac{n!}{e}+0.5\right\rfloor\]
\(\lfloor x \rfloor\) 表示向下取整，例如 \(\lfloor\pi\rfloor=3;\lfloor 5 \rfloor=\lfloor 5.99 \rfloor=5\)
哪怕是很小的 \(n\)，取整带来的差异也能忽略不计，即 \[\frac{D_n}{n!} \approx \frac{n!}{e} \cdot \frac{1}{n!} = \frac{1}{e} \approx 0.3678794412\]
直观上，这么大的概率其实有合理性：
上帝视角：有人抽到自己名字的概率达 \(63\%\)，并不是很神奇
个人视角：我自己抽到自己名字的概率很小，或许值得惊叹
生活中还有很多这样的情形，例如，在抽奖活动中，一定有人中奖，但中奖的人不太可能刚好是你。
所以，即便数学告诉我们有人抽到自己的礼物并不是一件很神奇的事，这并不妨碍我们为之惊叹：交换礼物当天，有两处爆发出同学们的欢呼声——那个人抽到了自己名字。
补充：在高中题目中的应用
问题：甲、乙两人各有 \(4\) 张卡片，每张卡片上分别标有 \(1,2,3,4\) 四个数字之一。两人进行四轮比赛，在每轮比赛中，甲、乙各自从自己持有的卡片中随机选一张，并比较卡片上数字的大小，数字大者胜，然后各自舍弃此轮所选卡片（舍弃的卡片在此后的轮次中不能使用）。则四轮比赛中，甲、乙每轮所出数字大小均不相同的情况共有多少种？
解答：甲和乙的出牌方式可能性过于自由，不妨先固定甲的顺序为 \(1,2,3,4\)，此时乙要想均不相同就有 \(D_4=9\) 种出牌顺序。而甲的出牌顺序有 \(4!=24\) 种情况，每种情况下乙都有 \(9\) 种出牌方式实现数字大小均不相同，于是总共有 \(24 \times 9=216\) 种符合要求的情况。
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。
