5個元素全錯位的排列公式

當n個編號元素放在n個編號位置，元素編號與位置編號各不對應的方法數用D(n)表示，那麼D(n-1)就表示n-1個編號元素放在n-1個編號位置，各不對應的方法數，其它類推.

第一步，把第n個元素放在一個位置，比如位置k，一共有n-1種方法

第二步，放編號為k的元素，這時有兩種情況：⑴把它放到位置n，那麼，對於剩下的n-1個元素，由於第k個元素放到了位置n，剩下n-2個元素就有D(n-2)種方法⑵第k個元素不把它放到位置n，這時，對於這n-1個元素，有D(n-1)種方法

綜上得到

D(n) = (n-1) [D(n-2) + D(n-1)]

特殊地，D(1) = 0， D(2) = 1.

下面通過這個遞推關係推導通項公式：

為方便起見，設D(k) = k! N(k)， k = 1， 2， …， n

則N(1) = 0， N(2) = 1/2.

n ≥ 3時，n! N(n) = (n-1) (n-1)! N(n-1) + (n-1)! N(n-2)

即 nN(n) = (n-1) N(n-1) + N(n-2)

D(1)＝0

D(2)=1

D(3)=2*(1+0)=2

D(4)=3*(2+1)=9

D(5)=4*(9+2)=44