错排问题

错排问题是组合数学中的问题之一。考虑一个有$n$个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 $n$个元素的错排数记为$D_n$或$!n$。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。

最早研究错排问题的是尼古拉·伯努利和欧拉，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将$n$封信装到$n$个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，所以也是典型的错排问题。

定義

記$D_n$為$\{1,2,\dots ,n\}$上沒有不動點的排列(即$\varphi :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\},\varphi (i)\ne i,\mathrm{\forall }1\le i\le n$)的個數，$D_n$的值如下：（由$n=1$起）

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

不難發現，這個數列有一個規律，

$D_n=n{D}_{n-1}+(-1{)}^n$。

例如有$n$封收件人不同的信，隨機放入$n$個寫了收件人地址的信封中寄出，求沒有一個收件人收到他所應接收的信的機率。當$n=4$，設四封信為ABCD，則在$4!=24$個排列之中，只有9個是錯排，即$!4=9$：

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

所以其機率為

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

历史

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

研究错排问题的方法

枚举法

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

• 当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。

递推数列法

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

显然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-1個空位(原本n個位置扣掉第k位)和n-1個數字，在排除了排在第k位的n後，由於k不在第n位，等價於把第n個空位改名為k的錯排問題。其错排数为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)

在上面我们得到

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

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

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

当n大于等于3时，由

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

即

$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}$。

所以，$n{M}_n-n{M}_{n-1}=-M_{n-1}+M_{n-2}$。

于是有 $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!}.$

所以

$\begin{array}{cc}{M}_n-M_{n-1}& =(-1{)}^n\frac{1}{n!}\\ M_{n-1}-M_{n-2}& =(-1{)}^{(n-1)}\frac{1}{(n-1)!}\\ ⋮& =⋮\\ M_2-M_1& =(-1{)}^2\frac{1}{2!}\\ \end{array}$

将上面式子分边累加，得

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

因此，我们得到错排公式

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

多项式模拟

$x_1,x_2,...,x_n$错排，$x_1$需排在$x_2,x_3,...,x_n$、$x_2$需排在$x_1,x_3,...,x_n$如此类推。

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

记$a_r=(-1{)}^r\sum x_1{x}_2...x_r$为基本对称多项式，

$\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}$

从$a_r$选出$x_1,x_2,...,x_r$，然后从$s^{n-r}$选出$x_{r+1},x_{r+2},...,x_n$，组成$\prod _{r=1}^n{x}_r$

从$a_r$选出r个x有$C_r^n$种可能，从$s$选出其余的n-r个x有

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

种可能

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

简化公式

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

其中的 $\lfloor n\rfloor$ 为高斯取整函数（小于等于 n 的最大整数）。

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

$\begin{array}{cc}{e}^{-1}& =1+\frac{{(-1)}^1}{1!}+\frac{{(-1)}^2}{2!}+\cdots +{(-1)}^n\frac{1}{n!}+\frac{e^{-c}}{(n+1)!}{(c-1)}^n\\ & =\frac{1}{2!}-\frac{1}{3!}+\cdots +{(-1)}^n\frac{1}{n!}+R_n\\ & =\frac{D_n}{n!}+R_n\\ \end{array}$

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

$|R_n|⩽\frac{e^0}{(n+1)!}=\frac{1}{(n+1)!}$

$|\frac{n!}{e}-D_n|⩽\frac{n!}{(n+1)!}=\frac{1}{(n+1)}$

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

$D_n=\lfloor \frac{n!}{e}+0.5\rfloor .$