錯排問題

錯排問題是組合數學中的問題之一。考慮一個有$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) \ne i,\ \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=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-1個空位(原本n個位置扣掉第k位)和n-1個數字，在排除了排在第k位的n後，由於k不在第n位，等價於把第n個空位改名為k的錯排問題。其錯排數為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}$。

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

將上面式子分邊累加，得

$$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_1x_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{align} 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 \\ <pre> &= \frac{1}{2!}-\frac{1}{3!}+\cdots+\left(-1\right)^n\frac{1}{n!} + R_n \\ &= \frac{D_n}{n!} + R_n \\ </pre> \end{align}$$

所以，$\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.$$