錯位重排

簡介

表述為：編號是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)