在HDU刷题时遇到了关于错排公式的一些问题。本篇文章将详细解释错排公式的推导过程。
错排的定义：一段序列中一共有n个元素，那么可知这些元素一共有n!种排列方法。假如在进行排列时，原来所有的元素都不在原来的位置，那么称这个排列为错排。而错排数所指的就是在一段有n个元素的序列中，有多少种排列方式是错排。
递归关系：Dn)=n-1)Dn-1)+Dn-2)) 特别地有D1)=0,D2)=1；
错排公式：Dn)=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元素进行错排的话，那么我们就可以得到了Dn-2)种 的错排方式。
2.若k号元素不排到第一个元素的位置，我们可以暂时将现在排在k号位置的第一个元素剔除出去，生下来的就只包含k号元素和原来n-2个的元素了。这时，我们可以将原来的第一个元素的位置看做是现在k号元素的原本位置，因为k号元素不能够放在原来的位置上，所以就相当于是原来的n-2个元素和k共计n-1个元素进行完全的错排。那么一共就有Dn-1)种方法。 第二种情况希望大家仔细理解！配一张图便于理解
那么，我们有根据加法原理，完成第二步有Dn-2)+Dn-1)种方法。
根据乘法原理得到Dn)=n-1)Dn-1)+Dn-2)) 。递推关系解释完毕。
下面我们来推一下错排公式
前提假设Dn)=n!Nn) 那么我们根据上面的递推公式可以得到n!Nn)=n-1)[n-2)!Nn-2)+n-1)!Nn-1)]，等式右边合并一下，我们可以得到
n!Nn)=n-1)!Nn-2)+n-1)!Nn-1)同时消去n-1)!可以得到nNn)=Nn-2)+Nn-1)
所以就有两边同时减去nNn-1)得到：nNn)-nNn-1)=n-1)Nn-1)+Nn-2)-nNn-1) 即有：nNn)-Nn-1))=-Nn-1)+Nn-2)
即为Nn)-Nn-1))/Nn-1)-Nn-2))=-1)/n;
同理有Nn-1)-Nn-2))/Nn-2)-Nn-3))=-1)/n-1);
Nn-2)-Nn-3))/Nn-3)-Nn-4))=-1)/n-2);
……
N3)-N2))/N2)-N1))=-1)/3;
一共我们得到了n-2个等式，我们可以让左边的等式相乘，右边的等式相乘，因为相消，那么我们可以得到的等式是
Nn)-Nn-1))/N2)-N1))=-1)^n-2)/[n*n-1)*n-2)*n-3)*……4*3] 等式1
又因为-1)^n-2)=-1)^n)
等式2并且N2)=D2)/2!=1/2 N1)=D1)/1!=0 所以有N2)-N1)=1/2
等式3 将这两个等式2和3带入到上面等式1中我们可以得到：
Nn)-Nn-1)=-1)^n/[n*n-1)*n-2)*n-3)*……*4*3*2] 即为：Nn)-Nn-1)=-1)^n/n!
所以有Nn)=-1)^2/2!+…-1)^n-1)/n-1)!+-1)^n/n! 又因为存在关系Dn)=n!Nn)
得到Dn)=n![-1)^2/2!+…-1)^n-1)/n-1)!+-1)^n/n! ] 得证
各位看官，推公式不易，且看且珍惜，THX。