簡介
表述為：編號是1、2、…、n的n封信，裝入編號為1、2、…、n的n個信封，要求每封信和信封的編號不同，問有多少種裝法？
對這類問題有個固定的遞推公式，記n封信的錯位重排數為Dn，則D1=0，D2=1，
Dn=（n-1）（Dn-2+Dn-1） 此處n-2、n-1為下標。
n>2
我們只需記住Dn的前幾項：D1=0，D2=1，D3=2，D4=9，D5=44。我們只需要記住結論，進行計算就可以。
【例】五個盒子都貼了標籤，全部貼錯的可能性有多少種？
即全貼錯標籤，N個項數全部排錯的可能數，可以總結出數列：
0，1，2，9，44，265，………
可以得到這樣一個遞推公式：（N-1）*（A+B）=C （A是第一項，B是第二項，C是第三項，N是項數）
s(n)=(n-1) [ s（n-1）+s（n-2）]
s(2)=1,s(3)=2
s(4)=3*(1+2)=9
s(5)=4*(2+9)=44
s(6)=5*(9+44)=265 ....................
公式由來 把編號 1-------------n的小球放到編號1------n的盒子裡，全錯位排列（1號球不在1號盒，2號球不在2號盒，依次類推），共有幾種情況？
------------------------------------------------------
設n個球全放錯的情況有 s（n）種
1號盒子可以選[2,n] 共（n-1）種選擇，設1號盒選擇某號球後對應的錯排次數是 a
（n-1）個選擇對應的錯排次數是相同的 ，則 s（n）=（n-1）a
不妨設1號盒選擇2號球
1： 2號盒選擇1號球，剩下 （n-2）個球去錯排，有 s（n-2）種情況
2： 2號盒不選擇1號球，則後面總有一個盒子選擇1號球，我們可以把1號球換成2號球，
對問題沒有影響，此時就相當於對（n-1）個球去錯排，有s（n-1）種情況
於是a= s（n-1)+s(n-2)
s(n)=(n-1) [ s（n-1）+s（n-2）]
s(2)=1,s(3)=2
s(4)=3*(1+2)=9
s(5)=4*(2+9)=44
s(6)=5*(9+44)=265 ....................
【例題】四位廚師聚餐時各做了一道拿手菜。現在要求每人去品嘗一道菜，但不能嘗自己做的那道菜。問共有幾種不同的嘗法？
A．6種 B．9種 C．12種 D．15種
根據4位廚師的錯位重排數D4=9，所以由公式可以看出是有9種。
通項公式
已經D1=0，D2=1，Dn=（n-1）（Dn-2+Dn-1），求Dn。
Dn = (n-1)Dn-1 + (n-1)Dn-2
Dn-nDn-1 = -[Dn-1 - (n-1)Dn-2]=(-1)^2*[Dn-2 - (n-2)Dn-3]=...(-1)^(n-2)*(D2-2D1)
設Dn-nDn-1=Cn
Cn=(-1)^(n-2)*1=(-1)^n
則 Dn = (-1)^n + nDn-1
兩邊同除(-1)^n
錯位重排設Dn/(-1)^n=Bn
Bn = 1 - nBn
兩邊同除n!
錯位重排設Bn/n!=An
An+An-1=1/n!..................(1)
An-1+An-2=1/(n-1)!.........(2)
............
A2+A1=1/2!......................(n-1)
A1+D1=0..........................(n)
(1)-(2)+(3)..............(n)得
錯位重排
錯位重排