全错位排列是什么意思？

　　全错位排列：即被著名数学家欧拉(Leonhard Euler，1707－1783)称为组合数论的一个妙题的“装错信封问题”。

　　“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli，1700－1782)提出来的，大意如下：

　　一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？

　　公式证明

　　n个相异的元素排成一排a1，a2，...，an。则ai(i=1，2，...，n)不在第i位的排列数为：

　　证明：

　　设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!)

基本简介

全错位排列：即被著名数学家欧拉(Leonhard Euler，1707－1783)称为组合数论的一个妙题的“装错信封问题”。
“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli，1700－1782)提出来的，大意如下：
一个人写了n封不同的信及相应的n个不同的信封，他把这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!)