錯排問題

維基百科,自由的百科全書
前往: 導覽搜尋

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

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

定義[編輯]

在[[組合出現在自己原本位置的排列動點的雙射

的值如下:(由起:)

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

例如有封寫好了的信,收件人不同,胡亂放入個寫了地址的信封中,寄出,求沒有一個收件人收到他所應接收的信的機率。當,在4! = 24個排列之中,只有9個是錯排:

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

所以有關幾率為9/24 = 37.5%

歷史[編輯]

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位重新考慮成一個新的「第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) [2]

在上面我們得到Dn=(n-1)(Dn-1+Dn-2) 從這個公式中我們可以推出Dn的通項公式,方法如下:

為書寫方便,記Dn = n!Mn,則M1 = 0, M2 =

當n大於等於3時,由Dn = (n-1)(Dn-1 + Dn-2),即。 所以,

於是有

所以

將上面式子分邊累加,得

因此,我們得到錯排公式

多項式模擬[編輯]

錯排,需排在需排在如此類推。

,錯排結果為的係數

基本對稱多項式

選出,然後從選出,組成

選出r個x有種可能,從選出其餘的n-r個x有種可能

簡化公式[編輯]

錯位排列數的公式可以簡化為:

其中的 高斯取整函數(小於等於 n 的最大整數)[5]

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

所以,。其中 Rn 是泰勒展開的餘項,c 是介於 0 和 1 之間的某個實數。Rn絕對值上限為

當 n≥2 時, 嚴格小於 0.5,所以 是最接近 的整數,可以寫成

參考資料[編輯]

  1. ^ OEIS:A000166
  2. ^ 2.0 2.1 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頁