6个信封中装了文件,结果刚好装错了3个

装错信封问题即欧拉错排问题
中“信封装错问题”的数学模型及解法；
有人写了N封信，同时写了N个信封，然后任意把信放进信封里。

问:每个字母被错误地装入时有多少种情况？排列、组合和简单计数问题。

计算问题。

让我们假设n个字母是A，B，c。

第一个字母A 有(n-1)种子放置方法。

假设A被放置在对应于B的包络中，B具有(n-1)种子放置方法；通过类比，分析下列字母的位置，然后通过计算排列公式得到答案。

解决方法:如果N个字母是A，B，c…，那么第一个字母A有(N-1)放置方法，并且假设A被放置在对应于B的信封中，那么B有(N-1)放置方法；假设b被放置在对应于c的包络中，c具有(n-2)种子放置方法；假设C被放置在对应于D的包络中，D具有(n-3)种子放置方法；...等等，有一种方法可以释放字母n；还有(n-1) (n-1) (n-2) (n-3)...1 = (n-1) (n-1)！因此，每个字母都被错误地加载(n-1) (n-1)！备注:本主题检查逐步计数原则的应用，并注意使用假设方法解决问题。

著名数学家莱昂哈德·欧拉(1707-1783)将“错放包络问题”的两个特例称为“组合数论中的一个奇n*1/n！)证明:
设置总排列t1，t2，...，TN = 1，2，...，n为I，并将ti=i设置为Ai(1。

逻辑推理考试要求1.掌握逻辑推理的解题思路与基本方法：列表、假设、对比分析、数论分析法等2.培养学生的逻辑推理能力，掌握解不同题型的突破口3.能够利用所学的数论等知识解复杂的逻辑推理题知识结构逻辑推理作为数学思维中重要的一部分，经常出现在各种数学竞赛中，除此以外，逻辑推理还经常作为专项的内容出现在各类选拔考试，甚至是面向成年人的考试当中。

对于学生学习数学来说，逻辑推理既有趣又可以开发智力，学生自主学习研究性比较高。

本讲我们主要从各个角度总结逻辑推理的解题方法。

一、列表推理法逻辑推理问题的显著特点是层次多，条件纵横交错.如何从较繁杂的信息中选准突破口，层层剖析，一步步向结论靠近，是解决问题的关键.因此在推理过程中，我们也常常采用列表的方式，把错综复杂的约束条件用符号和图形表示出来，这样可以借助几何直观，把令人眼花缭乱的条件变得一目了然，答案也就容易找到了.二、假设推理用假设法解逻辑推理问题，就是根据题目的几种可能情况，逐一假设．如果推出矛盾，那么假设不成立；如果推不出矛盾，而是符合题意，那么假设成立．解题突破口：找题目所给的矛盾点进行假设三、体育比赛中的数学对于体育比赛形式的逻辑推理题，注意“一队的胜、负、平”必然对应着“另一队的负、胜、平”。

有时综合性的逻辑推理题需要将比赛情况用点以及连接这些点的线来表示，从整体考虑，通过数量比较、整数分解等方式寻找解题的突破口.四、计算中的逻辑推理能够利用数论等知识通过计算解决逻辑推理题.例题精讲一、列表推理法【例 1】徐、王、陈、赵四位师傅分别是工厂的木工、车工、电工和钳工，他们都是象棋迷。

（1）电工只和车工下棋；（2）王、陈两位师傅经常与木工下棋；（3）徐师傅与电工下棋互有胜负；（4）陈师傅比钳工下得好。

问：徐、王、陈、赵四位师傅各从事什么工种？【考点】逻辑推理【难度】☆☆【题型】解答【解析】徐是车工，王是钳工，陈是木工，赵是电工。

【答案】徐是车工，王是钳工，陈是木工，赵是电工【巩固】根据条件判断旅游团去了A、B、C、D、E中的哪几个地方？⑴如果去A，就必须去B；⑵D、E两地至少去一地；⑶B、C两地只能去一地；⑷C、E两地要去都去，要不去都不去；⑸若去D，则A、E两地必须去.【考点】逻辑推理【难度】☆☆【题型】解答【解析】从⑶入手，分别假设去B或C：⑶若去B则不能去C，⑷也不能去E，⑵只能去D.⑸必须去A、E，与不能去E矛盾.所以不能去B假设去C：⑷必去E，⑵需去D，⑸必须去A、E，⑴去A必须去B，与⑶B、C不能同去矛盾，所以不能去D．综上只能去C、E.【答案】只能去C、E.【例 2】老师在3个小箱中各放一个彩色球，让小明、小强、小亮、小佳四人猜一下各个箱子中放了什么颜色的球．小明说：“1号箱中放的是黄色的，2号箱中放的是黑色的，3号箱中放的是红色的．”小亮说：“1号箱中放的是橙色的，2号箱中放的是黑色的，3号箱中放的是绿色的．”小强说：“1号箱中放的是紫色的，2号箱中放的是黄色的，3号箱中放的是蓝色的．”小佳说：“1号箱中放的是橙色的，2号箱中放的是绿色的，3号箱中放的是紫色的．”老师说：“你们中有一个人恰好猜对了两个，其余的三人都只猜对一个．”那么3号箱子中放的是________色的球．【考点】逻辑推理【难度】☆☆【题型】解答【关键词】2008年，迎春杯【解析】由于猜中的总次数为5次，所以有一个箱子至少被猜中了2次以上，从而这个箱子只能是2号箱，推理得出只能是小亮对了2次，其他人只对一次，所以1号箱只能是橙色的，那么3号箱的颜色是蓝色的．【答案】蓝色【巩固】四张卡片上分别写着奥、林、匹、克四个字（一张上写一个字），取出三张字朝下放在桌上，A、B、C三人分别猜每张卡片上是什么字，猜的情况见下表：结果，有一人一张也没猜中，一人猜中两张，另一人猜中三张.问：这三张卡片上各写着什么字．【考点】逻辑推理【难度】☆☆【题型】解答【解析】A、B有两张猜的相同，必有一人全对，一人对两张，因此，C全错，推知B全对.【答案】林、匹、克【例 3】五封信，信封完全相同，里面分别夹着红、蓝、黄、白、紫五种颜色的卡片．现在把它们按顺序排成一行，让A、B、C、D、E五人猜每只信封内所装卡片的颜色．A猜：第2封内是紫色，第3封是黄色；B猜：第2封内是蓝色，第4封是红色；C猜：第1封内是红色，第5封是白色；D猜：第3封内是蓝色，第4封是白色；E猜：第2封内是黄色，第5封是紫色．然后，拆开信封一看，每人都猜对一种颜色，而且每封都有一人猜中．请你根据这些条件，再猜猜，每封信中夹什么颜色的卡片？【考点】逻辑推理【难度】☆☆【题型】解答【解析】把已知条件简明地记录在表格中．选择其中一只信封作为“突破口”．比如第3封，A猜的是黄色，D猜的却是蓝色．由已知条件，这只信封内的卡片不是蓝色，就是黄色．假如第3封是蓝色，那么逐步推理可导出矛盾：白色卡片没人猜对．这说明假设不正确，第3封内应是黄色．由此推出其它各封内的颜色．【答案】第1封内是红色，第2封内是蓝色，第3封内应是黄色，第4封是白色；第5封是紫色．【巩固】老师让小新把小胖、小贝、小丸子、小淘气、小马虎的作业本带回去，小新见到这五人后就一人给了一本，结果全发错了．现在知道：⑴小胖拿的不是小贝的，也不是小淘气的；⑵小贝拿的不是小丸子的，也不是小淘气的；⑶小丸子拿的不是小贝的，也不是小马虎的；⑷小淘气拿的不是小丸子的，也不是小马虎的；⑸小马虎拿的不是小淘气的，也不是小胖的．另外，没有两人相互拿错(例如小胖拿小贝的，小贝拿小胖的)．问：小丸子拿的是谁的本？小丸子的本被谁拿走了？【考点】逻辑推理【难度】☆☆【题型】解答【解析】根据“全发错了”及条件⑴～⑸，可以得到下表：由表1看出，小淘气的本被小丸子拿了．此时，再继续推理分析不大好下手，我们可用假设法．由上表知，小胖拿的本不是小丸子的就是小马虎的．先假设小胖拿了小丸子的本．于是得到下表，表中小贝拿小马虎的本，小马虎拿小贝的本．两人相互拿错，不合题意．再假设小胖拿小马虎的本．于是又可得表，经检验，下表符合题意．所以小丸子拿了小淘气的本，小丸子的本被小马虎拿去了．【答案】小丸子拿了小淘气的本，小丸子的本被小马虎拿去了二、假设推理【例 4】一位法官在审理一起盗窃案中，对涉及到的四名嫌疑犯甲、乙、丙、丁进行了审问．四人分别供述如下：甲说：“罪犯在乙、丙、丁三人之中．”乙说：“我没有作案，是丙偷的．”丙说：“在甲和丁中间有一人是罪犯．”丁说：“乙说的是事实．”经过充分的调查，证实这四人中有两人说了真话，另外两人说的是假话．同学们，请你做一名公正的法官，对此案进行裁决，确认谁是罪犯？【考点】逻辑推理【难度】☆☆【题型】解答【解析】如果甲说的是假话，那么剩下三人中有一人说的也是假话，另外两人说的是真话．可是乙和丁两人的观点一致，所以在剩下的三人中只能是丙说了假话，乙和丁说的都是真话．即“丙是盗窃犯”．这样一来，甲说的也是对的，不是假话．这样，前后就产生了矛盾．所以甲说的不可能是假话，只能是真话．同理，剩下的三人中只能是丙说真话．乙和丁说的是假话，即丙不是罪犯，乙是罪犯．又由甲所述为真话，即甲不是罪犯．再由丙所述为真话，即丁是罪犯．所以乙和丁是盗窃犯．【答案】乙和丁是盗窃犯【巩固】四个小朋友宝宝、星星、强强和乐乐在院子里踢足球，一阵响声，惊动了正在读书的陆老师，陆老师跑出来查看，发现一块窗户玻璃被打破了。

利用错排公式求解装错信封问题【问题背景】18世纪数学家约翰·伯努利(Johann Bernoulli ，1667—1748)的儿子丹尼尔·伯努利(Danid Bernoulli ，1700—1782)提出来这样一个问题：一个人写了n 封信，并且写了n 个对应的信封，这个人随机将这n 封信分别装入这n 个信封，问：都装错的情况有多少种?后来著名数学家欧拉对此产生浓厚兴趣，并称之为“组合理论的一个妙题”，并且给出了“装错信封问题”的一劳永逸的答案：设n 个信封都装错的情况数为n D ，那么11111(1)(1)!0!1!2!3!(1)!!n n n D n n n −⎡⎤−−=⋅−+−+⋅⋅⋅++⎢⎥−⎣⎦. 特别说明，以上公式是通过数列递推得来，为了简化约分运算，我们可以将上式化简为2311(1)(1)n n n n n n n n D A A A −−−=−+⋅⋅⋅+−+−.在这里，我们可以记忆一些常见的结果：123450,1,2,9,44D D D D D =====.【经典例题】重新排列1，2，3，4，5，6，7，8.（1）使得偶数在原来的位置上，而奇数不在原来的位置上，有多少种不同的排法？（2）使得偶数在奇数的位置上，而奇数在偶数的位置上，有多少种不同的排法？（3）使得偶数在偶数位置上，但都不在原来的位置上，奇数在奇数的位置上，但也都不在原来的位置上，有多少种不同的排法？（4）如果要有数在原来的位置上，有多少种不同的排法？（5）如果只有4个数在原来的位置上，有多少种不同的排法？（6）如果至少有4个数在原来的位置上，有多少种不同的排法？（7）使得偶数在偶数的位置上，但恰有两个数不在原来的位置上，奇数在奇数的位置上，但恰有两个数不在原来位置上，有多少种不同的排法？（8）使得偶数在偶数的位置上，且至少有两个数不在原来的位置上；奇数在奇数的位置上，也至少有两个数不在原来的位置上，有多少种不同的排法？解析：（1）本题实质上是“装错信封问题”，49D =.（2）偶数在奇数位置上44A ，奇数在偶数位置上44A ，4444576A A ⋅=.（3）4481D D ⋅=.（4）正难则反，对8个数进行全排列88A ，减去没有数在原来的位置上8D ，88825487A D −=.（5）先从8个数中选择4个数在原来的位置上，剩余4个数不在原来的位置上，用分步乘法计数原理：484630C D ⋅=.（6）分类求解：45688483828771C D C D C D C ⋅+⋅+⋅+=.（7）224242()()36C D C D ⋅⋅⋅=.（8）22424424()()225C D D C D D ⋅+⋅⋅+=.上式中至少有2个数不在原来的位置上，包括恰有2个数不在原来的位置上和4个数都不在原来的位置上两种情况.【小结】“问题是数学的心脏.”思考问题，解决问题，才能促进数学素养的形成.。

“装错信封问题”的数学模型与求解某人写了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个不同元素的全排列的集合A i(i=1，2，…，n)为元素i在原位的排列的集合．A i∩A j(1≤i＜j≤n)为元素i与j在原位的排列的集合．…………A1∩A2∩…∩A n为n个元素的序排的集合．则它们的排列数(即各个集合中元素的个数)分别为|I|=n！|A i|=(n－1)！|A i∩A j|=(n－2)！…………|A1∩A2∩…∩A n|=(n－n)！=0！所以，根据容斥原理即得“装错信封问题”的数学模型的求解公式(即n个不同元素的错排数)为4 应用举例一个元素的错排数显然为0，二个不同元素的错排数为1，三个不同元素的错排数为2，均可由公式验证，由公式还可求得四个不同元素的错排数为五个不同元素的错排数为则本文开头的问题1)共有9种不同的分配方式，故选(B)．问题2)共有44种不同的戴法，下面再举几例说明公式的应用．例1 (1991年上海高考题)设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，则这样的投放方法的总数为[ ] A．20种B．30种C．60种D．120种解本题实质上是三个元素的错排问题，但由于题中未指明是哪三个元素进行的错排，故本题可分两步求解．第二步，对已选出的三个元素进行错排，有2种．例2某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务．问共有多少种不同的干部调配方案？解实质上本题即为8个不同元素的错排问题，一种干部调配方法对应于8个不同元素的一个错排．故由公式可求得不同的干部调配方案数为-- 参考答案：瑞士数学家欧拉按一般情况给出了一个递推公式：用Ａ、Ｂ、Ｃ……表示写着ｎ位友人名字的信封，ａ、ｂ、ｃ……表示ｎ份相应的写好的信纸。

