探究离散事件概率的问题本身就很吸引人。也许是因为它们让我们能够以结构化的方式推理不确定性，或者因为它们挑战我们在看似随机的情况中找到秩序。这也许可以解释为什么涉及基本概率和组合学的问题在定量面试中如此普遍。只需几个相对简单的前提，我们就可以设计出快速升级为智力要求高的计算的场景。这些场景可能会令人困惑，因为即使使用相对较小的数字，它们也经常涉及大量组合。
尽管如此，这些组合问题背后的数学原理通常很简单。无需使用高级代数、计算复杂积分或求解奇异微分方程。大多数时候，我们只需要简单的和和积。因此，这些问题是测试抽象思维、将复杂挑战分解为程序步骤的能力以及避免直观但错误解决方案的纪律的完美简约舞台。
这类问题中有一类特殊问题涉及错位。错位是一组元素的排列，其中没有元素出现在其原始位置。例如，如果我们考虑人们彼此交换帽子，错位意味着没有人最终会戴上他们原来的帽子。下面的问题就是一个很好的例子。我在许多不同的环境中找到了这个问题的不同版本，从有影响力的概率论和统计学书籍，如《概率的一千个练习》 ，到剑桥大学等顶尖大学的考试题目，以及定量准备书籍，如Timothy Falcon Crack的著名的《街头风云》。我的版本如下：
大量员工 N 正在参加公司培训活动。一天开始时，每位参与者都会被分配到一个大型培训室的特定办公桌上，他们的名牌会放在办公桌上。上午的会议结束后，他们都前往自助餐厅吃午饭。回到培训室后，参与者发现他们的名牌不见了：午休期间，清洁人员在整理时不小心取下了名牌。然后，参与者被指示坐在一个随机的办公桌上。至少有一名参与者最终坐在他们最初被分配的办公桌上的概率是多少？
您说得完全正确 — “quick and dirty” 确实具有一定的冲击力，能够有效传达预期含义。以下是保留该短语的修订版本：
一般来说，这个问题可以针对任意N值求解，但当N较大时，它会变得更加容易处理。下面，我将介绍两种不同的方法：一种快速而粗略的方法，另一种更详细但更严格。在深入研究我的解决方案之前，请先尝试自己解决这个练习！
快速而肮脏的解决方案正如问题陈述中提到的，我们可以假设N非常大，甚至接近无穷大。在这种情况下，想象一下午餐回来后，每个人排队随机分配一张新桌子。如果N非常大，我们可以将排队的每个人都视为“第一”，因为与他们身后无限长的队列相比，前面有限数量的人变得微不足道。
因此，每个人被分配到原来办公桌的概率大致相同，均为1/N 。从互补的角度来看，一个人不回到原来办公桌的概率为1-1/N。
我们感兴趣的是找出至少有一个人最终回到原来办公桌的概率，所以让我们定义一个随机变量 X 作为回到原来办公桌的人数。目标是计算 P(X>0)。与其直接计算这个概率，不如找到补集 P(X=0)，并使用关系 P(X>0)=1−P(X=0)，这样更简单。
继续上面的无限队列推理，当N非常大时，每个人被重新分配到哪个办公桌的事件都是独立的，因此所有N个人避开原来办公桌的概率只是他们各自概率的乘积。这给出：
右边的表达式应该让你想起什么。在N趋近于无穷大的极限中，该项收敛到1/e，其中e是欧拉数。因此，结果是：
这意味着至少有一人最终回到原来的办公桌的概率约为 63%。有趣的是，这是一个上限（因为我们在N趋向于无穷大的极限下工作）。人数越多，至少有一人回到原来的办公桌的概率就越大。
详细而严谨的解决方案要理解大N极限为何有效，我们可以从头开始构建事件X>0的计算。这需要仔细考虑包容排斥原理，它的核心其实只不过是集合的一个属性（毕竟，概率只是一些花哨的集合论）。包容排斥原理告诉我们如何根据事件交集来计算事件并集的概率，它非常有用，因为通常（就像在这种情况下）计算后者更简单。
令A_k表示第k位参与者最终回到其原始办公桌的事件（k=1至N） 。但是，我们的目标是找出至少一名员工最终回到其原始办公桌的概率。这对应于所有事件A_k的并集（换句话说，这是事件A_1 或事件A_2，或事件A_3等——其中所有或都是非排他性的）。其概率由下式给出
如果您熟悉包含-排除公式，您可以直接在此处应用它来评估合并的概率。对于不熟悉的人，可以通过仔细考虑重叠概率来推导出该公式。这涉及：
将每个单独事件的概率相加：首先对所有k=1,2,…,N求和P(A_k)，这表示每个人分别返回自己办公桌的概率。减去成对重叠：接下来，删除事件对P(A_k∩A_j)的概率，因为这些概率在第一步中被多算了。这些是人k 和人j最终都坐在他们最初的办公桌上的概率。加回三重重叠：为了调整过度校正，加回三重重叠的概率P(A_k∩A_j∩A_l)。继续这种模式：对于较大的交集（四元组、五元组等），交替使用减法和加法，直到所有项都得到考虑。这个过程可以用维恩图清楚地可视化（参见下图——我只显示了前三个步骤），其中重叠区域被系统地计数和调整。
用三个事件来说明容斥原理的维恩图。
我们刚刚解释的过程可以得出以下公式：
或者简洁地写成：
在这个公式中，在交集扩展的每个阶段，我们都在计算从N 个可能集合中选择m 个的组合，这些集合由二项式系数N 选择 m给出（查看最近这篇关于二项式系数的文章，重新认识一下二项式系数）。之所以允许进行这种简化，是因为包含-排除公式中交集的大小仅取决于有多少个集合被相交，而不取决于交集中涉及的具体集合。
现在我们已经有了一种通过交集概率来计算并集概率的方法，让我们计算后者。不失一般性，让我们将所有N名员工排成一行，编号从1到N。如前面的快速解决方案所示，给定随机办公桌分配，每个员工最终回到原来办公桌的概率均为P(A_k)=1/N。
现在，考虑事件之间的依赖关系。如果员工1获得了原来的办公桌，那么员工2被分配到原来的办公桌的概率P(A_2|A_1)=1/(N−1)会略高一些，因为我们已经消除了一个可能的不匹配。使用贝叶斯规则，我们可以计算出两个事件同时发生的概率：
这一推理可以归纳扩展，以计算m 名员工最终都回到原办公桌的概率。对于前m 名员工，这一概率为：
这个结果解释了员工之间的顺序依赖关系，这正是我们需要插入到包含-排除公式中的通用项。插入这个结果后，我们可以看到公式大大简化，我们很快就得到了最终结果，
在最后一步中，我们使用了欧拉数的逆的另一种表示，即指数函数exp(x)在x=-1 时的级数展开。请注意，在这个推导中，我们将N保持为通用的，直到最后一步！如果我们有兴趣求有限N的精确表达式，我们可以简单地计算有限和。因此，这种方法比我最初提出的快速方法更全面一些。
结论这个关于错乱的概率难题突出了结构化随机性的迷人融合以及直觉和数学严谨性之间的平衡。我探索了两种方法：一种是快速、直接的方法，可以直接跳到解决方案，另一种是详细的、循序渐进的方法，可以解开问题的每个方面。在它们之间进行选择取决于你对简单性或深度的偏好。无论哪种方式，我认为与欧拉数的惊人联系既有趣又富有启发性！
你喜欢这个问题吗？如果你有其他方法或见解，我很乐意听听！分享你的想法！
