欧拉-错装信封问题

错装信封问题

1 问题的提出

1)同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡．则四张贺年卡的不同分配方式有（ ）

A．6种 B．9种 C．11种 D．23种 （全国高考题理科17题)

2)有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家．回家后，他们的妻子都发现他们戴了别人的帽子．问5个客人都不戴自己帽子的戴法有多少种？

上述两个问题，实质上是完全一样的．是被著名数学家欧拉称为“组合数论的一个妙题”的“装错信封问题”的两个特例．“装错信封问题”是由当时最有名的数学家约翰·伯努利的儿子丹尼尔·伯努利提出来的，大意如下： 一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？

2 建立数学模型

“装错信封问题”及两个特例，其实就是n个不同元素的一类特殊排列问题，本文试就给出这类问题的数学模型及求解公式．为方便，我们先把n个不同的元素及相应的位置都编上序号1，2，„，n，并且约定：在n个不同元素的排列中 1° 若编号为i(i=1，2，„，n)的元素排在第i个位置，则称元素i在原位；否则称元素i不在原位．

2° 若所有的元素都不在原位，则称这种排列为n个不同元素的一个错排(若每个元素都在原位则称为序排)．

错排问题是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。n个元素的错排数记为Dn。研究一个排列错排个数的问题，叫做错排问题或称为更列问题。错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题：在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？有多少种至少有一封装入正确信封？

分析1：固定n个信封顺序，n封信均装错信封,实际上相当于{1,2, „, n} 错位排列问题。设Ai为第i封信装入正确信封的方法集合，则伯努利装错信封问题即为求n个性质均不满足的方法的个数，即

12...n

①设A为n个封信任意装入n个信封的方法集合，显然|A|=n!

②设Ai为第i封信装入正确信封的方法集合，显然| Ai |=(n-1)!

③第i1,i2,„,ik这k封信装入正确信封的方法集合，则

Ai1Ai2...Aik(nk)! 另外i1,i2,„,ik这k封信的选取有C(n,k)种方法

④根据容斥原理，n封信均没装入正确信封的方法数有

=n!12...n nnknnn(n1)!(n2)!...(1)(nk)!...(1)12kn(nn)! 

11(1)k(1)n=n!11!2!...k!...n!,另外，n封信中至少有一封装入正确信封 A1A2...An

=nnknnn(n1)!(n2)!...(1)(nk)!...(1)12kn(nn)!



=n!11111...(1)n1 n!1!2!3!4!

分析2 用A、B、C，„„，表示写着n位友人名字的信封，A、B、C……表示ｎ份相应的写好的信纸．把错装的总数为记作Dn．假设把A错装进B里了，包含着这个错误的一切错装法分两类：（1）B装入A里，这时每种错装的其余部分都与

A、B、无关，应有Dn2种错装法．（2）B装入A、B之外的一个信封，这时的装信工作实际是把（除A之外的）n1份信纸B、C，„„，装入（除B以外的）n1个信封A、C，„„，显然这时装错的方法有Dn1种．总之在A装入B的错误之下，共有错装法Dn1Dn2种．A装入C，装入D，„„的n2种错误之下，同样都有Dn1Dn2种错装法，因此Dn(n1)(Dn1Dn2)，这是递归表达式．下面证明Dn的表达式．

(n1)(Dn1Dn2)， （⊙）

由乘法和加法原理得：Dn

3 应用

例1 (上海高考题)设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，则这样的投放方法的总数为( )

A．20种 B．30种 C．60种 D．120种 选A

例2 某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务．问共有多少种不同的干部调配方案？答：14833

错装信封问题

1 问题的提出

1)同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡．则四张贺年卡的不同分配方式有（ ）

A．6种 B．9种 C．11种 D．23种 （全国高考题理科17题)

2)有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家．回家后，他们的妻子都发现他们戴了别人的帽子．问5个客人都不戴自己帽子的戴法有多少种？

上述两个问题，实质上是完全一样的．是被著名数学家欧拉称为“组合数论的一个妙题”的“装错信封问题”的两个特例．“装错信封问题”是由当时最有名的数学家约翰·伯努利的儿子丹尼尔·伯努利提出来的，大意如下： 一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？

2 建立数学模型

“装错信封问题”及两个特例，其实就是n个不同元素的一类特殊排列问题，本文试就给出这类问题的数学模型及求解公式．为方便，我们先把n个不同的元素及相应的位置都编上序号1，2，„，n，并且约定：在n个不同元素的排列中 1° 若编号为i(i=1，2，„，n)的元素排在第i个位置，则称元素i在原位；否则称元素i不在原位．

2° 若所有的元素都不在原位，则称这种排列为n个不同元素的一个错排(若每个元素都在原位则称为序排)．

错排问题是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。n个元素的错排数记为Dn。研究一个排列错排个数的问题，叫做错排问题或称为更列问题。错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题：在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？有多少种至少有一封装入正确信封？

分析1：固定n个信封顺序，n封信均装错信封,实际上相当于{1,2, „, n} 错位排列问题。设Ai为第i封信装入正确信封的方法集合，则伯努利装错信封问题即为求n个性质均不满足的方法的个数，即

12...n

①设A为n个封信任意装入n个信封的方法集合，显然|A|=n!

②设Ai为第i封信装入正确信封的方法集合，显然| Ai |=(n-1)!

③第i1,i2,„,ik这k封信装入正确信封的方法集合，则

Ai1Ai2...Aik(nk)! 另外i1,i2,„,ik这k封信的选取有C(n,k)种方法

④根据容斥原理，n封信均没装入正确信封的方法数有

=n!12...n nnknnn(n1)!(n2)!...(1)(nk)!...(1)12kn(nn)! 

11(1)k(1)n=n!11!2!...k!...n!,另外，n封信中至少有一封装入正确信封 A1A2...An

=nnknnn(n1)!(n2)!...(1)(nk)!...(1)12kn(nn)!



=n!11111...(1)n1 n!1!2!3!4!

分析2 用A、B、C，„„，表示写着n位友人名字的信封，A、B、C……表示ｎ份相应的写好的信纸．把错装的总数为记作Dn．假设把A错装进B里了，包含着这个错误的一切错装法分两类：（1）B装入A里，这时每种错装的其余部分都与

A、B、无关，应有Dn2种错装法．（2）B装入A、B之外的一个信封，这时的装信工作实际是把（除A之外的）n1份信纸B、C，„„，装入（除B以外的）n1个信封A、C，„„，显然这时装错的方法有Dn1种．总之在A装入B的错误之下，共有错装法Dn1Dn2种．A装入C，装入D，„„的n2种错误之下，同样都有Dn1Dn2种错装法，因此Dn(n1)(Dn1Dn2)，这是递归表达式．下面证明Dn的表达式．

(n1)(Dn1Dn2)， （⊙）

由乘法和加法原理得：Dn

3 应用

例1 (上海高考题)设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，则这样的投放方法的总数为( )

A．20种 B．30种 C．60种 D．120种 选A

例2 某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务．问共有多少种不同的干部调配方案？答：14833