全装错信问题即全错位排列问题及拓展——龙城老欧全装错信问题又称全错位排列问题，最早由瑞士数学家伯努利提出，最后由伯努利与他的学生欧拉讨论解决，这个问题就是——我们将编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信都和信封的编号不同，即1不能装进1，2不能装进2，3不能装进3……问有多少种装法？看到这个问题时，我们的第一反应就是退到简单处入手研究，如果只有一封信，2封信，3封信，4封信，……，然后从中再思考，之间是否有共性，是否有关联，共性用归纳，关联构成递推，或者其他。

〖解法〗容易知道：a[1]=0,a[2]=1，a[3]=2，a[4]=6;依我们设a[i]为i封信的全错位排列数据递归推理那么有a[i]=(a[i-1]+a[i-2])×(i-1)， (i>=3)。

为什么？为什么？为什么？大多数人看不明白。

不急，尽量先自己思考，不行的话，听我来解释：思考1：对于插入第i个元素，只可能有两种情况：第一种情况:插入第i个元素时，前i-1个已经错位排好，则选择其中任意一个与第i个互换一定满足要求,选择方法共i-1种，前i-1位错排f[i-1]种，记f[i-1]*(i-1),如下图：第二种情况:插入第i个元素时，前i-1个中恰有一个元素恰好在自己的位置上，即恰好只有一个元素不满足错位排列，其他i-2个错位排好，则将i与j交换，j在i-2位中的插入共i-1种，前i-2位错排a[i-2]种，记f[i-2]*(i-1)，如下图：以上两种情况求和可得: a[i]=(a[i-1]+a[i-2])×(i-1) (i>=3)我们还可以这样思考：思考2：有(i-1)个人已经都坐在在自己的板凳上了，现在第i个人张三带着自己的板凳来了，下面我们来对这i个人进行全错位排排坐，方法1：前面(i-1)个人中的某一个带着板凳出来与第i个人张三互换板凳坐（有（i-1）种方法），其它(i-2)个人进行全错位排列（有a[i-2]种方法），这样就整体上都是全错位；方法2：第i 个人张三走进去与将(i-1)个人中的某一个人换出来（i-1种方法），换出来的人（不妨称是李四）坐张三的板凳，换出来的李四的板凳看作张三的新板凳，这样又面临了(i-1)个元素进行全错位排列问题（a[i-2]种方法），这样就整体上也都是全错位了。

