全错位排列数公式的推导与化简.docx

全错位排列数公式的推导与化简 全错位排列数公式的推导与化简 一、提出问题 装错信封问题：一个人写了n封不同的信及相应的n个不同的信封，若他把这n封信都装错了信封，那么装错信封的装法共有多少种？这是被著名数学家欧拉称为“组合数论的一个妙题”. 把n个编号元素放在n个编号位置，元素编号与位置编号各不对应的排列方法称为错位排列法. 将编号分别为1，2，3，…，n的n个不同元素a1，a2，a3，…，an，安排在这n个位置作全排列，若某个排列中每个元素都错位，则把这个全排列称为这n个不同元素的一个全错位排列.n个不同元素所有的全错位排列的个数称为全错位排列数，记为Dn，易得D1=0，D2=1，D3=2. 二、递推关系式 对于n=4，D4推导如下：按分步乘法计数原理考虑，第一步，先安排好第一个位置，有C13=3种排法. 1234a3a1第二步，当安排好第一个位置后，假设安排的是a3，此时应考虑a1的位置，包括两种情况.若a1安排在第三个位置，则a2和a4排法是D2=1；若a1不安排在第三个位置，而a2不排在第二个位置，a4不排在第4个位置，对应的排法是D3=2.因此，当第一个位置安排的是a3时，对应 的排法共有D2+D3=3，而第一个位置安排的各种情况地位相当，所以D4=C13（D2+D3）=9. 对于Dn，推导如下： 按分步乘法计数原理考虑，第一步，先安排好第一个位置，有C1n-1=n-1种排法. 12…m…nama1第二步，当安排好第一个位置后，假设安排的是am，此时应考虑a1所放的位置，包括两种情况. 若a1安排在第m个位置，则对应的排法是Dn-2；若a1不安排在第m个位置，由于a2不排在第二个位置，…，an不排在第n个位置，对应的排法是Dn-1.因此，当第一个位置安排的是an时，对应的排法共有Dn-1+Dn-2.而第一个位置安排的各种情况地位相当，所以Dn=C1n-1（Dn-1+Dn-2）. （1）整理Dn-nDn-1=-[Dn-1-（n-1）Dn-2].这表明，{Dn-nDn-1}是以D2-2D1=1为首项，公比为-1的等比数列，于是 Dn-nDn-1=（-1）n-2，故Dn=nDn-1+（-1）n，其中n≥2，n ∈N+. （2） 对于（1）式还有一种方法：设满足题意的放法有Dn种，当加入第n+1个元素和编号时，对于Dn的每一种放法，都可以把第i（i=1，2，3，…，n）个元素与第n+1个元素互换，把第i个元素放入第n+1个位置，有nDn种放法；也可先把第n+1个元素放入第i个位置，还余下n个位置，而把第i 个元素不放入第n+1个位置，其它元素也不放在对应的位置， 则此时有nDn-1种放法，所以Dn+1=nDn+nDn-1，n≥2. 三、全错位排列数公式 利用递推关系式Dn-nDn-1=（-1）n，各项同除以n！，得Dnn！-Dn-1（n-1）！=（-1）nn！，构造数列bn=Dnn！，并利用数列恒等式bn=b1+（b2-b1）+（b3-b2）+…+（bn-bn-1）有Dnn！=01！+（-1）22！+（-1）33！+…+（-1）nn！，所以Dn=n！[12！-13！+…+（-1）n1n！]. 下面根据Dn=nDn-1+（-1）n利用分步迭代法推导Dn. D2=2D1+（-1）2，D3=3D2+（-1）3=3×2D1+3（-1）2+（-1）3.由于D1=0，则D4=4D3+（-1）4=4×3（-1）2+4（-1）3+（-1）4，D5=5D4+（-1）5=5×4×3（-1）2+5×4（-1）3+5（-1）4+（-1）5=5！2！（-1）2+5！3！（-1）3+5！4！（-1）4+5！5！（-1）5，…，所以Dn=n！[12！-13！+…+（-1）n1n！]. 还有一种方法： 利用递推关系式Dn=C1n-1（Dn-1+Dn-2），设Dk=k！pk，k=1、2、3、…、n，则p1=0，p2=12. 当n≥3时，由Dn=（n-1）（Dn-1+Dn-2）得n！pn=（n-1）（n-1）！pn-1+（n-1）（n-2）！pn-2，即n（n-1）！pn=（n-1）（n-1）！pn-1+（n-1）！pn-2，可知npn=（n-1）pn-1+pn-2，即npn=npn-1-pn-1+pn-2，则pn-pn-1=-pn-1-pn-2n， pn-1-pn-2=-pn-2-pn-3n-1，……，因此有pn-pn-1=（-1n）（-1n-1） （-1n-2）…（p2-p1）=（-1）n1n！，pn-1-pn-2=（-）n-11（n-1）！，…，p2-p1=（-1）212！. 各式两边相加得pn=12！-13！+…+（-1）n1n！. 所以Dn=n！pn=n！[1-11！+12！-13！+…+（-1）n1n！]. 四、化简公式 由于e-1=1-11！+12！-13！+…+（-1）n1n！+…，e=2.71828. 即e-1=pn+（-1）n+11（n+1）！+（-1）n+21（n+2）！+… 余项为Rn=（-1）n+11（n+1）！+（-1）n+21（n+2）！+…=（-1）n+11（n+1）！（1-1n+2）+… 那么该余项取值范围如何呢？由泰勒中值定理可知，在含有x0的某个开区间（a，b）内，函数f（x）可表示为（x-x0）的一个n次多项式pn（x）与一个余项Rn（x）之和，此和是关于（x-x0）的幂级数即泰勒级数，其中pn（x）=f（x0）+f ′（x0）（x-x0）+f ″（x0）2！（x-x0）2+…+f （n）（x0）n！（x-x0）n， 余项为Rn（x）=f （n+1）（ξ）（n+1）！（x-x0）n+1. ξ在x与x0之间. 若将函数f（x）=ex展开成x的幂级数即麦克劳林级数，由于x0=0，f （n+1）（x）=ex，则ex=1+x+x22！+x33！+…+xnn！+…. 对于任何有限的x、ξ（ξ在0与x之间），余项为Rn （x）=eξ（n+1）！xn+1. 而函数f（x）=ex展开成x的幂级数中含有xn+1的项为f （n+1）（ξ）（n+1）！xn+1=ex（n+1）！xn+1，可见二者形式相似. 由于x=-1，因此e-1的幂级数的余项为Rn（-1）=（-1）n+1eξ（n+1）！，且ξ∈（-1，0）. 因此Dn=n！e-1-（-1）n+1eξn+1. 设λ=|n！Rn|=|（-1）n+1eξn+1|=eξn+1，由于eξ∈（1e，1），当n=1时，λ 。