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

1、全错位排列数公式的推导与化简一、提出问题装错信封问题：一个人写了。封不同的信及相应的n个 不同的信封，若他把这n封信都装错了信封，那么装错信封 的装法共有多少种？这是被著名数学家欧拉称为“组合数论 的一个妙题”.把n个编号元素放在n个编号位置，元素编号与位置编 号各不对应的排列方法称为错位排列法.将编号分别为1，2, 3,，n的n个不同元素a1，a2, a3,，2。，安排在这n个位置作全排列，若某个排列中每 个元素都错位，则把这个全排列称为这n个不同元素的一个 全错位排列.n个不同元素所有的全错位排列的个数称为全错 位排列数，记为Dn，易得D1=0，D2=1，D3=2.二、递推关系式对于n=4

2、，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种排法.12mnam

3、a1第二步，当安排好第一个位置后，假设 安排的是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-

4、1+ (-1) n，其中 nN2，n EN+. (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, nN2.三、全错位排列数公式利用递推关系式Dn-nDn-1= (-1) n,各项同除以n!, 得 Dnn！ -Dn-1 (n-1)！ =

5、 (-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=3X2D1+3 (-1)2+ (-1) 3.由于 D1=0，贝，D4=4D3+ (-1) 4=4X3 (-1) 2+4 (-1) 3+ (-1) 4, D5=5D4+ (-1) 5=5X4X

6、3 (-1) 2+5X4 (-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.当 nN3 时，由 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) ！

7、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-1

8、1! +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 (x

9、0) (x-x0) +f (x0) 2! (x-x0) 2+f (n) (x0) n!(x-x0)n，余项为 Rn (x) =f (n+1) (E) (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、E(E在0与x之间)，余项为Rn (x) =eE(n+1)! xn+1.而函数f (x) =ex展开成X的慕级数中含有xn+1的项为 f (n+1) ( E ) (n+1) ! xn+1 =ex (n+1) ! xn+1,可见二者形 式相似.由于x=-l,因此e-