錯排問題比較難，但是也是經典算法問題

文章目錄

• • 1 錯排問題
  • 2 總結

1 錯排問題

家中陽臺有10盆不同的花，為保持新鮮感，希望每天重新擺放，使得每盆花都不在第一天放的位置。那么最多可以保持多少天每天擺法都不同？

這是一個典型的錯排問題。

錯排的定義：若一個 n 元素的全排列中所有的元素都不在本來的位置上，那么稱這個全排列就為原排列的一個錯排（derangement） 。

也稱作“伯努利-歐拉錯裝信封問題”（The Bernoulli-Euler problem of theMisaddressed letters） ——

• 小明給 n 個朋友寫信，邀請他們來家中聚會，結果粗心的他卻把請柬全都裝錯了信封。請問有多少種全部裝錯信封的情況

n 個元素的錯排的個數記為 D(n)，下面通過兩種計算方法來得到D（n）的值。

• 方法1：建立遞推關系：

第1步，選擇第 n 個元素的位置，共有n-1 種方法（假定放在編號為 k 的位置）；

第2步，選擇第 k 個元素的位置，有兩種可能：

1）第 k 個元素放在編號為 n 的位置，此時剩下的n-2 個元素進行錯排即可，方案數是 D(n-2)

2）或者第 k 個元素不在編號為 n 的位置，此時把編號為 n 的位置視作編號為 k 的位置， 將 n-1 個元素進行錯排即可， 方案數是 D(n-1)：

由此得到遞推關系D(n)=(n-1)(D(n-2)+D(n-1))，這個足以寫出遞歸代碼。

很容易得到初值 D(1)=0 和 D(2)=1。

如果不使用遞歸，可以使用這個計算結果進行循環。

• 方法2 ：應用容斥原理

則D（n） = n! - |$A1\cup A2$$\cup A3$$\cup ...\cup An$|

由容斥原理：

可得：

2 總結

• 學好數學

總結

以上是生活随笔為你收集整理的【离散数学中的数据结构与算法】十一 错排问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。