錯排問題

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

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

定義

記${\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-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) ^[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 .}$

參考資料

1. Sloane, N.J.A. (編). Sequence A000166 (Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
2. Heinrich Dörrie. Triumph der Mathematik: hundert berühmte Probleme aus zwei Jahrtausenden mathematischer Kultur. Courier Dover Publications. 1965 （英語）.第19-21頁
3. 盧開澄、盧華明. 《组合数学》. 清華大學出版社. ISBN 730213961X （中文（簡體））.
4. Miodrag Petković. Famous puzzles of great mathematicians. American Mathematical Soc. 2009. ISBN 9780821848142 （英語）.第184-186頁
5. Branislav Kisačanin. Mathematical problems and proofs: combinatorics, number theory, and geometry. Springer. 1998. ISBN 9780306459672 （英語）.第43-44頁