六年级时，我曾在《数字——破解万物的钥匙》中看到了这么一个有趣的事实：

一群小伙子去游泳池游泳，他们的泳裤在同一个箱子里。当他们进入更衣室时，房间停电了。于是他们每个人随手抓了一件泳裤穿在身上，那么他们全部穿错自己的泳裤的概率是 $\dfrac1e$，即 $36.79\%$ 左右。

当时年少无知，并不知道其中的原理。而且最神奇也是最令人不解的是这里面居然出现了一个 $e$！

如今高二学习了排列组合，便研究了一番，却发现这里面大有其奥妙，并且这么一个概率问题竟涉及到排列组合、数列和导数，甚至跟集合有关！

本文假设读者理解大部分高中数学知识，那就让我们开始吧！

从错排开始讲起

事实上，我们要从一个高中常见的组合问题讲起：

四个信封和四封信一一对应，现在将信随便装入信封内，四封信全部装错一共有几种装法？

很显然，经过简单的分类讨论可以知道有 $9$ 种方法。事实上，这类问题叫做「错排问题」，下面给出一般定义。

定义

错排（错位全排列）问题，又称为伯努利欧拉装错信封问题，是指如下问题：

$n$ 个信封和信，将信随便装入信封内，所有信全部装错信封的方案数有多少种？

找出递推式

我们设 $n$ 封信的方案数为 $D_n$，那么显然 $D_1=0,D_2=1$。

上面我们已经知道 $D_4=9$。但是，如果有更多的信封，问题的难度会大幅上升，单靠分类讨论难以解决，因此我们需要一些更高级的做法，而建立递推式便是一个好方法，在这里我们就用这个方法。

那我们如何找到 $D_n$ 的递推式呢，我们可以这样想：

1. 先考虑第一封信，它不放在自己的信封里显然有 $(n-1)$ 种放法。
2. 如果上一步第一封信放在了第 $k$ 封信的信封里了，那么我们考虑第 $k$ 封信的位置，又有两种情况：
   • 它在第一封信的信封里，那么此时剩下的 $(n-2)$ 封信要满足错排的性质，方案数就是 $D_{n-2}$ 种。
   • 它不在第一封信的信封里，此时我们假装将第一封信装进第 $k$ 封信的信封并将信封扔掉，由于第 $k$ 封信不在第一封信的信封里，那么此时如果我们将第一封信的信封重命名为新的第 $k$ 封信的信封，事实上就是 $(n-1)$ 封信的错排，有 $D_{n-1}$ 种方案。

根据加法原理和乘法原理，我们便得到了 $D_n$ 的递推式：

$D_n=(n-1)(D_{n-1}+D_{n-2})\quad (n\ge2)$

向通项式出发

在这里我给出百度百科找到的由递推式变形得到通项式的方法，其中涉及到了一些“天眼”（即难以想到的步骤）和常用的数列处理方法。首先，第一步，要把递推式变形成这个样子：

$n!\dfrac{D_n}{n!}=(n-1)(n-1)!\dfrac{D_{n-1}}{(n-1)!}+(n-1)(n-2)!\dfrac{D_{n-2}}{(n-2)!}$

为什么这么变？因为这样能做出来。

实际上我也不知道为什么要这么变，这一步是最难的，我自己也没想到。实际上，我在解通项式是用的是生成函数的方法（详见下一节），期间还碰了壁。

两边可以同时约去一个 $(n-1)!$，并且作一些变形：

$\begin{aligned} n\dfrac{D_n}{n!}&=(n-1)\dfrac{D_{n-1}}{(n-1)!}+\dfrac{D_{n-2}}{(n-2)!}\\ n\left(\dfrac{D_n}{n!}-\dfrac{D_{n-1}}{(n-1)!}\right)&=-\dfrac{D_{n-1}}{(n-1)!}+\dfrac{D_{n-2}}{(n-2)!}\\ \dfrac{D_n}{n!}-\dfrac{D_{n-1}}{(n-1)!}&=-\dfrac{1}{n}\left(\dfrac{D_{n-1}}{(n-1)!}-\dfrac{D_{n-2}}{(n-2)!}\right)\\ \end{aligned}$