错位排列问题：⼗本不同的书放在书架上。

现重新摆放，使每本书都不在原来放的位置。

有⼏种摆法？这个问题推⼴⼀下，就是错排问题，是组合数学中的问题之⼀。

考虑⼀个有n个元素的排列，若⼀个排列中所有的元素都不在⾃⼰原来的位置上，那么这样的排列就称为原排列的⼀个错排。

n个元素的错排数记为D(n)。

研究⼀个排列错排个数的问题，叫做错排问题或称为更列问题。

错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题。

这个问题有许多具体的版本，如在写信时将n 封信装到n个不同的信封⾥，有多少种全部装错信封的情况？⼜⽐如四⼈各写⼀张贺年卡互相赠送，有多少种赠送⽅法？⾃⼰写的贺年卡不能送给⾃⼰，所以也是典型的错排问题。

递推公式当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的⽅法数⽤D(n)表⽰，那么D(n-1)就表⽰n-1个编号元素放在n-1个编号位置，各不对应的⽅法数，其它类推.第⼀步，把第n个元素放在⼀个位置，⽐如位置k，⼀共有n-1种⽅法；第⼆步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种⽅法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种⽅法；综上得到D(n) = (n-1) [D(n-2) + D(n-1)]特殊地，D(1) = 0, D(2) = 1.下⾯通过这个递推关系推导通项公式：为⽅便起见，设D(k) = k! N(k), k = 1, 2, …, n,则N(1) = 0, N(2) = 1/2.n ≥ 3时，n! N(n) = (n-1) (n-1)! N(n-1) + (n-1)! N(n-2)即 nN(n) = (n-1) N(n-1) + N(n-2)于是有N(n) - N(n-1) = - [N(n-1) - N(n-2)] / n = (-1/n) [-1/(n-1)] [-1/(n-2)]…(-1/3) [N(2) - N(1)] = (-1)^n / n!.因此N(n-1) - N(n-2) = (-1)^(n-1) / (n-1)!,N(2) - N(1) = (-1)^2 / 2!.相加，可得N(n) = (-1)^2/2! + … + (-1)^(n-1) / (n-1)! + (-1)^n/n!因此D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].此即错排公式。

