装错信封问题即欧拉错排问题.doc

“装错信封问题”的数学模型与求解 某人写了n封信，同时写了n个信封，然后将信任意装入信封，问：每封信都装错的情况有多少种？ 排列、组合及简单计数问题． 计算题． 设这n封信依次为a、b、c…，第1封信a有（n﹣1）种放法，假设a放到了b对应的信封里，则b有（n﹣1）种放法；依此类推，分析随后的几封信的放法，进而由排列数公式计算可得答案． 解：设这n封信依次为a、b、c…， 则第1封信a有（n﹣1）种放法，假设a放到了b对应的信封里，则b有（n﹣1）种放法； 假设b放到了c对应的信封里，则c有（n﹣2）种放法； 假设c放到了d对应的信封里，则d有（n﹣3）种放法； … 依此类推，第n封信有1种放法； 则共有（n﹣1）（n﹣1）（n﹣2）（n﹣3）…1=（n﹣1）（n﹣1）!， 故每封信都装错的情况有（n﹣1）（n﹣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位的排列数为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!) 1 问题的提出 1)同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡．则四张贺年卡的不同分配方式有 A．6种 B．9种C．11种 D．23种 (1993年全国高考题理科17题) 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 模型求解 应用集合中的容斥原理，我们就可得到“装错信封问题”的数学模型的求解公式． 设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！ 　　 　　所以，根据容斥原理即得“装错信封问题”的数学模型的求解公