这里使用累乘的方法，有：

$\begin{aligned} \dfrac{D_n}{n!}-\dfrac{D_{n-1}}{(n-1)!}&=-\dfrac{1}{n}\left(\dfrac{D_{n-1}}{(n-1)!}-\dfrac{D_{n-2}}{(n-2)!}\right)\\ &=\left(-\dfrac{1}{n}\right)\left(-\dfrac{1}{n-1}\right)\left(\dfrac{D_{n-2}}{(n-2)!}-\dfrac{D_{n-3}}{(n-3)!}\right)\\ &=\left(-\dfrac{1}{n}\right)\left(-\dfrac{1}{n-1}\right)\cdots\left(-\dfrac{1}{3}\right)\left(\dfrac{D_2}{2!}-\dfrac{D_1}{1!}\right)\\ &=\left(-\dfrac{1}{n}\right)\left(-\dfrac{1}{n-1}\right)\cdots\left(-\dfrac{1}{3}\right)\left(-\dfrac{1}{2}\right)\left(-\dfrac{1}{1}\right)\\ &=\dfrac{(-1)^n}{n!} \end{aligned}$

再使用累加的方法，于是：

$\begin{aligned} &\dfrac{D_n}{n!}-\dfrac{D_1}{1!}\\ =&\left(\dfrac{D_n}{n!}-\dfrac{D_{n-1}}{(n-1)!}\right)+\left(\dfrac{D_{n-1}}{(n-1))!}-\dfrac{D_{n-2}}{(n-2)!}\right)+\cdots+\left(\dfrac{D_2}{2!}-\dfrac{D_1}{1!}\right)\\ =&\dfrac{(-1)^n}{n!}+\dfrac{(-1)^{n-1}}{(n-1)!}+\cdots+\dfrac{(-1)^2}{2!} \end{aligned}$

移项后我们便能得到错排问题的通项式了：

$D_n=n!\sum\limits_{k=2}^n\dfrac{(-1)^k}{k!}$

可能这个式子看着比较别扭，但是后面的求和号我们无法再精确地化简了。

当然，下标从 $2$ 开始可能有些许怪，由于 $\dfrac{(-1)^0}{0!}+\dfrac{(-1)^1}{1!}=0$，因此我们也可以写成：

$D_n=n!\sum\limits_{k=0}^n\dfrac{(-1)^k}{k!}$

如何让错排更好算

如果你将 $n$ 代入通项公式，你会发现 $D_n$ 算起来比较麻烦，这主要是其通项式中求和号造成的。

事实上，根据通项公式也可以得到一条比较简单的递推公式：

$D_n=nD_{n-1}+(-1)^n$

但递推式用起来还是没有通项式那么爽，因此接下来，我将带领你利用 $e^x$ 的泰勒展开式，得到错排通项公式的一个近似公式。

泰勒展开

泰勒展开就是利用求导构建一个多项式来逼近一个函数，它的优点就在于可以将复杂的函数化为多项式。用泰勒展开进行估算也是一个不错的选择。

那么具体怎么展开呢？这里有一个公式（这里我就直接写无穷和而非多项式估计了）：

$f(x)=\sum\limits_{k=0}^\infty{\dfrac{f^{(k)}(a)}{k!}(x-a)^k}$

其中 $f^{(k)}(x)$ 为 $f(x)$ 的 $k$ 阶导数（前提是要存在，否则不能展开）。

等号右边的式子就被称为 $f(x)$ 在 $x=a$ 处的泰勒展开。这个展开式会在 $x=a$ 处附近比较贴合原函数，估计的效果也越好。$f(x)$ 在 $x=0$ 处的泰勒展开也称为麦克劳林展开。

这里我给出一种比较直观的观点来证明它（但是并不严谨），假设展开式是长这样的：