装错信封问题容斥原理I ∑∑≤<≤=⋂+-=⋂⋂⋂ni i i i ni in A AA A A A A 21211121||||||||∑≤<<<≤⋂⋂⋂-++⋂⋂⋂-++ni i i n n i i i kk k A A A A A A2121121.||)1(||)1(II 12121211||||||nn i i i i i i nA A A A A A =≤<≤⋃⋃⋃=-⋂∑∑∑≤<<<≤--⋂⋂⋂-++⋂⋂⋂-++ni i i n n i i i k k kA A A A A A 212112111.||)1(||)1(装错信封问题“装错信封问题”是由当时最有名的数学家约翰·伯努利（Johann Bernoulli ，1667—1748）的儿子丹尼尔·伯努利（Danid Bernoulli ，1700—1782）提出来的，大意如下：一个人写了n 封信都装错了信封，问都装错信封的装法有多少种？其他叙述方式(1) “拿错帽子问题” (2) “分发贺卡问题” (3) “更列问题”设n 封为n a a ,,1 ，n 个信封为n A A ,,1 ，装对的情形为i a 装入i A ),,2,1(n i =. 我们把都装错的情形数记为n .(1) 若不考虑是否装对信封，则有!n A nn =种.(2) 若至少有1封信装对信封，即i a 装入i A ，而其他1-n 封信的装法有-1-1(-1)!n n A n =.由于i a 装入i A 有1n C 种，所以，至少有1封信装对信封的装法有1-1-1n n n C A 种.(3) 若至少有2封信装对信封，即i a 装入i A ，j a 装入j A ，而其他2-n 封信的装法有-2-2(-2)!n n A n =，所以，至少有2封信装对信封的装法有2-2-2n n n C A 种. (4) 至少有3封信装对信封的装法有3-3-3n n n C A 种.(5) 一般地，其中至少有k 封装对的装法有k n kn n k C A --种.于是，由容斥原理，封信都装错的情形种数为.12!(1)!(2)!(1)()!(1)1k k n nn n n n C n C n C n k =-⋅-+⋅-++-⋅-++-⋅另证.设n 封为n a a ,,1 ，n 个信封为n A A ,,1 ，装对的情形为i a 装入i A ),,2,1(n i =.我们把都装错的情形数记为n .首先研究1a 装入2A 时，信封装错的种数.分两种情况.(1)1a 装入2A ,2a 装入1A . 此时，其余2-n 封信都装错的种数为2-n .(2)1a 装入2A ,2a 没有装入1A . 此时，其余1-n 封信都装错的种数为1-n .这样，当1a 装入2A 时，信封装错的种数为1+2n n --.同样，当1a 装入3A ，当1a 装入4A ，……，当1a 装入n A 时，信封装错的种数也为1+2n n --.从而，信封装错的所有种数为)21)(1(-+--=n n n n .2)1(11-⋅-+---⋅=n n n n n n .于是，有递推公式]2)1(1)[1(1-⋅----=-⋅-n n n n n n . 取,,,4,3,2n n =可得332(1)(221)-⋅=--⋅]2)1(1)[1(1-⋅----=-⋅-n n n n n n相乘得)122()1(12⋅--=-⋅--n n n n . 容易求出 .01,12==于是 .)1(1n n n n -=-⋅-从而 .!)1()!1(1!n n n n n n-=---取,,,4,3,2n n =可得!2)1(!11!222-=-.!)1()!1(1!n n n n n n -=---相加得.!)1(!51!41!31!21!11!n n n n-++-+-=- 化为1111(1)![].2!3!4!5!!nn n n -=⋅-+-++定理1 n 封信都装错了信封的种数为].!)1(!51!41!31!21[!n n n n-++-+-⋅= 或 ∑=--=ni in n i A n 0)1(或 ∑=-⋅-=ni ini i n C n 0)!()1(.有且只有k )(n k <封信装对信封等价于k n -封信装错信封. 于是有定理2 有且只有k 封信装对的种数为.k n C kn -⋅有且只有k 封信装错的种数为.k C k n ⋅定理3 至少有k 封信装对的种数为)!.(k n C A C kn k n k n k n -⋅=⋅--例1 由93,2,1，，组成的形如⨯⨯⨯⨯⨯1234的九位数，其中，万位不是5，千位不是6，百位不是7，十位不是8，各位不是9，这样的九位数有多少个？例2 证明!.00n n C C nn n =⋅++⋅例3 某一天的课表要排6门课程，每门课上且上一节，一天排6节课，体育课不在第一节，数学不在最后一节，问有多少种排法？例4 有一个n 位数的集合，且这n 位数是由k ,,2,1 组成的，若每个数字至少出现一次，那么这个集合元素共有多少个？例5 P 为集合},,2,1{n S n =的一个排列，一个元素n j S ∈，如果j j P =)(就称为P 的一个不动点. 令n f 为n S 的无不动点的排列的个数，n g 为n S 恰有一个不动点的排列的个数，证明：.1||=-n n g f例6 把写有数码6,5,4,3,2,1的6张卡片插入编号为6,5,4,3,2,1的6只袋子，每只袋子只插入1张卡片.(1) 求每一张卡片的号码与所在袋子的号码都不同的插法种数. (2) 求恰有3张卡片的号码与所在袋子的号码相同的插法种数.1. 设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，则这样的投放方法的总数为第一步，先选出三个被错排的元素，有35C 种. 第二步，对已选出的三个元素进行错排，有2种.所以，根据乘法原理可得投放方法总数为35C ·2=20种.2. 某省决定对所辖8个城市的常政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？解实质上本题即为8个不同元素的错排问题，一种干部调配方法对应于8个不同元素的一个错排.11111111-+-+-+-+=（种）8!(1)148331!2!3!4!5!6!7!8!3.同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四张贺年卡的不同分配方式有4. 有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家，回家后，他们的妻子都发现他们戴了别人的帽子.问5个客人都不戴自己帽子的戴法有多少种？5. 由5,4,3,2,1这五个数字组成没有重复数字的五位数，按从小到大的顺序排列，问32154是这个数列的第几项？6. 以长方体的8个顶点中的3点位顶点的三角形,锐角三角形的个数共有几个?7. 一副扑克牌去掉两张王后还有52张，将牌发给4个人，每人13张，则某人获得的13张牌中花色齐全的全部情况数为多少？第一、先从13张牌中选出一张，再给他选一个花色，则有13×4种选法第二，从剩余的12张牌中再选一张，给他选一个与第一张牌颜色不同的花色，则有12×3种选法第三、再从剩余的11张牌中选出一张，给他与前两张不同的花色，则有11×2种选法第四、再从剩余的10张牌中选出一张，给他最后的一种花色，则有10×1种选法那么一共有：13×4×12×3×11×2×10×1=411840种组合情况．8. 在年龄彼此不同的30人中选出两组人,第一组12人,第二组15人,若第一组中年龄最大的人比第二组中年龄最小的还要小,问有几种选择方式？40609. 从1-300中,任取3个不同的数,使它们的和为3的倍数,有多少种取法?10.从6名短跑运动员中选出4人参加4×100m接力赛,如果甲不跑第一棒，乙不跑最后一棒,那么不同的参赛方案有几种？11. 如果1个凸十边形没有三条对角线交于同一点,问在十边形内部由它们的交点可将对角线分割成多少条线段?凸n边形的任意3条对角线不相交于形内的一点,问:(1)这些对角线将凸边形分成了多少个区域?(2)这些对角线被交点分成了多少条线段?12. 从数字7,5,3,1,0中取出不同的三个作系数，可组成多少个不同的一元二次方程？其中有实数根的有几个？一共有多少个实数根？。

一.页码问题对多少页出现多少1或2的公式如果是X千里找几，公式是 1000+X00*3 如果是X百里找几，就是100+X0*2，X有多少个0 就*多少。

依次类推!请注意，要找的数一定要小于X ，如果大于X 就不要加1000或者100一类的了，比如，7000页中有多少3 就是 1000+700*3=3100(个)20000页中有多少6就是 2000*4=8000 (个)友情提示，如3000页中有多少3，就是300*3+1=901，请不要把3000的3忘了二，握手问题N个人彼此握手，则总握手数S=(n-1){a1+a(n-1)}/2=(n-1){1+1+(n-2)}/2=『n^2-n』/2 =N×(N-1)/2例题：某个班的同学体育课上玩游戏，大家围成一个圈，每个人都不能跟相邻的2个人握手，整个游戏一共握手152次，请问这个班的同学有( )人A、16B、17C、18D、19【解析】此题看上去是一个排列组合题，但是却是使用的多边形对角线的原理在解决此题。

按照排列组合假设总数为X人则Cx取3=152 但是在计算X时却是相当的麻烦。

我们仔细来分析该题目。

以某个人为研究对象。

则这个人需要握x-3次手。

每个人都是这样。

则总共握了x×(x-3)次手。

但是没2个人之间的握手都重复计算了1次。

则实际的握手次数是x×(x-3)÷2=152 计算的x=19人三，钟表重合公式钟表几分重合，公式为： x/5=(x+a)/60 a时钟前面的格数四，时钟成角度的问题设X时时，夹角为30X ， Y分时，分针追时针5.5，设夹角为A.(请大家掌握)钟面分12大格60小格每一大格为360除以12等于30度，每过一分钟分针走6度，时针走0.5度，能追5.5度。

1.【30X-5.5Y】或是360-【30X-5.5Y】【】表示绝对值的意义(求角度公式)变式与应用2.【30X-5.5Y】=A或360-【30X-5.5Y】=A (已知角度或时针或分针求其中一个角)五，往返平均速度公式及其应用(引用)某人以速度a从A地到达B地后，立即以速度b返回A地，那么他往返的平均速度v=2ab/(a+b )。

装错信封问题容斥原理I ∑∑≤<≤=⋂+-=⋂⋂⋂ni i i i ni in A AA A A A A 21211121||||||||∑≤<<<≤⋂⋂⋂-++⋂⋂⋂-++ni i i n n i i i kk k A A A A A A2121121.||)1(||)1(II 12121211||||||nn i i i i i i nA A A A A A =≤<≤⋃⋃⋃=-⋂∑∑∑≤<<<≤--⋂⋂⋂-++⋂⋂⋂-++ni i i n n i i i k k kA A A A A A 212112111.||)1(||)1(装错信封问题“装错信封问题”是由当时最有名的数学家约翰·伯努利（Johann Bernoulli ，1667—1748）的儿子丹尼尔·伯努利（Danid Bernoulli ，1700—1782）提出来的，大意如下：一个人写了n 封信都装错了信封，问都装错信封的装法有多少种？其他叙述方式(1) “拿错帽子问题” (2) “分发贺卡问题” (3) “更列问题”设n 封为n a a ,,1 ，n 个信封为n A A ,,1 ，装对的情形为i a 装入i A ),,2,1(n i =. 我们把都装错的情形数记为n .(1) 若不考虑是否装对信封，则有!n A nn =种.(2) 若至少有1封信装对信封，即i a 装入i A ，而其他1-n 封信的装法有-1-1(-1)!n n A n =.由于i a 装入i A 有1n C 种，所以，至少有1封信装对信封的装法有1-1-1n n n C A 种.(3) 若至少有2封信装对信封，即i a 装入i A ，j a 装入j A ，而其他2-n 封信的装法有-2-2(-2)!n n A n =，所以，至少有2封信装对信封的装法有2-2-2n n n C A 种. (4) 至少有3封信装对信封的装法有3-3-3n n n C A 种.(5) 一般地，其中至少有k 封装对的装法有k n kn n k C A --种.于是，由容斥原理，封信都装错的情形种数为.12!(1)!(2)!(1)()!(1)1k k n nn n n n C n C n C n k =-⋅-+⋅-++-⋅-++-⋅另证.设n 封为n a a ,,1 ，n 个信封为n A A ,,1 ，装对的情形为i a 装入i A ),,2,1(n i =.我们把都装错的情形数记为n .首先研究1a 装入2A 时，信封装错的种数.分两种情况.(1)1a 装入2A ,2a 装入1A . 此时，其余2-n 封信都装错的种数为2-n .(2)1a 装入2A ,2a 没有装入1A . 此时，其余1-n 封信都装错的种数为1-n .这样，当1a 装入2A 时，信封装错的种数为1+2n n --.同样，当1a 装入3A ，当1a 装入4A ，……，当1a 装入n A 时，信封装错的种数也为1+2n n --.从而，信封装错的所有种数为)21)(1(-+--=n n n n .2)1(11-⋅-+---⋅=n n n n n n .于是，有递推公式]2)1(1)[1(1-⋅----=-⋅-n n n n n n . 取,,,4,3,2n n =可得332(1)(221)-⋅=--⋅]2)1(1)[1(1-⋅----=-⋅-n n n n n n相乘得)122()1(12⋅--=-⋅--n n n n . 容易求出 .01,12==于是 .)1(1n n n n -=-⋅-从而 .!)1()!1(1!n n n n n n-=---取,,,4,3,2n n =可得!2)1(!11!222-=-.!)1()!1(1!n n n n n n -=---相加得.!)1(!51!41!31!21!11!n n n n-++-+-=- 化为1111(1)![].2!3!4!5!!nn n n -=⋅-+-++定理1 n 封信都装错了信封的种数为].!)1(!51!41!31!21[!n n n n-++-+-⋅= 或 ∑=--=ni in n i A n 0)1(或 ∑=-⋅-=ni ini i n C n 0)!()1(.有且只有k )(n k <封信装对信封等价于k n -封信装错信封. 于是有定理2 有且只有k 封信装对的种数为.k n C kn -⋅有且只有k 封信装错的种数为.k C k n ⋅定理3 至少有k 封信装对的种数为)!.(k n C A C kn k n k n k n -⋅=⋅--例1 由93,2,1，，组成的形如⨯⨯⨯⨯⨯1234的九位数，其中，万位不是5，千位不是6，百位不是7，十位不是8，各位不是9，这样的九位数有多少个？例2 证明!.00n n C C nn n =⋅++⋅例3 某一天的课表要排6门课程，每门课上且上一节，一天排6节课，体育课不在第一节，数学不在最后一节，问有多少种排法？例4 有一个n 位数的集合，且这n 位数是由k ,,2,1 组成的，若每个数字至少出现一次，那么这个集合元素共有多少个？例5 P 为集合},,2,1{n S n =的一个排列，一个元素n j S ∈，如果j j P =)(就称为P 的一个不动点. 令n f 为n S 的无不动点的排列的个数，n g 为n S 恰有一个不动点的排列的个数，证明：.1||=-n n g f例6 把写有数码6,5,4,3,2,1的6张卡片插入编号为6,5,4,3,2,1的6只袋子，每只袋子只插入1张卡片.(1) 求每一张卡片的号码与所在袋子的号码都不同的插法种数. (2) 求恰有3张卡片的号码与所在袋子的号码相同的插法种数.1. 设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，则这样的投放方法的总数为第一步，先选出三个被错排的元素，有35C 种. 第二步，对已选出的三个元素进行错排，有2种.所以，根据乘法原理可得投放方法总数为35C ·2=20种.2. 某省决定对所辖8个城市的常政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？解实质上本题即为8个不同元素的错排问题，一种干部调配方法对应于8个不同元素的一个错排.11111111-+-+-+-+=（种）8!(1)148331!2!3!4!5!6!7!8!3.同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四张贺年卡的不同分配方式有4. 有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家，回家后，他们的妻子都发现他们戴了别人的帽子.问5个客人都不戴自己帽子的戴法有多少种？5. 由5,4,3,2,1这五个数字组成没有重复数字的五位数，按从小到大的顺序排列，问32154是这个数列的第几项？6. 以长方体的8个顶点中的3点位顶点的三角形,锐角三角形的个数共有几个?7. 一副扑克牌去掉两张王后还有52张，将牌发给4个人，每人13张，则某人获得的13张牌中花色齐全的全部情况数为多少？第一、先从13张牌中选出一张，再给他选一个花色，则有13×4种选法第二，从剩余的12张牌中再选一张，给他选一个与第一张牌颜色不同的花色，则有12×3种选法第三、再从剩余的11张牌中选出一张，给他与前两张不同的花色，则有11×2种选法第四、再从剩余的10张牌中选出一张，给他最后的一种花色，则有10×1种选法那么一共有：13×4×12×3×11×2×10×1=411840种组合情况．8. 在年龄彼此不同的30人中选出两组人,第一组12人,第二组15人,若第一组中年龄最大的人比第二组中年龄最小的还要小,问有几种选择方式？40609. 从1-300中,任取3个不同的数,使它们的和为3的倍数,有多少种取法?10.从6名短跑运动员中选出4人参加4×100m接力赛,如果甲不跑第一棒，乙不跑最后一棒,那么不同的参赛方案有几种？11. 如果1个凸十边形没有三条对角线交于同一点,问在十边形内部由它们的交点可将对角线分割成多少条线段?凸n边形的任意3条对角线不相交于形内的一点,问:(1)这些对角线将凸边形分成了多少个区域?(2)这些对角线被交点分成了多少条线段?12. 从数字7,5,3,1,0中取出不同的三个作系数，可组成多少个不同的一元二次方程？其中有实数根的有几个？一共有多少个实数根？。

算法学习——回溯之伯努利装错信封问题算法描述某⼈给6个朋友每个⼈都写了⼀封信，同时写了这6个朋友地址的信封，有多少种投放信笺的⽅法，使得每封信与信封上的收信⼈都不相符？算法思路6封信可能出现的结果：所有的信都是在对应的信封中，也就是所有的信都放对了信封，这种情况只有⼀种部分信放错了信封全部信都放错了信封题⽬要求的就是求最后⼀种情况，也就是全部新都放错了信封定义⼀个数组a[i]，a[1] = 1 表⽰第⼀封信放在了第⼀个信封中限制条件a[i]!=i 即限制信放在正确的信封中a[i]!=a[j] 即限制信不能放在同⼀个信封回溯条件a[i]=6 即已经遍历到了最后⼀封信算法实现System.out.println("输⼊n：");Scanner scaner = new Scanner(System.in);int n = scaner.nextInt();scaner.close();int s = 0;//解的个数统计int[] a = new int[n+1];a[1]=2;int i=1;while(true){boolean flag = true;if(a[i]!=i){for(int j=1;j<i;j++){if(a[j]==a[i]){flag = false;break;}}}else{flag = false;}if(flag&&i==n){s++;for(int j=1;j<=n;j++){System.out.print(a[j]);}System.out.print(" ");//出现⼗个解换⾏if(s%10==0){System.out.println("");}}if(flag&&i<n){i++;a[i]=1;continue;}while(a[i]==n&&i>0){i--;//回溯，a[i]到末尾，则回溯 }if(i>0){a[i]++;//向后移}else{break;}}System.out.println("\n"+"s="+s);结果。

行测答题技巧：插板法解决排列组合问题在公务员考试中，数量关系模块一直是考生复习的重难点所在，从历年考试来看，排列组合问题是这一模块的难度较大的题型之一。

而从题量来看，排列组合问题也是出现数量较多、出现频率较高的，可见这一类题型在公务员考试中的重要程度。

而分配插板法是排列组合问题中较为重要的一种方法，这种方法用于解决元素分组问题。

灵活运用插板法能处理一些较复杂的排列组合问题，但使用时有2点要求：①元素相同;②每组中至少分一个元素。

一、直接使用插板型例1、把9个苹果分给5个人，每人至少一个苹果，那么不同的分法一共有多少种?( )(2010年河南政法干警考试A卷第41题)A.30B.40C.50D.60答案：D。

该问题用分类计数法较复杂，但可以将9个苹果排成一行,9个苹果中间就出现8个空挡，再用,4个挡板把9个苹果分成有序的5份，每个人就依次按序分到对应的n个苹果(可能是1个﹑2个﹑3个﹑4个、5个)。

即在8个空挡中插入4个挡板，由4个挡板把球分成5份,共有C84种方法。

在这道题目中，直接符合了使用插板法的2点要求：(1)每个苹果都相同;(2)每个人都至少拿到1个苹果。

二、一组多元素型例2、某单位订阅了30份学习材料发放给3个部门，每个部门至少发放9份材料。

问一共有多少种不同的发放方法?( )(2010年国家公务员考试行测第46题)A.12B.10C.9D.7答案：B。

先拿出24份材料，每个部分发8份，这时变成"6份材料发给3个部门，每个部门至少发1份"，再利用插板法，在5个空中插上2个挡板：C52=10(种)发放办法。

在这道题中，显然不符合使用插板法的第二点要求："每组中至少分得一个元素"。

题目要求"每个部分至少发放9份材料"，因此可以把题目稍作变形，先给每个部分发8份材料，题目就变成了"每个部分至少发1份材料"，符合使用插板法的2个要求，可以使用插板法。

发表于浙江师大《中学教研∙数学》2011（07）从竞赛到高考班的装错信笺题及变式题探究●甘大旺（北仑明港中学浙江宁波315806）瑞士数学家尼•伯努利(Danil Bemoulli ，1700~1782)提出了装错信笺问题——某人写了n （∈N +）封不同的信，并在n 个信封上写下对应的地址，问把所有信笺全部装错的方法共有多少种？后来，瑞士数学家欧拉(Euler ，1707~1783)认为此题是“组合理论的一个妙题”，并运用递推数列{}n x 独立地解决了这道妙题，求出的方法种数用阶乘表示为11111(1)(1)!0!1!2!3!(1)!!n n n x n n n -⎡⎤--=⋅-+-+++⎢⎥-⎣⎦ ．(#)欧拉解法的关键是找出递推数列的递推式))(1(12n n n x x n x +-=++、难点是后续的求出通项．下面另辟蹊径，运用容斥原理来验证(#)式．证明：当正整数2n ≥时，将这n 封信笺任意装入这n 个信封，不管装对装错，笼统有!n 种方法．其中，至少有1封信笺恰好正确装入信封的任意装法有)!1(1-⋅n n C 种，至少有2封信笺恰好正确装入信封的任意装法有)!2(2-⋅n nC 种，至少有3封信笺恰好正确装入信封的任意装法共有)!3(3-⋅n nC 种，┅，至少有1-n 封信笺恰好正确装入信封的装法共有!11⋅-n n C 种，所有n 封信笺都正确装入信封的装法共有n nC 种．根据容斥原理知，符合题意的投放信笺方法共有123!(1)!(2)!(3)!n x n C n C n C n nn n=-⋅-+⋅--⋅-n n C n n n C n )1(!111)1(-+⋅---++!!)1()!1(!)1(!3!!2!!1!!1n n n n n n n n nn -+--++-+-=- ⎥⎥⎦⎤⎢⎢⎣⎡-+--++-+-⋅=-!)1()!1()1(!31!21!11!01!1n n n n n 种．当1n =时，11100!1!x ==-适合上式.。

考试难点攻克之错位重排随着我们备考的逐渐深入，很多考生对于数量关系这部分的内容还是感觉难以下手，那么面对这种情况，就需要我们的考生对于我们数量中一些常考的有明显题型特征且解题思路清晰明了的一些题型进行重点攻克。

比如我们今天要给大家讲到的排列组合问题中常见的错位重拍问题。

一、题型特征错位重排问题是一种比较复杂的数学模型，其实就是著名的伯努利一欧拉的装错信封问题，我们可以形象地叙述如下:“某人写了n封信,并在n个信封上写下了对应的地址和收信人姓名,把所有的信笺装错信封的情况共有多少种。

”为了便于理解题目，我们不妨先假设n=3，并且将三个信封分别用大写字母ABC来代替，将三封信用小写字面abc来代替，题目的要求其实就是将信封和信件两两配对，但是A-a，B-b，C-c不能配对，这样的题目就叫做错位重排问题。

二、解题要点错位重排作为排列组合的一种模型，原理很复杂，但是应用上面很简单。

解决此类问题最直接的就是记住公式：一个元素错位重排的时候情况数为0（因为只有一个，不可能排错），两个元素错位重排情况为1，三个为2，四个为9，五个为44…从这里不难看出从第四项开始为前面两数和的倍数，也就是说，若将错位重排数记为D n，则：D n=（n-1）（D n-2+D n-1），（D1=0，D2=1，D3=2）三、重点题型掌握了错位重排的公式，我们一起来看几道题目看看在实战中错位重排问题如何解决。

例1. 四位厨师聚餐时各做了一道拿手菜。

现在要求每人去品尝一道菜，但不能尝自己做的那道菜。

问共有几种不同的尝法?A．6种 B.9种 C.12种 D.15种【答案】B。

解析：4位厨师的错位重排数为D4=9，即有9种不同的尝法。

除了此类直接应用公式的题型之外，错位重排问题还包括一类不完全错位重排问题，比如下面这道例题：例2.五个装药用的瓶子都贴有标签,其中恰好贴错了三个,那么贴错的可能情况有多少种?A.9种B.12种C.18种D.20种【答案】D。

公务员⾏测技巧：伟⼈出错后的反思,错位重排 店铺为您带来《公务员⾏测技巧：伟⼈出错后的反思-错位重排》，供您参考!更多相关资讯请继续关注本⽹站的更新!希望给您带来帮助!祝您顺利通过考试! 公务员⾏测技巧：伟⼈出错后的反思-错位重排 错位重排问题是⼀种⽐较难理解的复杂数学模型，是伯努利和欧拉在错装信封时发现的，因此⼜称伯努利-欧拉装错信封问题。

这类问题经常出现在⾏测试卷，但⽐较难解决，现在在此进⾏分析。

常见考法： 例1、四位厨师聚餐时各做了⼀道拿⼿菜。

现在要求每⼈去品尝⼀道菜，但不能尝⾃⼰做的那道菜。

问共有⼏种不同的尝法? A.6种 B.9种 C.12种 D.15种 【答案】B。

解析：根据每个⼈不能尝⾃⼰的那道菜，我们可以知道这个题⽬是考察我们错位重排问题，⽽且是4个元素的错位重排问题，所以我们直接应⽤结论，选择9种，B选项。

例2、某中学⾼中三年级有五个班，在即将进⾏的考试中，拟安排5个班主任考试监考数学，每班1⼈，要求每个班主任⽼师都不能监考⾃⼰的班级，则不同的监考安排⽅案共有多少种? A.6种 B.9种 C.35种 D.44种 【答案】D。

解析：每个⽼师对应⼀个班级，但⽼师不能监考⾃⼰所对应的那个班级，这个题⽬符合错位重排的题型特征，⽽且是5个元素的错位重排问题，所以我们直接应⽤结论，选择44种，所以选D。

例3、⼩明和5位同学打篮球⽐赛，休息期间将⾃⼰带的6瓶相同的矿泉⽔分给⼤家，每位同学都没有喝完，并随机将6瓶⽔放在了⼀排后继续⽐赛，等待结束⽐赛再次去拿⽔瓶喝⽔时已经辨别不清哪个是⾃⼰的。

如果他们6⼈随机拿⼀瓶，恰好有4位同学拿的不是⾃⼰之前喝剩下的有⼏种情况? A.120 B.125 C.133 D.135 【答案】D。

解析：排列组合与错位重排相结合，6⼈中选择4⼈拿错⽔瓶有=15种情况，4⼈全拿错⽔瓶有9种(错位重排)，所以⼀共有15×9=135种情况。

前两个题⽬相对来说⽐较简单，直接通过记住特殊数据就可以把题⽬作对，最后⼀个题⽬是讲错位重排的知识点和普通的排列组合进⾏了结合，难度稍有提⾼。

如何快速解决2019国家公务员考试行测错位重排问题在中，有一种特殊题型是错位重排问题，在复习过程中很多人往往没有能够具体学习这个知识点，导致正确率较低。

错位重排问题也叫装错信封问题，这是源自于伯努利和欧拉在相互写信过程中所发现的。

错装信封问题其实是比较容易做对的，因为它的结论比较简单，所以我们应该重点掌握错位重排的应用环境以及它的结论方法。

所以，接下来中公教育专家通过例题来给大家说明如何快速解决错位重排问题。

错位重排问题可以简单的理解为，把n个元素进行重新排列，使得每个元素都不在自己原来对应的位置上。

我们通过一个例题来看一下。

比如：例1、现在有三个信封，我们分别用A、B和C表示，分别装有编号为a、b和c的信纸，现在我们把所有信纸重新装进信封，那么所有信纸都没有装进信封的情况有几种?三封信的情况较为简单。

全部装错的情况为：A B C(1)b c a(2)c a b总共两种情况。

对于类似于上个题目描述的情况，所有元素都不在对应位置上的题目，我们可以判断出此题为错位重排问题。

那么我们来分析一下，错位重排问题方法数的规律。

其实元素较少的情况下，我们可以通过穷举法来求出结果。

比如，当只有一封信(一个信封和一个信纸)的情况下，是不会装错的，也就是说装错的方法数位0;当有2封信的情况下，装错的情况有1种。

如：A Bb a当有3封信的时候，如例1所示，有2种结果。

当有4封信的时候，有9中方法。

我们用n表示有多少个元素，用Dn表示n个元素错位重排的方法数，用一个表格写出结果：得到其他的情况，但是在考试中上述表格中的数据是常考的，需要我们记住。

接下来我们通过两道题目来看一下，错位重排到底如何去应用。

2016年江西公务员考试难点攻克之错位重排问题错位重排问题是江西务员考试行测试卷中比较难理解的复杂数学模型，是伯努利和欧拉在错装信封时发现的，因此又称为伯努利-欧拉装错信封问题，是指把n个元素的位置重新排列，使每个元素都不在原来位置上的排列问题。

其原题的简单表述如下：编号是1、2、3的3封信，装入编号为1、2、3的3个信封，要求每封信和信封的编号不同，问有多少种装法?由于信封数目比较少，我们可以写出具体装法，1-2,2-3,3-1或者1-3,2-1,3-2，共两种。

但随着元素n的数目增多，分析过程也随之变得更加繁琐。

因此，对于这类问题有个固定的递推公式，即n封信的错位重排数为Dn，则Dn=(n-1)(Dn-2+Dn-1)。

根据这个公式，我们还可以提炼出一个性质：n个数的错位重排数Dn是n-a 的倍数。

例 1.四位厨师聚餐时各做了一道拿手菜。

现在要求每人去品尝一道菜，但不能尝自己做的那道菜。

问共有几种不同的尝法?A.6种B.9种C.12种D.15种【中公解析】4位厨师的错位重排数D4=9，即有9种不同的尝法。

验证：设四位厨师为甲、乙、丙、丁，他们的菜对应为①②③④。

甲可以选②③④三盘菜，假定选②，甲、乙、丙、丁对应的情况数有②①④③、②③④①、②④①③三种情况。

甲人选一盘有3种情况，你那么总共有3X3=9种情况。

例 2.五个瓶子都贴有标签,其中恰好贴错了三个,贴错的可能情况有多少种?A.9种B.12种C.18种D.20种【中公解析】五个瓶子中恰好有三个瓶子的标签贴错了，我们首先得确定是哪三个错了，即C(5，3)=10种，三个贴错了相当于是3个元素的错位重排，有2种情况，再利用分布相乘10×2=20种。

例3.小明要给自己的6位好朋友分别写一封信，在装信的时候一不小心只有2个信封上写对了地址，问写错的可能情况有多少种?A.90种B.115种C.125种D.135【中公解析】6封信只有2封写对了地址，说明有4封写错了，先选出哪4封写错了，即C(6，4)=15种，4封写错了相当于是4个元素的错位重排，有9种情况，再利用分布相乘15×9=135种为了便于考生们以后在做题过程中快速得到答案，须记住Dn的前5项结果。

装错信封问题一、问题的提出1、小东给六个不同学校的六位小朋友分别写一封信，这些信都装错了信封的情况共有多少种？A．35种 B．44种 C．125种 D．265种2、有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家．回家后，他们的妻子都发现他们戴了别人的帽子．问5个客人都不戴自己帽子的戴法有多少种？上述两个问题，实质上是完全一样的．是被著名数学家欧拉(LeonhardEuler，1707 －1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例．“装错信封问题”是由当时最有名的数学家约翰·伯努利(JohannBernoulli，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli，1700－1782)提出来的，大意如下：一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？二、问题求解“装错信封问题”其实就是n个不同元素的一类特殊排列问题，下面我们给出这类问题的求解公式．为方便，我们先把n个不同的元素及相应的位置都编上序号1，2，…，n，并且约定：在n个不同元素的排列中若编号为i(i=1，2，…，n)的元素排在第i个位置，则称元素i在原位；否则称元素i不在原位．若所有的元素都不在原位，则称这种排列为n个不同元素的一个错排(若每个元素都在原位则称为序排)．按照上面约定，“装错信封问题”即为n个不同元素的错排问题，也就是求在n个不同元素的全排列中，有多少种不同的错排？设I表示n个不同元素的全排列的集合Ai(i=1，2，…，n)为元素i在原位的排列的集合．A i ∩Aj(1≤i＜j≤n)为元素i与j在原位的排列的集合．i j …………()12121k i i i k A A A i i i ≤<<≤为n 个元素的序排的集合．则它们的排列数(即各个集合中元素的个数)分别为|I|=n ！| A i |=(n －1)！i| A i ∩A j |=(n －2)！………… 12k i i i A A A =(n －k)！…………()12!0!n A A A n n =-=、因为集合A 1有1n C 种，A i ∩A j 有2n C 种，…，12k i i i A A A 有k n C 种，12n A A A 有n n C 种。