错排问题

记${\displaystyle D_{n}}$ 为${\displaystyle \{1,2,\dots ,n\}}$ 上没有不动点的排列(即${\displaystyle \phi :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\},\ \phi (i)\neq i,\ \forall 1\leq i\leq n}$ )的个数，${\displaystyle D_{n}}$ 的值如下：（由${\displaystyle n=1}$ 起）

0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... ^[1]

不难发现，这个数列有一个规律，

${\displaystyle D_{n}=nD_{n-1}+(-1)^{n}}$ 。

例如有${\displaystyle n}$ 封收件人不同的信，随机放入${\displaystyle n}$ 个写了收件人地址的信封中寄出，求没有一个收件人收到他所应接收的信的几率。当${\displaystyle n=4}$ ，设四封信为ABCD，则在${\displaystyle 4!=24}$ 个排列之中，只有9个是错排，即${\displaystyle !4=9}$ ：

BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA

所以其几率为

${\displaystyle {\frac {9}{24}}=37.5\%}$ 。

18世纪的法国数学家尼古拉·伯努利（1687-1759年）是最早考虑这个问题的人。之后欧拉也开始对这个问题感兴趣，并称之为“组合数学中的一个奇妙问题”（拉丁文：a quaestio curiosa ex doctrina combinationis），并独立解决了这个问题^[2]。

枚举法

对于情况较少的排列，可以使用枚举法^[3]。

• 当n=1时，全排列只有一种，不是错排，D₁ = 0。
• 当n=2时，全排列有两种，即1、2和2、1，后者是错排，D₂ = 1。
• 当n=3时，全排列有六种，即1、2、3；1、3、2；2、1、3；2、3、1；3、1、2；3、2、1，其中只有有3、1、2和2、3、1是错排，D₃=2。用同样的方法可以知道D₄=9。
• 最小的几个错排数是：D₁ = 0，D₂ = 1，D₃=2，D₄ = 9，D₅ = 44，D₆ = 265，D₇ = 1854。^[4]

递推数列法

对于排列数较多的情况，难以采用枚举法。这时可以用递归思想推导错排数的递回关系式。

显然D₁=0，D₂=1。当n≥3时，不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑k的情况。

• 当k排在第n位时，除了n和k以外还有n-2个数，其错排数为D_n-2。
• 当k不排在第n位时，那么将第n位重新考虑成一个新的“第k位”，这时的包括k在内的剩下n-1个数的每一种错排，都等价于只有n-1个数时的错排（只是其中的第k位会换成第n位）。其错排数为D_n-1。

所以当n排在第k位时共有D_n-2+D_n-1种错排方法，又k有从1到n-1共n-1种取法，我们可以得到：

D_n=(n-1)(D_n-1+D_n-2) ^[2]

在上面我们得到

D_n=(n-1)(D_n-1+D_n-2)

从这个公式中我们可以推出D_n的通项公式，方法如下：

为书写方便，记D_n = n!M_n，则M₁ = 0, M₂ = ${\displaystyle {\frac {1}{2}}}$ 

当n大于等于3时，由

D_n = (n-1)(D_n-1 + D_n-2)，

即

${\displaystyle n!M_{n}=(n-1)(n-1)!M_{n-1}+(n-1)(n-2)!M_{n-2}=n!M_{n-1}-(n-1)!M_{n-1}+(n-1)!M_{n-2}}$ 。

所以，${\displaystyle nM_{n}-nM_{n-1}=-M_{n-1}+M_{n-2}}$ 。

于是有 ${\displaystyle M_{n}-M_{n-1}=-{\frac {1}{n}}(M_{n-1}-M_{n-2})=...=(-{\frac {1}{n}})(-{\frac {1}{n-1}})...(-{\frac {1}{3}})(M_{2}-M_{1})=(-1)^{n}{\frac {1}{n!}}.}$ 

所以

${\displaystyle {\begin{aligned}M_{n}-M_{n-1}&=(-1)^{n}{\frac {1}{n!}}\\M_{n-1}-M_{n-2}&=(-1)^{(n-1)}{\frac {1}{(n-1)!}}\\\vdots \quad &=\quad \vdots \\M_{2}-M_{1}&=(-1)^{2}{\frac {1}{2!}}\\\end{aligned}}}$ 