$f(x)=\sum\limits_{k=0}^\infty{t_k(x-a)^k}$

其中 $\{t_n\}$ 是待定系数。那么我们接下来反复进行以下操作：

1. 代入 $x=a$ 得到 $t_k$ 的值。
2. 两边同时求导。

不难可以发现 $t_k=\dfrac{f^{(k)}(a)}{k!}$，其中 $k!$ 是多次求导累积形成的。

这里我们用到的是一个带有拉格朗日余项的泰勒展开，它的严格证明要用到拉格朗日中值定理，这里就不再补充了，感兴趣的读者可以自行查阅资料：

$f(x)=\sum\limits_{k=0}^n{\dfrac{f^{(k)}(a)}{k!}(x-a)^k}+R_n(x)$

其中 $R_n(x)=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}(x-a)^{n+1}$ 为余项，并且 $\xi$ 在 $x$ 与 $a$ 之间。

错排公式的近似公式

熟悉泰勒展开的同学当见到错排公式时一定有着一种熟悉的感觉，那便是 $e^x$ 的泰勒展开。

我们对 $e^x$ 进行展开，由于 ${(e^x)}^{(n)}=e^x$，因此：

$e^x=\sum\limits_{k=0}^n{\dfrac{x^k}{k!}}+\dfrac{e^\xi}{(n+1)!}x^{n+1}$

接下来，我们让 $x=-1$，就有：

$\dfrac1e=\sum\limits_{k=0}^n{\dfrac{{(-1)}^k}{k!}}+\dfrac{e^\xi}{(n+1)!}{(-1)}^{n+1}\quad\xi\in(-1,0)$

两边乘上 $n!$ 并移项取绝对值，得到：

$\left|\dfrac{n!}{e}-D_n\right|=\dfrac{e^\xi}{n+1}<\dfrac{1}{n+1}\le\dfrac12$

因此 $\dfrac{n!}{e}$ 与 $D_n$ 的误差不会超过 $\dfrac12$，也就意味着 $\dfrac{n!}{e}$ 四舍五入的结果便是 $D_n$，即：

$D_n=\left\lfloor\dfrac{n!}{e}+\dfrac12\right\rfloor$

其中，$\left\lfloor x+\dfrac12\right\rfloor$ 表示 $x$ 四舍五入得到的结果。

回到开头

那么接下来就可以回到开头，解决开头关于泳裤的疑问了。

由于 $n$ 个人各取一条泳裤是全排列问题，一共有 $n!$ 种取法。全部拿错自己泳裤的方案数又有 $D_n$ 种，那么全部拿错的概率便是：

$\dfrac{D_n}{n!}=\dfrac{\left\lfloor\dfrac{n!}{e}+\dfrac12\right\rfloor}{n!}\approx\dfrac{\dfrac{n!}{e}}{n!}=\dfrac1e\approx36.7\%$

补充：错排通项式的一些其它解法

这些解法是非常自然能够想到的，比上面逆天的数列处理方法好很多。

生成函数

生成函数就是一列用来展示一串数字的挂衣架。——赫伯特·维尔夫

生成函数（又称母函数）是求无穷和以及求数列通项的一个利器，我打算在此挖个坑，科普一下生成函数，因为这玩意很神奇，很好玩，还非常有用，基本可以做到指哪打哪，多难的问题都可以解决。

在我之前的文章 [研究] “复杂”的相遇问题 的文末，我提到了这么一个式子：

$1+x+x^2+\cdots=\dfrac{1}{1-x}$

等号左边事实上就是常数列 $a_n=1$ 的生成函数。我们通常可以通过递推将这么一个无穷和化为像等号右边的这个浓缩的形式。

接下来，跟着我的思路一步一步得到通项。

我们现在有 $S_1=0,S_2=1,S_n=(n-1)(S_{n-1}+S_{n-2})$，假设递推式对 $n=2$ 成立，那么可以设 $S_0=1$，这是为了方便计算。我们构建 $S_n$ 的生成函数：

