公式是
D[n] = (n-1)(D[N-1] + D[n-2])
假設n個數是從1到n，
n個位置（或者說信封）是從p1到pn。
將數字分為兩種1~(n-1)，和n。
第一種分有(n-1)個數，針對每個數考慮有幾種排列，假設當前考慮的是數字k
顯然數字k不能放在pk上（否則不符合錯位的要求）
公式第一部分
考慮將k放在pn上，將n放在pk上，這樣n和k就滿足了錯位的要求。
那麼在這種情況下，有多少種排列呢？因為n個數字中，2個數字固定，所以相當於剩下n-2個數字的錯排數量：D[n-2]
公式第二部分
這一部分稍難理解。
同樣，k還是放在pn上，但是此時同樣也不允許n放在pk上，也就是將n也放入剩下的n-2個數字中進行錯排，此時有D[n-1]種組合。
這裡的關鍵點在於，n-1個數錯排，所謂錯排，就有相應的對排(原位置)，除k以外，其他數字原位置就是她們的數字位置，但數字n的原位置在哪呢？
在k。即這種情況下k的位置出現數字n是不允許的。
這有兩層含義：
這種情況下，就完全符合D[n-1]的情況
這樣n不允許在k處，也就和公式第一部分數量不重複。同時又和第一種情況完全互補
合併
由於有n-1個（公式第一部分+公式第二部分），所以最後公式為
公式是
D[n] = (n-1)(D[N-1] + D[n-2])
假設n個數是從1到n，
n個位置（或者說信封）是從p1到pn。
將數字分為兩種1~(n-1)，和n。
第一種分有(n-1)個數，針對每個數考慮有幾種排列，假設當前考慮的是數字k
顯然數字k不能放在pk上（否則不符合錯位的要求）
公式第一部分
考慮將k放在pn上，將n放在pk上，這樣n和k就滿足了錯位的要求。
那麼在這種情況下，有多少種排列呢？因為n個數字中，2個數字固定，所以相當於剩下n-2個數字的錯排數量：D[n-2]
公式第二部分
這一部分稍難理解。
同樣，k還是放在pn上，但是此時同樣也不允許n放在pk上，也就是將n也放入剩下的n-2個數字中進行錯排，此時有D[n-1]種組合。
這裡的關鍵點在於，n-1個數錯排，所謂錯排，就有相應的對排(原位置)，除k以外，其他數字原位置就是她們的數字位置，但數字n的原位置在哪呢？
在k。即這種情況下k的位置出現數字n是不允許的。
這有兩層含義：
這種情況下，就完全符合D[n-1]的情況
這樣n不允許在k處，也就和公式第一部分數量不重複。同時又和第一種情況完全互補
合併
由於有n-1個（公式第一部分+公式第二部分），所以最後公式為
D[n] = (n-1)(D[N-1] + D[n-2])