記
為
上沒有不動點的排列(即
)的個數,
的值如下:(由
起)
- 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... [1]
不難發現,這個數列有一個規律,
。
例如有
封收件人不同的信,隨機放入
個寫了收件人地址的信封中寄出,求沒有一個收件人收到他所應接收的信的機率。當
,設四封信為ABCD,則在
個排列之中,只有9個是錯排,即
:
- BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA
所以其機率為
。
18世紀的法國數學家尼古拉·伯努利(1687-1759年)是最早考慮這個問題的人。之後歐拉也開始對這個問題感興趣,並稱之為「組合數學中的一個奇妙問題」(拉丁文:a quaestio curiosa ex doctrina combinationis),並獨立解決了這個問題[2]。
對於情況較少的排列,可以使用枚舉法[3]。
- 當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。[4]
對於排列數較多的情況,難以採用枚舉法。這時可以用遞歸思想推導錯排數的遞迴關係式。
顯然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) [2]
在上面我們得到
Dn=(n-1)(Dn-1+Dn-2)
從這個公式中我們可以推出Dn的通項公式,方法如下:
為書寫方便,記Dn = n!Mn,則M1 = 0, M2 =
當n大於等於3時,由
Dn = (n-1)(Dn-1 + Dn-2),
即
。
所以,
。
於是有
所以
![{\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}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/66eed270adf73a9b0dd9e04cfd2eb0eaa8893666)
將上面式子分邊累加,得
因此,我們得到錯排公式
錯排,
需排在
、
需排在
如此類推。
記
,錯排結果為
中
的係數
記
為基本對稱多項式,
從
選出
,然後從
選出
,組成
從
選出r個x有
種可能,從
選出其餘的n-r個x有
種可能
![{\displaystyle \displaystyle \sum _{r=2}^{n}(-1)^{r}C_{r}^{n}(n-r)!=n!\sum _{r=2}^{n}{\frac {(-1)^{r}}{r!}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/6f0c948a399f10351b438cea0dff53786f5672cd)
Heinrich Dörrie. Triumph der Mathematik: hundert berühmte Probleme aus zwei Jahrtausenden mathematischer Kultur. Courier Dover Publications. 1965 (英語).第19-21頁