$f(x)=\sum\limits_{k=0}^\infty S_kx^k=S_0+S_1x+S_2x^2+S_3x^3+\cdots$

那么：

$\begin{aligned} xf(x)&=S_0x+S_1x^2+S_2x^3+S_3x^4+\cdots\\ (x+1)f(x)&=S_0+(S_1+S_0)x+(S_2+S_1)x^2+(S_3+S_2)x^3+(S_4+S_3)x^4+\\ ((x+1)f(x))'&=(S_1+S_0)+2(S_2+S_1)x+3(S_3+S_2)x^2+4(S_4+S_3)x^3+\cdots\\ &=S_2+S_3x+S_4x^2+\cdots\\ &=\dfrac{f(x)-S_0-S_1x}{x^2}\\ \end{aligned}$

得到关系式后，我们再变下形：

$\begin{aligned} ((x+1)f(x))'&=\dfrac{f(x)-S_0-S_1x}{x^2}\\ x^2(x+1)f'(x)+x^2f(x)&=f(x)-1\\ f'(x)+\dfrac{x-1}{x^2}f(x)&=-\dfrac{1}{x^2(x+1)}\\ \end{aligned}$

接下来便是求一个微分方程的事。式子两边乘上待定函数 $\beta(x)$，其中满足 $\beta'(x)=\dfrac{x-1}{x^2}\beta(x)$。

那么很显然 $\beta(x)=e^{I}$，其中 $I=\displaystyle\int\dfrac{x-1}{x^2}dx=\ln x+\dfrac{1}{x}$，即 $\beta(x)=xe^\frac1x$。因此：

$\begin{aligned} {\left(\beta(x)f(x)\right)}'&=-\dfrac{\beta(x)}{x^2(x+1)}\\ {\left(xe^\frac{1}{x}f(x)\right)}'&=-\dfrac{e^\frac{1}{x}}{x(x+1)} \end{aligned}$

当我做到这一步时，原本下一步应该是两边积分的，但是我发现右边这玩意积不出来啊！！没办法，这条路最终以失败告终。

但是我突然想起还有个很类似的东西叫做指数型母函数。我们上面用的是普通型母函数，这两种母函数形式非常相似，但是又有区别：

形式上说，普通型生成函数用于解决多重集的组合问题，而指数型母函数用于解决多重集的排列问题。

我们这种属于排列问题，因此指数型母函数也许能做出来。我们建立 $D_n$ 的指数型母函数：

$g(x)=\sum\limits_{k=0}^\infty S_k\dfrac{x^k}{k!}=S_0+S_1x+S_2\dfrac{x^2}{2}+S_3\dfrac{x^3}{3!}+\cdots$

那么：

$\begin{aligned} g'(x)&=S_1+S_2x+S_3\dfrac{x^2}{2}+S_4\dfrac{x^3}{3!}+\cdots\\ g'(x)+g(x)&=(S_1+S_0)+(S_2+S_1)x+(S_3+S_2)\dfrac{x^2}{2}+(S_4+S_3)\dfrac{x^3}{3!}+\cdots\\ &=S_2+S_3\dfrac{x}{2}+S_4\dfrac{x^2}{3!}+S_5\dfrac{x^3}{4!}\\ &=\dfrac{g'(x)-S_1}{x}=\dfrac{g'(x)}{x} \end{aligned}$

因此：

$\begin{aligned} g'(x)+g(x)&=\dfrac{g'(x)}{x}\\ (x-1)g'(x)+xg(x)&=0 \end{aligned}$

这个式子可顺眼太多了，炮制之前解微分方程的方法（即凑导数），我们可以得到：

$\begin{aligned} ((x-1)e^xg(x))'&=0\\ g(x)&=\dfrac{C}{(x-1)e^x}\\ \end{aligned}$

其中 $C$ 为积分常量。根据 $g(0)=S_0=1$ 解得 $C=-1$。因此 $g(x)=\dfrac1{1-x}\cdot e^{-x}$

