在HDU刷題時遇到了關于錯排公式的一些問題。本篇文章将詳細解釋錯排公式的推導過程。
錯排的定義：一段序列中一共有n個元素，那麼可知這些元素一共有n!種排列方法。假如在進行排列時，原來所有的元素都不在原來的位置，那麼稱這個排列為錯排。而錯排數所指的就是在一段有n個元素的序列中，有多少種排列方式是錯排。
遞歸關系：D(n)=(n-1)(D(n-1)+D(n-2)) 特别地有D(1)=0,D(2)=1；
錯排公式：D(n)=(n!)[(-1)^0/0!+(-1)^1/(1!)+(-1)^2/(2!)+(-1)^3/(3!)+......+(-1)^n/(n!)]； 其中n!=n*(n-1)*(n-2)*......3*2*1 特别地有0!=1 1!=1
首先來對遞歸公式進行解釋：
n個不同的元素的一個錯排公式可以分作兩步完成：
第一步：假設我們錯排第一個元素，那麼它可以從2~n的位置任意選擇其中的一個，一共是有n-1種選擇。
第二步：錯排其餘n-1個元素，也是需要分情況和種類的。因為這需要看第一步的結果，如果第一個元素落在第k個位置上，第二步就需要把k号元素進行錯排，k号元素錯排位置的不同将導緻不同的情況會發生：
1.假設k号元素正好落在了第一個元素的位置，那麼就可以将第一個元素和第k個元素完全剔除出去，因為相當于隻是他們兩者互換了位置，其他元素暫時還沒有發生變動。留下來的n-2元素進行錯排的話，那麼我們就可以得到了D(n-2)種 的錯排方式。
2.若k号元素不排到第一個元素的位置，我們可以暫時将現在排在k号位置的第一個元素剔除出去，生下來的就隻包含k号元素和原來n-2個的元素了。這時，我們可以将原來的第一個元素的位置看做是現在k号元素的原本位置，因為k号元素不能夠放在原來的位置上，是以就相當于是原來的n-2個元素和k共計n-1個元素進行完全的錯排。那麼一共就有D(n-1)種方法。 第二種情況希望大家仔細了解！配一張圖便于了解
那麼，我們有根據加法原理，完成第二步有D(n-2)+D(n-1)種方法。
根據乘法原理得到D(n)=(n-1)(D(n-1)+D(n-2)) 。遞推關系解釋完畢。
下面我們來推一下錯排公式
前提假設D(n)=n!N(n) 那麼我們根據上面的遞推公式可以得到n!N(n)=(n-1)[(n-2)!N(n-2)+(n-1)!N(n-1)]，等式右邊合并一下，我們可以得到
n!N(n)=(n-1)!N(n-2)+(n-1)!N(n-1)同時消去(n-1)!可以得到nN(n)=N(n-2)+N(n-1)
是以就有兩邊同時減去nN(n-1)得到：nN(n)-nN(n-1)=(n-1)N(n-1)+N(n-2)-nN(n-1) 即有：n(N(n)-N(n-1))=-N(n-1)+N(n-2)
即為(N(n)-N(n-1))/(N(n-1)-N(n-2))=(-1)/n;
同理有(N(n-1)-N(n-2))/(N(n-2)-N(n-3))=(-1)/(n-1);
(N(n-2)-N(n-3))/(N(n-3)-N(n-4))=(-1)/(n-2);
......
(N(3)-N(2))/(N(2)-N(1))=(-1)/3;
一共我們得到了n-2個等式，我們可以讓左邊的等式相乘，右邊的等式相乘，因為相消，那麼我們可以得到的等式是
(N(n)-N(n-1))/(N(2)-N(1))=(-1)^(n-2)/[n*(n-1)*(n-2)*(n-3)*......4*3] 等式1
又因為(-1)^(n-2)=(-1)^(n)
等式2并且N(2)=D(2)/2!=1/2 N(1)=D(1)/1!=0 是以有N(2)-N(1)=1/2
等式3 将這兩個等式2和3帶入到上面等式1中我們可以得到：
N(n)-N(n-1)=(-1)^n/[n*(n-1)*(n-2)*(n-3)*......*4*3*2] 即為：N(n)-N(n-1)=(-1)^n/n!
是以有N(n)=(-1)^2/2!+...(-1)^(n-1)/(n-1)!+(-1)^n/n! 又因為存在關系D(n)=n!N(n)
得到D(n)=n![(-1)^2/2!+...(-1)^(n-1)/(n-1)!+(-1)^n/n! ] 得證
各位看官，推公式不易，且看且珍惜，THX。