欢迎来到天天文库
浏览记录
ID:20217128
大小:44.00 KB
页数:4页
时间:2018-10-11
《装错信封问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、考公务员,就上591UP公务员考试平台(http://gwy.591up.com)装错信封问题 1问题的提出1)同室四人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送出的贺年卡.则四张贺年卡的不同分配方式有[] A.6种B.9种C.11种D.23种 2)有5个客人参加宴会,他们把帽子放在衣帽寄放室内,宴会结束后每人戴了一顶帽子回家.回家后,他们的妻子都发现他们戴了别人的帽子.问5个客人都不戴自己帽子的戴法有多少种? 上述两个问题,实质上是完全一样的.是被著名数学家欧拉(LeonhardEuler,17
2、07-1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例.“装错信封问题”是由当时最有名的数学家约翰·伯努利(JohannBernoulli,1667-1748)的儿子丹尼尔·伯努利(DanidBernoulli,1700-1782)提出来的,大意如下: 一个人写了n封不同的信及相应的n个不同的信封,他把这n封信都装错了信封,问都装错信封的装法有多少种? 2建立数学模型 “装错信封问题”及两个特例,其实就是n个不同元素的一类特殊排列问题,本文试就给出这类问题的数学模型及求解公式.为方便,我们先把
3、n个不同的元素及相应的位置都编上序号1,2,…,n,并且约定:在n个不同元素的排列中 1°若编号为i(i=1,2,…,n)的元素排在第i个位置,则称元素i在原位;否则称元素i不在原位. 2°若所有的元素都不在原位,则称这种排列为n个不同元素的一个错排(若每个元素都在原位则称为序排). 按照上面约定,“装错信封问题”即为n个不同元素的错排问题,则可构建“装错信封问题”的数学模型为 在n个不同元素的全排列中,有多少种不同的错排? 3模型求解 应用集合中的容斥原理,我们就可得到“装错信封问题”的数学模型的求解
4、公式.591UP公务员考试平台(http://gwy.591up.com)考公务员,就上591UP公务员考试平台(http://gwy.591up.com) 设I表示n个不同元素的全排列的集合 Ai(i=1,2,…,n)为元素i在原位的排列的集合. Ai∩Aj(1≤i<j≤n)为元素i与j在原位的排列的集合. …… …… A1∩A2∩…∩An为n个元素的序排的集合. 则它们的排列数(即各个集合中元素的个数)分别为
5、I
6、=n!
7、Ai
8、=(n-1)!
9、Ai∩Aj
10、=(n-2)! ……
11、 ……
12、A1∩A2∩…∩An
13、=(n-n)!=0! 所以,根据容斥原理即得“装错信封问题”的数学模型的求解公式(即n个不同元素的错排数)为 591UP公务员考试平台(http://gwy.591up.com)考公务员,就上591UP公务员考试平台(http://gwy.591up.com) 4应用举例 一个元素的错排数显然为0,二个不同元素的错排数为1,三个不同元素的错排数为2,均可由公式验证,由公式还可求得四个不同元素的错排数为 五个不同元素的错排数为 则本文开头的问题1)共有9种不
14、同的分配方式,故选(B).问题2)共有44种不同的戴法,下面再举几例说明公式的应用. 例1设有编号为1,2,3,4,5的五个球和编号为1,2,3,4,5的五个盒子,现将这五个球投放入五个盒内,要求每个盒内投放一个球,并且恰好有两个球的编号与盒子的编号相同,则这样的投放方法的总数为[] A.20种B.30种 C.60种D.120种 解本题实质上是三个元素的错排问题,但由于题中未指明是哪三个元素进行的错排,故本题可分两步求解. 591UP公务员考试平台(http://gwy.591up.com)考公务员,就上
15、591UP公务员考试平台(http://gwy.591up.com) 第二步,对已选出的三个元素进行错排,有2种. 例2某省决定对所辖8个城市的党政一把手进行任职交流,要求把每个干部都调到另一个城市去担任相应的职务.问共有多少种不同的干部调配方案? 解实质上本题即为8个不同元素的错排问题,一种干部调配方法对应于8个不同元素的一个错排.故由公式可求得不同的干部调配方案数为591UP公务员考试平台(http://gwy.591up.com)
此文档下载收益归作者所有