还记得上面讲到 $e^x$ 的泰勒展开吗，代入 $-x$ 得到：

$e^{-x}=\sum\limits_{k=0}^\infty{(-1)^k\dfrac{x^k}{k!}}$

以及再用上面提及到的 $1+x+x^2+\cdots=\dfrac{1}{1-x}$，可以展开 $g(x)$：

$\begin{aligned} g(x)&=(1+x+x^2+x^3+\cdots)(1-x+\dfrac{x^2}{2}-\dfrac{x^3}{3!}+\cdots)\\ &=\sum\limits_{k=0}^\infty\left(x^k\sum_{i=0}^k\dfrac{(-1)^i}{i!}\right) \end{aligned}$

对比每一个 $x^n$ 的系数，可以得到：

$\begin{aligned} \dfrac{D_n}{n!}&=\sum\limits_{k=0}^n\dfrac{(-1)^k}{k!}\\ D_n&=n!\sum\limits_{k=0}^n\dfrac{(-1)^k}{k!} \end{aligned}$

容斥原理

容斥原理在我们学集合时就已经学过：

$\begin{aligned} |A\cup B|&=|A|+|B|-|A\cap B|\\ |A\cup B\cup C|&=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\\ \end{aligned}$

根据这两条式子很容易可以想到它拓展到 $n$ 的形式：

$\left|\mathop{\Large\cup}\limits_{k=1}^nS_k\right|=\sum\limits_{k=1}^n{(-1)}^{k-1}\sum\limits_{1\le i_1<\cdots<i_k\le n}\left|\mathop{\Large\cap}\limits_{j=0}^kS_{i_j}\right|$

其中 $\left|\mathop{\Large\cup}\limits_{k=1}^nS_k\right|=S_1\cup\cdots\cup S_n$，$\left|\mathop{\Large\cap}\limits_{k=1}^nS_k\right|=S_1\cap\cdots\cap S_n$。

再搭配上德 · 摩根律：

$\begin{aligned} \left|\mathop{\Large\cap}\limits_{k=1}^n\overline{S_k}\right|&=\overline{\left|\mathop{\Large\cup}\limits_{k=1}^nS_k\right|}\\ &=|S|-\left|\mathop{\Large\cup}\limits_{k=1}^nS_k\right|\\ \end{aligned}$

得到这个能秒杀错排问题的公式（逐步淘汰原理）：

$\left|\mathop{\Large\cap}\limits_{k=1}^n\overline{S_k}\right|=|S|-\sum\limits_{k=1}^n{(-1)}^{k-1}\sum\limits_{1\le i_1<\cdots<i_k\le n}\left|\mathop{\Large\cap}\limits_{j=0}^kS_{i_j}\right|$

接下来，考虑这么 $n$ 个集合 $S_n$，其中 $|S_k|$ 表示第 $k$ 封信在自己信封里时，其它信封排列的方案数。那么：

$\begin{aligned}D_n&=\left|\mathop{\Large\cap}\limits_{k=1}^n\overline{S_k}\right|\\ &=|S|-\sum\limits_{k=1}^n{(-1)}^{k-1}\sum\limits_{1\le i_1<\cdots<i_k\le n}\left|\mathop{\Large\cap}\limits_{j=0}^kS_{i_j}\right|\\ &=n!-\sum\limits_{k=1}^n{(-1)}^{k-1}\sum\limits_{1\le i_1<\cdots<i_k\le n}(n-k)!\\ &=n!-\sum\limits_{k=1}^n{(-1)}^{k-1}C_n^k(n-k)!\\ &=n!-\sum\limits_{k=1}^n\dfrac{n!{(-1)}^{k-1}}{k!}\\ &=n!\sum\limits_{k=0}^n\dfrac{{(-1)}^{k}}{k!}\\ \end{aligned}$

当然了，错排公式也可以用二项式反演推得，本质上与容斥原理一样，这里就不再赘述了。