装错信封问题
1 问题的提出
1)同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡．则四张贺年卡的不同分配方式有[ ] A．6种 B．9种 C．11种 D．23种
2)有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家．回家后，他们的妻子都发现他们戴了别人的帽子．问5个客人都不戴自己帽子的戴法有多少种？
上述两个问题，实质上是完全一样的．是被著名数学家欧拉(Leonhard Euler，1707－1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例．“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli，1700－1782)提出来的，大意如下：
一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？ 2 建立数学模型
“装错信封问题”及两个特例，其实就是n个不同元素的一类特殊排列问题，本文试就给出这类问题的数学模型及求解公式．为方便，我们先把n个不同的元素及相应的位置都编上序号1，2，„，n，并且约定：在n个不同元素的排列中
1° 若编号为i(i=1，2，„，n)的元素排在第i个位置，则称元素i在原位；否则称元素i不在原位．
2° 若所有的元素都不在原位，则称这种排列为n个不同元素的一个错排(若每个元素都在原位则称为序排)．
按照上面约定，“装错信封问题”即为n个不同元素的错排问题，则可构建“装错信封问题”的数学模型为
在n个不同元素的全排列中，有多少种不同的错排？ 3 模型求解
应用集合中的容斥原理，我们就可得到“装错信封问题”的数学模型的求解公式．
bbs.qzzn.com
QZZN公考指南之行测篇 BY 田老鼠
QZZN公考指南之行测篇 BY 田老鼠
设I表示n个不同元素的全排列的集合
Ai(i=1，2，„，n)为元素i在原位的排列的集合． Ai∩Aj(1≤i＜j≤n)为元素i与j在原位的排列的集合． „„
„„
A1∩A2∩„∩An为n个元素的序排的集合． 则它们的排列数(即各个集合中元素的个数)分别为 |I|=n！ |Ai|=(n－1)！ |Ai∩Aj|=(n－2)！ „„
„„
|A1∩A2∩„∩An|=(n－n)！=0！
所以，根据容斥原理即得“装错信封问题”的数学模型的求解公式(即n个不同元素的错排数)为
bbs.qzzn.com
QZZN公考指南之行测篇 BY 田老鼠
QZZN公考指南之行测篇 BY 田老鼠
4 应用举例
一个元素的错排数显然为0，二个不同元素的错排数为1，三个不同元素的错排数为2，均可由公式
验证，由公式
还可求得四个不同元素的错排数为
五个不同元素的错排数为
则本文开头的问题1)共有9种不同的分配方式，故选(B)．问题2)共有44种不同的戴法，下面再举几例说明公式的应用．
例1设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，则这样的投放方法的总数为
[ ]
A．20种 B．30种 C．60种 D．120种
解 本题实质上是三个元素的错排问题，但由于题中未指明是哪三个元素进行的错排，故本题可分两步求解．
bbs.qzzn.com
QZZN公考指南之行测篇 BY 田老鼠
QZZN公考指南之行测篇 BY 田老鼠
第二步，对已选出的三个元素进行错排，有2种．
例2 某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务．问共有多少种不同的干部调配方案？
解 实质上本题即为8个不同元素的错排问题，一种干部调配方法对应于8个不同元素的一个错排．故由公式
可求得不同的干部调配方案数为
bbs.qzzn.com
QZZN公考指南之行测篇 BY 田老鼠
因篇幅问题不能全部显示，请点此查看更多更全内容