设想有 n 个人参加一场宴会，每个人拿一顶帽子，所有的帽子各不相同。宴会结束时，
每个人随机拿一顶帽子带走。问所有人拿错帽子的概率是多少？
用数学语言重新表述这个问题：在 n 阶置换群 Sn 中，置换没有不动点的概率是多少？
以及，当 n 趋于无穷时，这个概率会趋近于 0，趋近于 1，还是其他数？
可能大多数人凭直觉认为，这个概率要么太大要么太小，因此总会趋近 0 或者 1。让我
们用计算来验证直觉是否准确。

这是一个典型的古典概型，我们需要先算出样本空间的大小。样本空间是整个Sn，即 n
个不同元素的所有排列。高中的排列知识告诉我们，样本空间的大小是 n!。
然后需要计算没有不动点的置换数量。为了便于理解，我仍然会拿参加宴会的人和帽子
作为研究对象。在进入讨论之前，先补充一些前置知识。

容斥原理：对于任意两个（有限）集合 A 和 B，令 N(A)表示 A 的元素数量，那么

用人话讲，A 和 B 的元素总数等于两个集合的元素数量之和，减去它们公共部分的元素
数量。因为交集被数了两次，所以要减去。
如果有三个集合 A,B 和 C，那么

这个原理可以推广到 n 个集合。如果 A1,A2,…,An 是 n 个集合，那么

其中，第二个及以后的求和符号代表对所有满足 i<j （i<j<k 等）的正整数对（组）求
和。求和号有 k 个下角标，根据排列组合的知识，就代表是 C(n,k)个 k 个集合的交集的
元素数量和。可以用这个公式验证上面三个集合的情况是正确的。

坐等更新不剧透

回归我们的题目。我们要求有多少种方法让每个人都拿错帽子。为了方便起见，我们把
客人从 1 到 n 标号。设事件 A1 是客人 1 拿对帽子（其余的人怎么拿就不管了）。所以
A1 的大小为

类似地定义 A2 是客人 2 拿对帽子，…，An 是客人 n 拿对帽子。这样，A2，…，An 的大
小都是(n-1)!。所以

下面来看各种交集的大小。对于两个集合的情况，比如 A1∩A2——即客人 1 和 2 拿对
帽子的情况，由于这两人的选择是唯一的，而其余 n-2 人从剩下 n-2 顶帽子中任选，所
以 A1∩A2 的大小为

有 C(n,2)种方法从 n 个客人中选 2 位拿对帽子，所以

（2!先留着不化简，有用）
类似地，对于 1≤k≤n，k 个交集代表 k 个客人拿对帽子，剩下 n-k 个客人从 n-k 个帽
子中任选，共(n-k)!种选择。而有 C(n,k)种方法从 n 个客人中选 k 个拿对帽子，所以

在进行完这一系列推导以后，由容斥原理可以得出，至少一个客人拿对帽子的选择数量
为

所以，至少有一个客人拿对帽子的概率，等于这个数量除以 n!：

1 减去这个概率，就是我们要求的，n 个客人无一人拿对帽子的概率：

到此为止，文中开头的两个问题都已经得到了答案，而第三个问题的答案也呼之欲出了。
如果你熟悉微积分，那么肯定知道下面的麦克劳林级数：

代入 x=-1，我们得到了下面的结论：

截然不同于大多数人的直觉。
用一句话概括本文的结论：在完全随机的情况下，每个人都拿错的概率还是相当高的。
完。

暖

这个好。不过如果不用数学归纳法的话，容斥原理有什么比较好的证法吗？

感觉可以用概率、递推数列解决

群可真难，没接触过。但是看了看楼主解答问题的过程，感觉有点意思

竹