错位排列 有N封信和N个信封,每封信都不装在自己信封里的排列种数记作Dn,则 D1=0,D2=1,D3=2,D4=9,D5=44...为什么,是怎么算出来的?

错位排列 有N封信和N个信封,每封信都不装在自己信封里的排列种数记作Dn,则 D1=0,D2=1,D3=2,D4=9,D5=44...为什么,是怎么算出来的?
错位排列 有N封信和N个信封,每封信都不装在自己信封里的排列种数记作Dn,则 D1=0,D2=1,D3=2,D4=9,D5=44...
为什么,是怎么算出来的?

错位排列 有N封信和N个信封,每封信都不装在自己信封里的排列种数记作Dn,则 D1=0,D2=1,D3=2,D4=9,D5=44...为什么,是怎么算出来的?
D1=0
D2=1
Dn=A(n,n)-C(1,n)*Dn-1-C(2,n)*Dn-2-.-C(n-2,n)D2 -1 ,n>1
这个就是计算公式,可以验算
推断思路写的话比较多比较繁,如果需要可以一起讨论

比如有n封信，从第一个算起，第一封信可以放在2---n封信中，可能排列有n-1；如果它放在第x封信中，那么第x封信就有可能的排列n-2种；如果它放在第y封信中，那么第y封信就有可能的排列n-3种...
类推下去，所有信都放好，最后排列有(n-1)(n-2)(n-3)****[n-(n-1)]，就是(n-1)!，即它的阶乘。...

全部展开

比如有n封信，从第一个算起，第一封信可以放在2---n封信中，可能排列有n-1；如果它放在第x封信中，那么第x封信就有可能的排列n-2种；如果它放在第y封信中，那么第y封信就有可能的排列n-3种...
类推下去，所有信都放好，最后排列有(n-1)(n-2)(n-3)****[n-(n-1)]，就是(n-1)!，即它的阶乘。

收起

错位排列问题被著名数学家欧拉(Leonhard Euler，1707－1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例。“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli，1700－1782)提出来的。


其通常提法是：n个有序...

全部展开

错位排列问题被著名数学家欧拉(Leonhard Euler，1707－1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例。“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli，1700－1782)提出来的。


其通常提法是：n个有序元素，全部改变其位置的排列数是多少？所以称之为“错位”问题。
公式为：
n个相异的元素排成一排a1,a2,...,an,且ai(i=1,2,...,n)不在第i位的排列数为n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)
证明：
设1,2,...,n的全排列t1,t2,...,tn的集合为I,而使ti=i的全排列的集合记为Ai(1<=i<=n),
则Dn=|I|-|A1∪A2∪...∪An|.
所以Dn=n!-|A1∪A2∪...∪An|.
注意到|Ai|=(n-1)!,|Ai∩Aj|=(n-2)!,...,|A1∩A2∩...∩An|=0!=1.
由容斥原理：
Dn=n!-|A1∪A2∪...∪An|=n!-C(n,1)(n-1)!+C(n,2)(n-2)!-C(n,3)(n-3)!+...+(-1)^nC(n,n)*0!
=n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)

下面先给出一道错位排列题目，使你有直观感觉。
五个编号为1、2、3、4、5的小球放进5个编号为1、2、3、4、5的小盒里面，全错位排列（即1不放1，2不放2，3不放3，4不放4，5不放5，也就是说5个全部放错）一共有多少种放法？
【解析】：直接求5个小球的全错位排列不容易，我们先从简单的开始。
小球数/小盒数 全错位排列
1 0
2 1（即2、1）
3 2（即3、1、2和2、3、1）
4 9
5 44
6 265
当小球数/小盒数为1~3时，比较简单，而当为4~6时，略显复杂，考友只需要记下这几个数字即可（其实0，1，2，9，44，265是一个有规律的数字推理题，请各位想想是什么？）由上述分析可得，5个小球的全错位排列为44种。

收起