全错位排列是什么意思?

2025-03-15 07:36:41
推荐回答(2个)
回答1:

  全错位排列:即被著名数学家欧拉(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!)

回答2:

基本简介

全错位排列:即被著名数学家欧拉(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!)