将上面式子分边累加，得

${\displaystyle M_{n}=(-1)^{2}{\frac {1}{2!}}+(-1)^{3}{\frac {1}{3!}}...+(-1)^{n}{\frac {1}{n!}}.}$ 

因此，我们得到错排公式

${\displaystyle D_{n}=n!M_{n}=n!({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}).}$ 

${\displaystyle x_{1},x_{2},...,x_{n}}$ 错排，${\displaystyle x_{1}}$ 需排在${\displaystyle x_{2},x_{3},...,x_{n}}$ 、${\displaystyle x_{2}}$ 需排在${\displaystyle x_{1},x_{3},...,x_{n}}$ 如此类推。

记${\displaystyle s=\sum _{r=1}^{n}x_{r}}$ ，错排结果为${\displaystyle \displaystyle \prod _{r=1}^{n}(s-x_{r})}$ 中${\displaystyle \displaystyle \prod _{r=1}^{n}x_{r}}$ 的系数

记${\displaystyle a_{r}=(-1)^{r}\sum x_{1}x_{2}...x_{r}}$ 为基本对称多项式，

${\displaystyle \displaystyle \prod _{r=1}^{n}(s-x_{r})=\sum _{r=0}^{n}a_{r}s^{n-r}=\sum _{r=2}^{n}a_{r}s^{n-r}}$ 

从${\displaystyle a_{r}}$ 选出${\displaystyle x_{1},x_{2},...,x_{r}}$ ，然后从${\displaystyle s^{n-r}}$ 选出${\displaystyle x_{r+1},x_{r+2},...,x_{n}}$ ，组成${\displaystyle \displaystyle \prod _{r=1}^{n}x_{r}}$ 

从${\displaystyle a_{r}}$ 选出r个x有${\displaystyle C_{r}^{n}}$ 种可能，从${\displaystyle s}$ 选出其余的n-r个x有

${\displaystyle {\frac {(n-r)!}{1!1!...1!}}=(n-r)!}$ 

种可能

${\displaystyle \displaystyle \sum _{r=2}^{n}(-1)^{r}C_{r}^{n}(n-r)!=n!\sum _{r=2}^{n}{\frac {(-1)^{r}}{r!}}}$ 

错位排列数的公式可以简化为：${\displaystyle D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor ,}$ 

其中的 ${\displaystyle \lfloor n\rfloor }$  为高斯取整函数（小于等于 n 的最大整数）^[5]。

这个简化公式可以由之前的错排公式推导出来。事实上，考虑指数函数在 0 处的泰勒展开：

${\displaystyle {\begin{aligned}e^{-1}&=1+{\frac {\left(-1\right)^{1}}{1!}}+{\frac {\left(-1\right)^{2}}{2!}}+\cdots +\left(-1\right)^{n}{\frac {1}{n!}}+{\frac {e^{-c}}{(n+1)!}}\left(c-1\right)^{n}\\&={\frac {1}{2!}}-{\frac {1}{3!}}+\cdots +\left(-1\right)^{n}{\frac {1}{n!}}+R_{n}\\&={\frac {D_{n}}{n!}}+R_{n}\\\end{aligned}}}$ 

所以，${\displaystyle {\frac {n!}{e}}-D_{n}=n!\,R_{n}}$ 。其中 R_n 是泰勒展开的余项，c 是介于 0 和 1 之间的某个实数。R_n 的绝对值上限为

${\displaystyle |R_{n}|\leqslant {\frac {e^{0}}{(n+1)!}}={\frac {1}{(n+1)!}}}$ 

${\displaystyle {\Big |}{\frac {n!}{e}}-D_{n}{\Big |}\leqslant {\frac {n!}{(n+1)!}}={\frac {1}{(n+1)}}}$ 

当 n≥2 时，${\displaystyle {\frac {1}{(n+1)}}}$  严格小于 0.5，所以 ${\displaystyle D_{n}=n!\left({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}\right)}$  是最接近 ${\displaystyle {\frac {n!}{e}}}$  的整数，可以写成

${\displaystyle D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor .}$