《全错位排列数公式的推导与化简.docx》由会员分享，可在线阅读，更多相关《全错位排列数公式的推导与化简.docx（3页珍藏版）》请在金锄头文库上搜索。
1、全错位排列数公式的推导与化简一、提出问题 装错信封问题：一个人写了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推导如下：按分
2、步乘法计数原理考虑，第一步，先安排好第一个位置，有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种排法.12mnama1第二步，当安排好第一个位置后，假设
3、安排的是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，其中n2，nN+. （2）对于（1）式还有一种方
4、法：设满足题意的放法有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，n2.三、全错位排列数公式利用递推关系式Dn-nDn-1=（-1）n，各项同除以n！，得Dnn！-Dn-1（n-1）！=（-1）nn！，构造数列bn=Dnn！，并利用数列恒等式bn=b1+（b2-b1）+（b3-b2）+（bn-b
5、n-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=32D1+3（-1）2+（-1）3.由于D1=0，则D4=4D3+（-1）4=43（-1）2+4（-1）3+（-1）4，D5=5D4+（-1）5=543（-1）2+54（-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！.还有一种方法：利用递推关系式D
6、n=C1n-1（Dn-1+Dn-2），设Dk=k！pk，k=1、2、3、n，则p1=0，p2=12.当n3时，由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-
7、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）
8、与一个余项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（
9、n+1）！xn+1，可见二者形式相似.由于x=-1，因此e-1的幂级数的余项为Rn（-1）=（-1）n+1e（n+1）！，且（-1，0）.因此Dn=n！e-1-（-1）n+1en+1.设=|n！Rn|=|（-1）n+1en+1|=en+1，由于e（1e，1），当n=1时，12，由于n2，因此总有12.而Dn=n！e为整数.由取整函数（y=x表示不大于x的整数）的性质可知，无论（-1）n+1eun+1是正数还是负数，n！e+12的整数部分都一定与Dn的整数部分相同.例如对于整数n=（n-）+，（0，12），那么（n-）+12=n+12-=n；对于整数n=（n+）-，（0，12），那么（n+）+12=n+12=n；所以错排公式为Dn=n！e+0.5.五、公式应用例题将4名同学分配批改他们的4张考试卷，要求每个同学都不能批改自己的考试卷，那么有多少种不同的分配方案？解析利用错排公式，当n=4时，D4=4！e+0.5=9.也可利用递推公式Dn=nDn-1+（-1）n求得相同结果.
