错排问题

**錯排問題**是組合數學中的問題之一。考慮一個有 $n$ 個元素的排列，若一個排列中所有的元素都不在自己原來的位置上，那麼這樣的排列就稱為原排列的一個**錯排**。 $n$ 個元素的錯排數記為 $D_{n}$ 或 $!n$ 。 研究一個排列錯排個數的問題，叫做**錯排問題**或稱為**更列問題**。

最早研究錯排問題的是尼古拉・伯努利和歐拉，因此歷史上也稱為伯努利 - 歐拉的裝錯信封的問題。這個問題有許多具體的版本，如在寫信時將 $n$ 封信裝到 $n$ 個不同的信封里，有多少種全部裝錯信封的情況？又比如四人各寫一張賀年卡互相贈送，有多少種贈送方法？自己寫的賀年卡不能送給自己，所以也是典型的錯排問題。

## 定義

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

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

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

 $D_{n}=nD_{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\%$ 。

## 歷史

18 世紀的法國數學家尼古拉・伯努利（1687-1759 年）是最早考慮這個問題的人。之後歐拉也開始對這個問題感興趣，並稱之為「組合數學中的一個奇妙問題」（拉丁文：_a quaestio curiosa ex doctrina combinationis_），並獨立解決了這個問題。

## 研究錯排問題的方法

### 枚舉法

對於情況較少的排列，可以使用枚舉法。

* 當 n=1 時，全排列只有一種，不是錯排，D1 = 0。
* 當 n=2 時，全排列有兩種，即 1、2 和 2、1，後者是錯排，D2 = 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 是錯排，D3=2。用同樣的方法可以知道 D4=9。
* 最小的幾個錯排數是：D1 = 0，D2 = 1，D3=2，D4 = 9，D5 = 44，D6 = 265，D7 = 1854。

### 遞推數列法

對於排列數較多的情況，難以採用枚舉法。這時可以用遞歸思想推導錯排數的遞迴關係式。

顯然 D1=0，D2=1。當 n≥3 時，不妨設 n 排在了第 k 位，其中 k≠n，也就是 1≤k≤n-1。那麼我們現在考慮 k 的情況。

* 當 k 排在第 n 位時，除了 n 和 k 以外還有 n-2 個數，其錯排數為 Dn-2。
* 當 k 不排在第 n 位時，那麼將第 n 位重新考慮成一個新的「第 k 位」，這時的包括 k 在內的剩下 n-1 個數的每一種錯排，都等價於只有 n-1 個數時的錯排（只是其中的第 k 位會換成第 n 位）。其錯排數為 Dn-1。

所以當 n 排在第 k 位時共有 Dn-2+Dn-1 種錯排方法，又 k 有從 1 到 n-1 共 n-1 種取法，我們可以得到：

　
: Dn=(n-1)(Dn-1+Dn-2)

在上面我們得到

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

從這個公式中我們可以推出 Dn 的通項公式，方法如下：

為書寫方便，記 Dn = n!Mn，則 M1 = 0, M2 = ${\frac {1}{2}}$

當 n 大於等於 3 時，由

Dn = (n-1)(Dn-1 + Dn-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}$ 。

所以， $nM_{n}-nM_{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{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}}$

將上面式子分邊累加，得

$$
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}$ ，錯排結果為 $\displaystyle \prod _{r=1}^{n}(s-x_{r})$ 中 $\displaystyle \prod _{r=1}^{n}x_{r}$ 的係數

記 $a_{r}=(-1)^{r}\sum x_{1}x_{2}...x_{r}$ 為基本對稱多項式，

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

從 $a_{r}$ 選出 $x_{1},x_{2},...,x_{r}$ ，然後從 $s^{n-r}$ 選出 $x_{r+1},x_{r+2},...,x_{n}$ ，組成 $\displaystyle \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)!
$$

種可能

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

## 簡化公式

錯位排列數的公式可以簡化為： $D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor ,$

其中的 $\lfloor n\rfloor $ 為高斯取整函數（小於等於 _n_ 的最大整數）。

這個簡化公式可以由之前的錯排公式推導出來。事實上，考慮指數函數在 0 處的泰勒展開：

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

所以， ${\frac {n!}{e}}-D_{n}=n!\,R_{n}$ 。其中 _Rn_ 是泰勒展開的餘項，_c_ 是介於 0 和 1 之間的某個實數。_Rn_ 的絕對值上限為

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

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

當 n≥2 時， ${\frac {1}{(n+1)}}$ 嚴格小於 0.5，所以 $D_{n}=n!\left({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}\right)$ 是最接近 ${\frac {n!}{e}}$ 的整數，可以寫成

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

## 參考資料