秘密圣诞老人之谜
你可能还记得，我在2023年10月26日的新闻通讯中写过一篇关于他们在船上玩的游戏节目的文章，名为“一掷千金”（Deal or No Deal）。在那个游戏中，每个玩家都可以购买卡片，获得上台表演的机会。不过，每张卡片都有机会赢得安慰奖。安慰奖的玩法是，每张卡片上有20个箱子，箱子后面随机放着20种不同的奖金。箱子的盖子掀开后即可打开。玩家获胜的条件是，卡片上的奖金有多少与屏幕上随机排列的相同奖金匹配。那篇新闻通讯中一个未解决的问题是，任意给定数量的匹配概率。
这个问题通常被称为“秘密圣诞老人谜题”。它的名字来源于圣诞派对上的一项活动：一群人（通常在同一间办公室）从一顶写有所有办公室员工名字的帽子里抽取一个名字，以此来决定要送礼物给谁。这个游戏的一个问题是，你有可能抽到自己的名字，这很没意思。平均而言，每个办公室都会有一名玩家遇到这种情况，无论有多少员工。在本期简报中，我试图解答的一个问题是，没有人抽到自己名字的确切概率是多少。
在我撰写10月26日的时事通讯时，我并不清楚该如何计算，所以用泊松函数进行了估算。然而，这个问题一直困扰着我。我一直觉得估算在智力上非常不令人满意。
首先，我编写了一个计算机程序，循环遍历所有可能的奖品顺序，并计算每个排列对应的匹配数量。然而，如果是13个行李箱，该程序大约需要一天时间才能遍历完所有6,227,020,800种排列。如果是20个行李箱，则有2,432,902,008,176,640,000种排列，大约需要一百万年才能遍历完。
其次，我打开Excel，尝试用递归的方式计算。结果比我想象的要简单得多。我一开始就应该这么做。本通讯的其余部分将解释该方法背后的逻辑。
我假设读者熟悉 Excel 的 combin(x,y) 函数，它表示从 x 中选择 y 项的方式数量。其确切公式为 x!/(y!*(xy)!)。
让我们从一些明显的案例开始。
- 1.有一位圣诞老人，显然他有自己的名字。
- 2.有两个圣诞老人，那么两个人都有自己名字或彼此名字的概率是 50%。
- 3.有三个圣诞老人，每个人有1种可能的名字。两个人有0种可能的名字，因为如果他们这样，最后一个人也会抽到自己的名字，因为这是唯一剩下的一个。一个人有3种可能的名字，分别是3个人各一个，另外两个人互相有1种可能的名字。3*1 = 1。3个名字的排序方式共有3!=6种。0个人有自己名字的可能方式数就是剩下的：6-1-3 = 2。
到目前为止，我们的进展如下：
| 火柴 | 3个圣诞老人 | 2个圣诞老人 | 1 圣诞老人 |
| 3 | 1 | ||
| 2 | 0 | 1 | |
| 1 | 3 | 0 | 1 |
| 0 | 2 | 1 | 0 |
| 全部的 | 6 | 2 | 1 |
接下来，让我们来谈谈 4 位圣诞老人。
4 场比赛：每个人总有一种方法可以得到自己的名字。
3个匹配：除了一个人之外，其他人都抽到自己的名字是不可能的。当除了一个人之外的其他人都匹配成功后，就只剩下一个人和他们的名字，而且他们必须相同。
2 人匹配：从 4 个人中选出 2 人进行匹配，一共有 combin(4,2)=6 种方法。另外 2 个人不匹配，只有 1 种方法，即通过抽签的方式匹配对方的名字。
1 次匹配：选择与自己匹配的圣诞老人有 4 种方式。从 3 个圣诞老人的情况可以看出，另外 3 个圣诞老人不匹配的情况有两种，这是必然发生的。因此，1 次匹配的组合数为 4*2=8。
0 个匹配：同样，我们从总排列中减去所有其他可能性。4！- 1 - 6 - 8 = 24-15=9。
现在我们位于：
| 火柴 | 4个圣诞老人 | 3个圣诞老人 | 2个圣诞老人 | 1个圣诞老人 |
| 4 | 1 | |||
| 3 | 0 | 1 | ||
| 2 | 6 | 0 | 1 | |
| 1 | 8 | 3 | 0 | 1 |
| 0 | 9 | 2 | 1 | 0 |
| 全部的 | 24 | 6 | 2 | 1 |
接下来，让我们来了解一下 5 位圣诞老人。
5 场比赛：每个人总有一种方法可以得到自己的名字。
4 场比赛：不可能，原因在 4 个圣诞老人的案例中有所说明。
3 次匹配：从 5 个人中选择 3 个人进行匹配，共有 combin(5,3)=10 种方法。另外两个人互相知道对方名字的方法只有 1 种。因此，3 次匹配共有 10 种方法。
2 人匹配：从 5 个人中选出 2 人进行匹配，一共有 combin(5,2)=10 种方式。其余 3 人，有两种不匹配的方式，这一点我们从 3 个圣诞老人的案例中可以看出。因此，2 人匹配共有 10*2=20 种方式。
1 次匹配：选择与自己匹配的圣诞老人有 5 种方式。从 4 个圣诞老人的情况可以看出，其他 4 个圣诞老人不匹配的情况有 9 种，这是必然发生的。因此，1 次匹配的组合数为 5*9=45。
0 个匹配：同样，我们从总排列中减去所有其他可能性。5！- 1 - 0 - 10 - 20 - 45 = 44。
现在我们位于：
| 火柴 | 5个圣诞老人 | 4个圣诞老人 | 3个圣诞老人 | 2个圣诞老人 | 1个圣诞老人 |
| 5 | 1 | ||||
| 4 | 0 | 1 | |||
| 3 | 10 | 0 | 1 | ||
| 2 | 20 | 6 | 0 | 1 | |
| 1 | 45 | 8 | 3 | 0 | 1 |
| 0 | 四十四 | 9 | 2 | 1 | 0 |
| 全部的 | 120 | 24 | 6 | 2 | 1 |
按照同样的逻辑，我们得到最多 10 位圣诞老人的下表。
| 垫。 | 10个圣诞老人 | 9个圣诞老人 | 8个圣诞老人 | 7个圣诞老人 | 6个圣诞老人 | 5个圣诞老人 | 4个圣诞老人 | 3个圣诞老人 | 2个圣诞老人 | 1个圣诞老人 |
| 10 | 1 | |||||||||
| 9 | 0 | 1 | ||||||||
| 8 | 45 | 0 | 1 | |||||||
| 7 | 240 | 三十六 | 0 | 1 | ||||||
| 6 | 1890 | 168 | 二十八 | 0 | 1 | |||||
| 5 | 11088 | 1134 | 112 | 21 | 0 | 1 | ||||
| 4 | 55650 | 5544 | 630 | 70 | 15 | 0 | 1 | |||
| 3 | 222480 | 22260 | 2464 | 315 | 40 | 10 | 0 | 1 | ||
| 2 | 667485 | 66744 | 7420 | 924 | 135 | 20 | 6 | 0 | 1 | |
| 1 | 1334960 | 133497 | 14832 | 1855 | 264 | 45 | 8 | 3 | 0 | 1 |
| 0 | 1334961 | 133496 | 14833 | 1854 | 265 | 四十四 | 9 | 2 | 1 | 0 |
| 全部的 | 3628800 | 362880 | 40320 | 5040 | 720 | 120 | 24 | 6 | 2 | 1 |
请注意，0 个匹配和 1 个匹配的排列数总是相差无几。如果圣诞老人数量为偶数，则 0 个匹配的排列数比 1 个匹配的排列数多一个；如果圣诞老人数量为奇数，则 0 个匹配的排列数比 1 个匹配的排列数少一个。如果我们接受这种情况总是成立（事实也确实如此），那么我们可以快速确定 11 个或更多圣诞老人的 0 个匹配的排列数，如下所示。
11个圣诞老人：对于一个匹配，有11个圣诞老人需要匹配，而其他10个不匹配的情况，则有133,496种方式。因此，1个匹配的排列数为11*133,496 = 14,684,571。由于11是奇数，因此0个匹配的排列数少一个，即14,684,571 - 1 = 14,684,570。
12个圣诞老人：对于一个匹配，有12个圣诞老人需要匹配，而其他11个不匹配的情况，则有14,684,570种方式。因此，1个匹配的排列数为12*14,684,570 = 176,214,840。由于12是偶数，因此0个匹配的排列数多一个，即176,214,840 + 1 = 176,214,841。
继续同样的逻辑，这里是 1 到 20 个圣诞老人的 0 个匹配的排列数，包括总排列数和概率。
| 圣诞老人 | 0 场比赛 | 总排列 | 可能性 |
| 20 | 895,014,631,192,902,000 | 2,432,902,008,176,640,000 | 0.367879 |
| 19 | 44,750,731,559,645,100 | 121,645,100,408,832,000 | 0.367879 |
| 18 | 2,355,301,661,033,950 | 6,402,373,705,728,000 | 0.367879 |
| 17 | 130,850,092,279,664 | 355,687,428,096,000 | 0.367879 |
| 16 | 7,697,064,251,745 | 20,922,789,888,000 | 0.367879 |
| 15 | 481,066,515,734 | 1,307,674,368,000 | 0.367879 |
| 14 | 32,071,101,049 | 87,178,291,200 | 0.367879 |
| 十三 | 2,290,792,932 | 6,227,020,800 | 0.367879 |
| 12 | 176,214,841 | 479,001,600 | 0.367879 |
| 11 | 14,684,570 | 39,916,800 | 0.367879 |
| 10 | 1,334,961 | 3,628,800 | 0.367879 |
| 9 | 133,496 | 362,880 | 0.367879 |
| 8 | 14,833 | 40,320 | 0.367882 |
| 7 | 1,854 | 5,040 | 0.367857 |
| 6 | 265 | 720 | 0.368056 |
| 5 | 四十四 | 120 | 0.366667 |
| 4 | 9 | 24 | 0.375000 |
| 3 | 2 | 6 | 0.333333 |
| 2 | 1 | 2 | 0.500000 |
| 1 | 0 | 1 | 0.000000 |
注意，0场比赛的概率是如何接近0.367879的。这个数字看起来很熟悉吗？没错！它是1/e。我现在可以写一本关于泊松估计的小册子了，但这份简报已经太长了。想了解更多，我推荐斯坦福·黄（Stanford Wong）的《敏锐体育博彩》（Sharp Sports Betting），这本书解释了如何使用泊松函数分析超级碗的命题投注。
让我们回到 Deal or No Deal 游戏，它相当于 20 个圣诞老人的情况。我们想知道 0 到 20 个匹配的组合数。
20 位圣诞老人中，m 个匹配项的组合数为 combin(20,m)*z(m)，其中 z(m)=m 位圣诞老人中 0 个匹配项的组合数。下表使用该方法计算了 20 位圣诞老人中，0 到 20 个匹配项的组合数。
| 火柴 | 排列 | 可能性 |
| 20 | 1 | 0.000000 |
| 19 | - | 0.000000 |
| 18 | 190 | 0.000000 |
| 17 | 2,280 | 0.000000 |
| 16 | 43,605 | 0.000000 |
| 15 | 682,176 | 0.000000 |
| 14 | 10,271,400 | 0.000000 |
| 十三 | 143,722,080 | 0.000000 |
| 12 | 1,868,513,010 | 0.000000 |
| 11 | 22,421,988,160 | 0.000000 |
| 10 | 246,642,054,516 | 0.000000 |
| 9 | 2,466,420,377,200 | 0.000001 |
| 8 | 22,197,783,520,770 | 0.000009 |
| 7 | 177,582,268,088,640 | 0.000073 |
| 6 | 1,243,075,876,659,240 | 0.000511 |
| 5 | 7,458,455,259,939,930 | 0.003066 |
| 4 | 37,292,276,299,704,500 | 0.015328 |
| 3 | 149,169,105,198,817,000 | 0.061313 |
| 2 | 447,507,315,596,451,000 | 0.183940 |
| 1 | 895,014,631,192,902,000 | 0.367879 |
| 0 | 895,014,631,192,902,000 | 0.367879 |
| 全部的 | 2,432,902,008,176,640,000 | 1.000000 |
如果您将这些概率与我在2023 年 10 月 26 日的新闻通讯中的泊松估计进行比较，您会发现所有人都同意提供的六位小数，这表明泊松函数和数字 e 的有用性。
下周，我计划详细阐述这个主题，并展示任意数量圣诞老人的排列数的一般公式。