全错位排列

概念：全错位排列，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∩...∩Am|=0!=1.

由容斥原理：

|A1∪A2∪...∪An|=n(n-1)!-C(n,2)(n-2)!+C(n,3)(n-3)!-...+(-1)^(n-1)C(n,n)*0!

=n!(1/1!-1/2!+...+(-1)^(n-1)*1/n!),

所以

Dn=n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)