错排信封问题

回专题模式回学习阶段模式

【题目名称、来源】

错排信封问题《组合数学》经典题目

【问题描述】

伯努利有n封信要寄，现在有n个信封装这n封信，问任何一封信都不装到正确的信封里的方案有多少种。

【所属专题】

组合数学算法

【适合学习阶段】

第二阶段

【解题思路】

问题分析：

方法一、找递推式

以1、2、3、4四个数为例找出错排规律，

1 2 的错排是唯一的2 1

1 2 3的错排有3 1 2 和2 1 3，这两个可以看成是1 2错排，3分别于1和2换位所得，如下图所示

1 2 3 4的错排有

4 3 2 1，4 1 2 3，4 3 1 2，

3 4 1 2，3 4 2 1，2 4 1 3，

2 1 4 3，

3 1

4 2，2 3 4 1

第一列是4分别与1，2，3互换位置，其余两个元素错排，由此产生的。

第二列是4与1 2 3 的一个错排3 1 2的每一个数互换得到的

第三列是4与1 2 3的另一个错排2 3 1中的每一个数换位所得

从上面的分析结果可知，产生n个数的错排方法是：

设n个数1 2 3 …n的错排数目为D(n)，任取其中一个数i，数i分别与其他的n-1个数之一互换，其余n-2个数错排，共得(n-1)*D(n-2)个错排，另一部分为数i以外的n-1个数进行错排，然后i与其中任意一个数互换得(n-1)*D(n-1)个错排。

综合以上分析的递推关系：

D(n)=(n-1)(D(n-1)+D(n-2)) D(1)=0 D(2)=1 D(3)=2 方法二、容斥原理

存储结构：

【测试数据】

【源程序】

排列组合问题经典题型解析含答案

排列组合问题经典题型解析含答案

排列组合问题经典题型与通用方法 1.相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一个组，当作一个大元素参与排列. 例1.,,,, A B C D E五人并排站成一排，如果,A B必须相邻且B在A 的右边，则不同的排法有（） A、60种 B、48种 C、36种 D、24种 2.相离问题插空排:元素相离（即不相邻）问题，可先把无位置要求的几个元素全排列，再把规定的相离的几个元素插入上述几个元素的空位和两端. 例2.七人并排站成一行，如果甲乙两个必须不相邻，那么不同的排法种数是（） A、1440种 B、3600种 C、4820种 D、4800种 3.定序问题缩倍法:在排列问题中限制某几个元素必须保持一定的顺序，可用缩小倍数的方法. 例3.A,B,C,D,E五人并排站成一排，如果B必须站在A的右边（,A B可以不相邻）那么不同的排法有（）A、24种 B、60种 C、90种D、120种

4.标号排位问题分步法:把元素排到指定位置上，可先把某个元素按规定排入，第二步再排另一个元素，如此继续下去，依次即可完成. 例4.将数字1，2，3，4填入标号为1，2，3，4的四个方格里，每格填一个数，则每个方格的标号与所填数字均不相同的填法有（ ） A 、6种 B 、9种 C 、11种 D 、23种 5.有序分配问题逐分法:有序分配问题指把元素分成若干组，可用逐步下量分组法. 例5.（1）有甲乙丙三项任务，甲需2人承担，乙丙各需一人承担，从10人中选出4人承担这三项任务，不同的选法种数是（ ） A 、1260种 B 、2025种 C 、2520种 D 、5040种 （2）12名同学分别到三个不同的路口进行流量的调查，若每个路口4人，则不同的分配方案有（ ） A 、44412 8 4 C C C 种 B 、44412 8 4 3C C C 种 C 、44312 8 3 C C A 种 D 、 4441284 33 C C C A 种

公务员考试行测：记住错位重排结论的重要性

在公务员考试中，在数学运算部分有每年必考题型——排列组合。一般情况下不管省考还是国考每年都会出现一道题目，并从近几年公务员考试的命题趋势来看，这一题型的难度也有逐年上升的趋势，考察形式也比较多样化。环形排列、隔板模型、错位重排等都是排列组合中的经典模型，对于这些题型如果大家没有系统的学习过，看到一个题后就去硬着头皮去做，这样是很浪费时间的，一般也易做错，但如果大家了解这些题型所涉及的原理及其结论，只要在考试时大家能准确的区分题型，那对于这一类题目就是简单的计算问题了。接下来中公教育老师就给大家介绍一下错位重排的结论。 错位重排问题是伯努利和欧拉在错装信封时发现的，因此又称伯努利-欧拉装错信封问题。表述为：编号是1、2、…、n的n封信， 装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法? 解析：假设用Dn来表示n封信进行错位重排的方法数，我们不 难得出以下结论： (1) n=1, D1=0;1封信是不能进行错位重排的; (2) n=2，D2=1;2封信的时候只能相互对调只有1种方法; (3) n=3，D3=2×(D1+D2)=2×(0+1)=2; (4) n=4，D4=3×(D2+D3)=3×(1+2)=9; (5) n=5，D5=4×(D3+D4)=4×(2+9)=44; (6) n=6，D6=5×(D4+D5)=5×(9+44)=265;

(7) n=n，Dn=(n-1)×(Dn-2+Dn-1); 对于第一封信只要不装在1号信封即可，因此有n-1种装法，剩下的还有n-1封信没有装信封，其有两种情况。第一种情况：假设第一封信装进2号信封，第二封信装进1号信封，则此时剩下n-2封信件，这些信件再进行错位重排有Dn-2种方法;第二种情况：假设第一封信装进2号信封，这时候将其拿出，那最后剩余n-1封信，满足编号2不放1号信封、3号不放2号信封，则变成n-1封信的错位重排，因此有Dn-1种装法。我们都知道排列组合是建立在分类分步思想之下的，因此n封信件的错位重排就是Dn=(n-1)×(Dn-2+Dn-1)。在考试中一般n 6,因此大家在做题时只要能区分题型，记住n=1,2,3的错位重排数即可，按照我们的结论再难的题也能够通过简单的计算得出。 下面主要通过几个练习题来巩固一下错位重排的结论。 例1：四位厨师聚餐时各做了一道拿手菜，现在要求每个人去品尝一道菜，但不能尝自己做的那道菜，问共有几种不同的尝法? A.6 B.9 C.12 D.15 【答案】B。解析：此题为4个元素的错位重排有9种方式，故选B选项。 例2：编号为1至6的6个小球放入编号为1至6个盒子里，每个盒子放一

装错信封问题(1)

装错信封问题 容斥原理 I ∑∑≤<≤=?+- =???n i i i i n i i n A A A A A A A 2121 11 21|||||||| ∑≤<<<≤???-++???-++n i i i n n i i i k k k A A A A A A 2121 121.||)1(||)1( II 1212121 1||||||n n i i i i i i n A A A A A A =≤<≤?? ?=- ?∑∑ ∑≤<<<≤--???-++???-++n i i i n n i i i k k k A A A A A A 2121 12111 .||)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 n n =种. (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 种.

装错信封问题

装错信封问题 华图教育邹维丽 1．问题的提出 1)小明给住在五个国家的五位小朋友分别写一封信，这些信都装错了信封的情况共有多少种？ A．32种 B．44种 C．64种 D．120种 2)有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家．回家后，他们的妻子都发现他们戴了别人的帽子．问5个客人都不戴自己帽子的戴法有多少种？ 上述两个问题，实质上是完全一样的．是被著名数学家欧拉(LeonhardEuler，1707－1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例．“装错信封问题”是由当时最有名的数学家约翰·伯努利(JohannBernoulli，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个不同元素的全排列中，有多少种不同的错排？ 设I表示n个不同元素的全排列的集合 A i (i=1，2，…，n)为元素i在原位的排列的集合． A i∩A j (1≤i＜j≤n)为元素i与j在原位的排列的集合．i j ……

排列组合问题经典题型(含解析)

排列组合问题经典题型与通用方法 1.相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一个组，当作一个大元素参与排列. 例1.,,,, A B C D E五人并排站成一排，如果,A B必须相邻且B在A的右边，则不同的排法有（） A、60种 B、48种 C、36种 D、24种 2.相离问题插空排:元素相离（即不相邻）问题，可先把无位置要求的几个元素全排列，再把规定的相离的几个元素插入上述几个元素的空位和两端. 例2.七人并排站成一行，如果甲乙两个必须不相邻，那么不同的排法种数是（） A、1440种 B、3600种 C、4820种 D、4800种 3.定序问题缩倍法:在排列问题中限制某几个元素必须保持一定的顺序，可用缩小倍数的方法. 例3.A,B,C,D,E五人并排站成一排，如果B必须站在A的右边（,A B可以不相邻）那么不同的排法有（）A、24种 B、60种 C、90种 D、120种 4.标号排位问题分步法:把元素排到指定位置上，可先把某个元素按规定排入，第二步再排另一个元素，如此继续下去，依次即可完成. 例4.将数字1，2，3，4填入标号为1，2，3，4的四个方格里，每格填一个数，则每个方格的标号与所填数字均不相同的填法有（） A、6种 B、9种 C、11种 D、23种 5.有序分配问题逐分法:有序分配问题指把元素分成若干组，可用逐步下量分组法. 例5.（1）有甲乙丙三项任务，甲需2人承担，乙丙各需一人承担，从10人中选出4人承担这三项任务，不同的选法种数是（） A、1260种 B、2025种 C、2520种 D、5040种 （2）12名同学分别到三个不同的路口进行流量的调查，若每个路口4人，则不同的分配方案有（） A、 444 1284 C C C 种 B、 444 1284 3C C C 种 C、 443 1283 C C A 种 D、 444 1284 3 3 C C C A种 6.全员分配问题分组法: 例6.（1）4名优秀学生全部保送到3所学校去，每所学校至少去一名，则不同的保送方案有多少种？ （2）5本不同的书，全部分给4个学生，每个学生至少一本，不同的分法种数为（） A、480种 B、240种 C、120种 D、96种 7.名额分配问题隔板法: 例7：10个三好学生名额分到7个班级，每个班级至少一个名额，有多少种不同分配方案？ 8.限制条件的分配问题分类法: 例8.某高校从某系的10名优秀毕业生中选4人分别到西部四城市参加中国西部经济开发建设，其中甲同学不到银川，乙不到西宁，共有多少种不同派遣方案？ 9.多元问题分类法：元素多，取出的情况也多种，可按结果要求分成不相容的几类情况分别计数再相加。 例9（1）由数字0，1，2，3，4，5组成没有重复数字的六位数，其中个位数字小于十位数字的共有（）A、210种 B、300种 C、464种 D、600种 （2）从1，2，3…，100这100个数中，任取两个数，使它们的乘积能被7整除，这两个数的取法（不计顺序）共有多少种？ （3）从1，2，3，…，100这100个数中任取两个数，使其和能被4整除的取法（不计顺序）有多少种？

3--装错信封问题

装错信封问题 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 模型求解 应用集合中的容斥原理，我们就可得到“装错信封问题”的数学模型的求解公式． 设I表示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个不同元素的排列中

欧拉装错信封问题

欧拉装错信封问题 “装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli ，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli ，1700－1782)提出来的，大意如下： 一个人写了n 封不同的信及相应的n 个不同的信封，他把这n 封信都装错了信封，问都装错信封的装法有多少种？ 1. 一个人写了4封不同的信及相应的4个不同的信封，他把这4封信都装错了 信封，问都装错信封的装法有多少种？ 【解析】分为两步 （1）首先让A 信选信封，有3种选择，假设A 选择了b 信封 （2）接着让B 信选信封，选择情况可分为两大类 ○ 1B 信选择了a 信封（A 信与B 信相互选择对方的信封） 剩下了C 信、D 信去选择c 信封、d 信封，相当于是2封不同的信装入对应的2个不同的信封，有2A 种装法。 ○ 2B 信不选择a 信封 d D 信封 信c b a C B A d D 信封 信c b a C B A

相当于3封信装入对应的3个不同的信封（因为B 信不选择a 信封，所以可以将a 信封看成b 信封），有3A 种装法。 综上，由乘法原理可得：()()()432=4-13219A A A +=?+=（种）装法。 同理我们可以总结出递推公式：()()12=-1n n n A n A A --+ （拓展：装错信封求解公式()11 1!1-11!2! !n n A n n ??=-++ +? ??? ） 2. 同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺 年卡．则四张贺年卡的不同分配方式有 _____种 (1993年全国高考题理科17题) 3. 有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了 一顶帽子回家．回家后，他们的妻子都发现他们戴了别人的帽子．问5个客人都不戴自己帽子的戴法有多少种？ × ×d D 信封 信c b a(b ) C B A

数量关系个常见问题公式

一.页码问题 对多少页出现多少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、16 B、17 C、18 D、19 【解析】此题看上去是一个排列组合题，但是却是使用的多边形对角线的原理在解决此题。按照排列组合假设总数为X人则Cx取3=152但是在计算X时却是相当的麻烦。我们仔细来分析该题目。以某个人为研究对象。则这个人需要握x-3次手。每个人都是这样。则总共握了x×(x-3)次手。但是没2个人之间的握手都重复计算了1次。则实际的握手次数是x×(x-3)÷2=152计算的x=19人三，钟表重合公式 钟表几分重合，公式为：x/5=(x+a)/60a时钟前面的格数 四，时钟成角度的问题 设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)。 证明：设A、B两地相距S，则 往返总路程2S，往返总共花费时间s/a+s/b 故v=2s/(s/a+s/b)=2ab/(a+b) 六，空心方阵的总数 空心方阵的总数=(最外层边人(物)数-空心方阵的层数)×空心方阵的层数×4 =最外层的每一边的人数^2-(最外层每边人数-2*层数)^2 =每层的边数相加×4-4×层数 空心方阵最外层每边人数=总人数/4/层数+层数 方阵的基本特点：①方阵不论在哪一层，每边上的人(或物)数量都相同.每向里一层边上的人数就少2;

解决排列组合问题的常用方法

解决排列组合问题的常用方法 1.特殊元素，优先处理；特殊位置，优先考虑 例1：六人站成一排，求甲不在排头，乙不在排尾的排列数（） .520 C 答案：A 分析：法1:先考虑排头，排尾，但这两个要求相互有影响，因而考虑分类。 第一类：乙在排头，有A种站法。 第二类：乙不在排头，当然他也不能在排尾，这时候有4种选择即C，还剩5个位置，甲不能再排头所以只有4种选择C，剩下的全排列，即有CCA种站法。 2.反面考虑法 法2: 全排列减掉甲在排头的、乙在排尾的、再加上他们多减的部分（正好甲在排头，乙在排尾） A-A*2+A =504 例2：某单位邀请10名教师中的6位参加一个会议，其中甲乙两位不能同时参加，则邀请的不同方法有多少种（） .98 C 答案：D 解析：法1:①甲参加，乙不参加，有C=56种 ②乙参加，甲不参加，有C=56种 ③甲，乙都不参加，有C=28种 则邀请的不同方法有56+56+28=140种 法2:从反面考虑，甲乙都参加，有C=70种 C -C=140 3.捆绑法 例3：A、B、C、D、E五人排成一排，其中A、B两人必须站在一起，共有（）种排法。 .72 C D24 答案：C

解析:将A 、B 捆绑一起，与C 、D 、E 一起排，共有2444=A 种排法，A 、B 又有 222=A 种排法，共有48224=?种排法。 例4：从单词“equation ”选5个不同的字母排成一排，且含有qu （其中qu 相连且顺序不变），共有（）种排法。 .480 C D840 答案：B 解析：①从剩下的6个字母里选3个，有C(6，3)=20， ②再将这3个字母和qu 全排列A=24 所以共有20×24=480种排法 4.错位排列 错位排列问题：有n 封信和n 个信封，每封信都不装在自己的信封里， 比如： 2封信就有1种装法； 3封信的具体装法 1→2,2→3,3→1和1→3,2→1,3→2就有2种装法； 随着信封数目的增多，这种问题也随之复杂多了。 应用集合中的容斥原理，我们就可得到“装错信封问题”的数学模型的求解公式，请牢记： 设这n 个数的错位排列数为n D ，当5,4,3,2,1=n 时，01=D ，12=D ， 23=D ，94=D ，445=D …，经过枚举我们可以得到：))(1(21--+-=n n n D D n D 例5：甲乙丙丁四个同学站成一队，从左到右数，如果甲不排在第一个位置，乙不排在第二个位置，丙不排在第三个位置，丁不排在第四个位置，那不同的排法有几种 .11 C D24 答案：A 5.间接计数法.(排除法) 例6： 三行三列共九个点，以这些点为顶点可组成多少个三角形 B.71 C72 D76

有趣的概率问题

有趣的概率问题 保险业的兴起 18世纪的欧洲，因工商业的迅速发展，加之概率论的研究，兴起了一门崭新的行业――保险业. 保险公司为了获取利润，必须先调查统计火灾、水灾、意外死亡等事件的概率，据此来确定保险的价格. 例如，要确定人寿保险的价格，先统计各年龄段死亡的人数，如右表. 然后算出死亡概率，如40岁，死亡概率为765÷78 106≈0.009 8，如有一万个40岁的人参加保险，每人付A元保险金，死亡可得B元人寿保险金，预期这1万个人中死亡数是9.8人，因此，保险公司需付出9.8×B元人寿保险金，其收支差额10 000×A-9.8×B（元）就是公司的利润. 扑克牌中的概率 四条（四张同点数的牌）出现概率≈0.0 002 401； 同花（四张同花色的牌）出现概率≈0.001 981； 顺子（五张连续点数的牌）出现概率≈0.00 394； 同花顺（五张同花色的顺子）出现概率≈0.00 001 539； 葫芦（三张同点数，二张另同点数）出现概率≈0.00 144. 按照概率的大小，决定打牌的游戏规则：

同花顺>四条>葫芦>同花>顺子. 两个骰子的概率 装错信封 概率计算往往与组合计数有关，这里介绍一下“装错信封”问题. 装错信封问题由法国数学家蒙莫尔于1713年提出，并给出解法. 后来瑞士数学家伯努利提出等价命题. 大数学家欧拉称赞该问题是组合数学的妙题. 某人写了4封信，并在4只信封上写下4个收信人的地址与姓名. 但匆忙之中，他把所有信笺装错了信封. 问有几种可能的错装情况？ 我们把信封记为A、B、C、D， 相应的信笺记为a、b、c、d. 两封信装错的可能性只有1种：Ab Ba 三封信装错的可能性只有2种： Ab Bc Ca 和Ac Ba Cb 四封信装错的可能性共有9种： Ab Ba Cd Dc Ac Ba Cd Db Ad Ba Cb Dc Ab Bc Cd Da Ac Bd Ca Db Ad Bc Ca Db Ab Bd Ca Dc Ac Bd Cb Da Ad Bc Cb Da 同学的生日会相同吗 如果我说“班上一定有两个同学的生日是相同的！”你

伯努利错装信封问题

伯努利-欧拉错装信封问题 设有变号为1~n 个不同的信封和编号为1~n 封不同的信，现将n 封信装入n 个信封内，则全部装错的有多少种情况？（信封的编号与信的编号不同） 假设n 封信全装错的不同情况有a n 种，则a 1=0，a 2=1，a 3=2； 首先装第1封信，有n －1种方法，不妨设第1封信装入第k 号信封，第二步，装第k 封信， 分以下两种情况： 当第k 封信恰装入第1号信封，则剩下n －2个信封和n －2封信错装，不同的方法有a n －2种， 当第k 封信没有装入第1号信封时，不妨将第1号信封视作第k 个信封，则问题转化为n －1封信错装，不同的错装方式为a n －1. 因此a n =(n －1)(a n －1+a n －2)，n ≥3 接下来只要求出通项公式即可. 令b n =a n n ! ，则a n =n !b n ，则n !b n =(n －1)(n －1)!b n －1＋(n －1)(n －2)!b n －2 即n !b n =(n －1)b n －1＋b n －2，整理得n (b n －b n －1)=－(b n －1－b n －2) 令c n =b n －b n －1，则c n c n －1 ＝－1n ，c 2=b 2－b 1=12， 由累乘法，求得c n c 2＝(－1)n ·13·4·5·…·n ，∴c n =(－1)n ·1n !， 即b n －b n －1=(－1)n ·1n ! ，

由累加法，得b n －b 1=12!－13!＋14!＋…＋(－1)n ·1n ! ， 又因为b 1=a 1=0，所以b n =12!－13!＋14!＋…＋(－1)n ·1n ! ， 即a n n !=12!－13!＋14!＋…＋(－1)n ·1n ! ， a n =n !? ????1－11!＋12!－13!＋…＋(－1)n ·1n !.

容斥定理解伯努利装错信封问题

容斥定理解伯努利装错信封问题 错排问题是组合数学中的问题之一。考虑一个有n 个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。n 个元素的错排数记为Dn 。研究一个排列错排个数的问题，叫做错排问题或称为更列问题。错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题：在写信时将n 封信装到n 个不同的信封里，有多少种全部装错信封的情况？有多少种至少有一封装入正确信封？ 解：固定n 个信封顺序，n 封信均装错信封,实际上相当于{1,2, …, n} 错位排列问题。 设Ai 为第i 封信装入正确信封的方法集合，则伯努利装错信封问题即为求n 个性质均不满足的方法的个数，即 n A A A (21) ①设A 为n 个封信任意装入n 个信封的方法集合，显然|A|=n! ②设Ai 为第i 封信装入正确信封的方法集合，显然| Ai |=(n-1)! ③第i1,i2,…,ik 这k 封信装入正确信封的方法集合，则 )!(...21k n A A A k i i i -= 另外i1,i2,...,ik 这k 封信的选取有C(n,k)种方法 ④根据容斥原理，n 封信均没装入正确信封的方法数有 n A A A (21)

=)!()1(...)!()1(...)!2(2)!1(1!n n n n k n k n n n n n n n k -???? ??-++-???? ??-+--???? ??+-???? ??- =??? ? ??-++-+-+-!)1(...!)1(...!21!111!n k n n k 另外，n 封信中至少有一封装入正确信封 n A A A (21) =)!()1(...)!()1(...)!2(2)!1(1n n n n k n k n n n n n n k -??? ? ??-++-???? ??-++-???? ??--???? ?? =??? ??-++-+--!1)1(...!41!31!21!11!1n n n

错位重排公式推导

错位重排： 错位重排是指一种比较难理解的复杂数学模型，是伯努利和欧拉在错装信封时发现的，因此又称伯努利-欧拉装错信封问题。 简介： 表述为：编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法？ 对这类问题有个固定的递推公式，记n封信的错位重排数为Dn，则D1=0，D2=1， Dn=（n-1）（Dn-2+Dn-1）此处n-2、n-1为下标。 n>2 我们只需记住Dn的前几项：D1=0，D2=1，D3=2，D4=9，D5=44。我们只需要记住结论，进行计算就可以。 【例】五个盒子都贴了标签，全部贴错的可能性有多少种？ 即全贴错标签，N个项数全部排错的可能数，可以总结出数列：0，1，2，9，44，265，……… 可以得到这样一个递推公式：（N-1）*（A+B）=C （A是第一项，B是第二项，C是第三项，N是项数） s(n)=(n-1) [ s（n-1）+s（n-2）] s(2)=1,s(3)=2 s(4)=3*(1+2)=9 s(5)=4*(2+9)=44 s(6)=5*(9+44)=265 ....................

公式由来把编号1→n的小球放到编号1→n的盒子里，全错位排列（1号球不在1号盒，2号球不在2号盒，依次类推），共有几种情况？ ------------------------------------------------------ 设n个球全放错的情况有s(n)种，那么可以有如下思路： 不妨设1号球选择2号盒，接下来会有两种情况： 第一种情况：2号球选择1号盒，剩下（n-2）个球去错排，有s（n-2）种情况 第二种情况：2号球不选择1号盒，则题目可转化为把编号为2→n的小球分别放入编号为1、3、4……→n的盒子错位重排（即2号球不在1号盒、3号球不在3号盒…n号球不在n号盒），相当于n-1个球错位重排，有s(n-1)种 因为1号球可以放到[2,n]中任意一个盒子里，共（n-1）种选择，于是s(n)=(n-1) *[s(n-1)+s(n-2)] s(1)=0 s(2)=1 s(3)=2 s(4)=3*(1+2)=9 s(5)=4*(2+9)=44 s(6)=5*(9+44)=265 .................... 【例题】四位厨师聚餐时各做了一道拿手菜。现在要求每人去品尝一道菜，但不能尝自己做的那道菜。问共有几种不同的尝法？

考试难点攻克之错位重排

考试难点攻克之错位重排 随着我们备考的逐渐深入，很多考生对于数量关系这部分的内容还是感觉难以下手， 那么面对这种情况，就需要我们的考生对于我们数量中一些常考的有明显题型特征且解题 思路清晰明了的一些题型进行重点攻克。比如我们今天要给大家讲到的排列组合问题中常 见的错位重拍问题。 一、题型特征 错位重排问题是一种比较复杂的数学模型，其实就是著名的伯努利一欧拉的装错信封 问题，我们可以形象地叙述如下:“某人写了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。解析：五个瓶子中恰好有三个瓶子的标签贴错了，那我们首先要确定 是哪三个瓶子贴错了，即C35=10种，三个贴错了，即错位重排数为D3=2，根据分步相乘的原理，10*2=20种。

2011-11-12_信封与钱的交换问题

信封与钱的交换问题 - 2011-11-12，The University of Chicago 问题描述：设有信封A 和B ，它们里面都装着钱，已知其中一个的钱数是另一个的两倍。你可以任挑一个信封，把里面的钱拿走。假如你选择了信封A ，打开一看，里面有100元。现在有机会让你改选B ，你是否应该改选。 首先我们来看一种解法：因为B 中的钱数只有两种可能，50元或200元。因为没有任何其它信息可以利用，所以假定出现这两种情况的概率分别为2/1，按照计算期望的方法，可以计算出换信封之后获得的钱数的期望为125元，因此应该换。实际上很容易看出，不管A 中钱数是多少，都应该换。 1252002 15021=?+?. 这种解法的结果似乎有道理，但是和常识不通。因为假如有两个人来分这两个信封，按照上面的计算，即使不打开信封看到钱数，两个人也应该交换，这样获得的钱数的期望都会增加。那么如果允许无穷次的交换，期望岂非都将增大到无穷？ 实际上，这个解法是错误的。这里先解释一下原因。错误的原因在于给定A 中的钱数为x 后，B 中钱数分别为2/x 元和x 2元的条件概率均为2/1的假定是错误的。为什么不能做这样的假定？下面给出一个虽不正确，但和问题本质很接近的一种直观看法。在做出概率均为1/2这一假定时，隐含了“一个信封中的钱数是另一个信封钱数的二倍”这一规则对所有A 中出现的钱数M 都是以等可能成立的。换句话说，+∈R M 上的概率是均匀分布的，+R 为正实数。然而我们知道，在+∈R M 上不能建立均匀分布，因为若建立的话，取某值的概率必然为0，否则不满足概率质量函数之和为1的条件。因此，我们必须先对钱数的分布做一个满足概率论要求的定义，然后才可以在这个条件下计算期望，并最终做出判定。 现对此问题进行理论分析，假定钱数M 的样本空间为正实数。

常见错字解析

100个最常见错别字详解 括号中的为正确的字。 1、按（安）装 “安”与“装”同义，都指按照一定的方法、规格把机械或器材（多指成套的）固定在一起的地方。由于“安装”是动词因此易误作“按装”。还有“安排”也易误作“按排”。“安排”的“安”指“使有合适的位置”。 2、甘败（拜）下风 这里的“拜”指“拜服”，引申为“承认不如别人”，不可写为“败”。 3、自抱（暴）自弃 这里的“暴”指“糟蹋、损害”，写成“抱”就不好解释了。 ４、针贬（砭） “砭”（biān）是古代用以刺激人体皮肉治病的石针。“针砭”比喻深刻批评。 ５、泊（舶）来品 “泊”指“停船靠岸”，是动词语素；“舶”指“航海大船”，是名词语素。“舶来品”指航海大船运来的物品，旧时指进口的商品；写成“泊来品”就不好解释了。 6、脉博（搏） 这里的“搏”指“跳动、搏动”，写成“博”语意不通。 7、松驰（弛） “松”和“弛”同义，都指“松懈、松散”；写成“松驰”就不好解释了。 8、一愁（筹）莫展 这里的“筹”指计算用的筹码，引申为计策。写成“愁”是望文生义所致。 9、穿（川）流不息 这个成语的意思是：像河流中的水那样流淌，永不停息。“川”指“河流”，写成“穿”也是望文生义所造成的。 10、精萃（粹） “精粹”指“精炼纯粹”。“粹”是“****”的意思，常组成“荟萃”一词，如“精英荟萃”也不能缩简为“精萃”。 11重迭（叠） 1964年公布的《简化字总表》中删去了“迭（叠）”，恢复了“叠”字的使用。“迭”现在只用于“更迭、迭次”等词语中。 12、渡（度）假村 在现代汉语中，“度”的基本义指时间上的经过，“渡”的基本义指由此岸到彼岸。因此，“欢度春节”“度日”“度假村”的“度”不能写作“渡”。 13、防（妨）碍 “妨”与“碍”同义，都指“阻碍”，故“妨碍”指“阻碍”；写成“防碍”则变成“防止阻碍”的意思了。 14、幅（辐）射 “辐”指车轮中边接车毂和轮圈的一条条直棍儿。“辐射”指从中心向各个方向沿着直线伸展出去，写成“幅射”就不好解释了。 15、一幅（副）对联

信封问题

“装错信封问题”的数学模型与求解 1 问题的提出 1)同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡．则四张贺年卡的不同分配方式有 [ ] A．6种B．9种 C．11种D．23种 (1993年全国高考题理科17题) 2)有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家．回家后，他们的妻子都发现他们戴了别人的帽子．问5个客人都不戴自己帽子的戴法有多少种？ 上述两个问题，实质上是完全一样的．是被著名数学家欧拉(Leonhard Euler，1707－1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例．“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(Daniel Bernoulli，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 模型求解

常见错字解析讲解学习

常见错字解析

100个最常见错别字详解 括号中的为正确的字。 1、按（安）装 “安”与“装”同义，都指按照一定的方法、规格把机械或器材（多指成套的）固定在一起的地方。由于“安装”是动词因此易误作“按装”。还有“安排”也易误作“按排”。“安排”的“安”指“使有合适的位置”。 2、甘败（拜）下风 这里的“拜”指“拜服”，引申为“承认不如别人”，不可写为“败”。 3、自抱（暴）自弃 这里的“暴”指“糟蹋、损害”，写成“抱”就不好解释了。 ４、针贬（砭） “砭”（biān）是古代用以刺激人体皮肉治病的石针。“针砭”比喻深刻批评。 ５、泊（舶）来品 “泊”指“停船靠岸”，是动词语素；“舶”指“航海大船”，是名词语素。“舶来品”指航海大船运来的物品，旧时指进口的商品；写成“泊来品”就不好解释了。 6、脉博（搏） 这里的“搏”指“跳动、搏动”，写成“博”语意不通。 7、松驰（弛） “松”和“弛”同义，都指“松懈、松散”；写成“松驰”就不好解释了。

8、一愁（筹）莫展 这里的“筹”指计算用的筹码，引申为计策。写成“愁”是望文生义所致。 9、穿（川）流不息 这个成语的意思是：像河流中的水那样流淌，永不停息。“川”指“河流”，写成“穿”也是望文生义所造成的。 10、精萃（粹） “精粹”指“精炼纯粹”。“粹”是“****”的意思，常组成“荟萃”一词，如“精英荟萃”也不能缩简为“精萃”。 11重迭（叠） 1964年公布的《简化字总表》中删去了“迭（叠）”，恢复了“叠”字的使用。“迭”现在只用于“更迭、迭次”等词语中。 12、渡（度）假村 在现代汉语中，“度”的基本义指时间上的经过，“渡”的基本义指由此岸到彼岸。因此，“欢度春节”“度日”“度假村”的“度”不能写作“渡”。 13、防（妨）碍 “妨”与“碍”同义，都指“阻碍”，故“妨碍”指“阻碍”；写成“防碍”则变成“防止阻碍”的意思了。 14、幅（辐）射 “辐”指车轮中边接车毂和轮圈的一条条直棍儿。“辐射”指从中心向各个方向沿着直线伸展出去，写成“幅射”就不好解释了。 15、一幅（副）对联

行测技巧：排列组合问题之错位重排

行测技巧：排列组合问题之错位重排 公务员行测考试主要是考量大家的数学推理能力和逻辑分析能力，下面由出国留学网小编为你精心准备了“行测技巧：排列组合问题之错位重排”，持续关注本站将可以持续获取更多的考试资讯！ 行测技巧：排列组合问题之错位重排 公务员考试中虽然数量关系的题目比较难，但是有些特殊的题型是可以直接套用固定公式的。这些题型解题的关键就在于区分题型以及记住相应结论。错位重排就是这种题型。接下来就给大家介绍一下什么是错位重排，以及这类题型该如何作答。 错位重排是一个排列组合问题。是伯努利和欧拉在错装信封时发现的，因此又称伯努利-欧拉装错信封问题。 【题型表述】编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法? 【解析】这个问题如果数量比较少时还比较简单，比如说n=1时，0种;n=2时，1种。但是n一旦比较大时就比较麻烦了。其实对这类问题有个固定的递推公式，如果记n封信的错位重排数为Dn，则D1=0，D2=1，Dn=(n-1)(Dn-2+Dn-1)(n>2)。 其实在考试中n一般不会超过5，也就是说我们只需记住Dn的前几项：D1=0，D2=1，D3=2，D4=9，D5=44。我们只需要记住结论，进行计算就可以。 我们来看一下考题是如何考察的。 【例1】四位厨师聚餐时各做了一道拿手菜。现在要求每人去品尝一道菜，但不能尝自己做的那道菜。问共有几种不同的尝法? A.6种 B.9种 C.12种 D.15种 【解析】答案：B。记住结论D4=9。直接锁定答案。 【例2】办公室工作人员一共有8个人，某次会议，已知全部到场。问：恰好有3个人坐错位置的情况一共有多少种? A.78 B.96 C.112 D.146 【解析】答案：C。8个人有3个坐错了，我们首先得确定哪3个坐错了。即C(8，3)=56。3个人坐错相当于3个人都没有坐在他原来的位置上，也就说相当于三个元素的错位重排，一共有2种。再用分步相乘得到一共有56X2=112种。选择C。 【例3】五个瓶子贴标签，其中恰好贴错了三个，则错得情况可能有多少种? A.10 B.20 C.30 D.40 【解析】答案：B。同样的思路。先选出来哪3个贴错了，即C(5，3)=10。三个的错位重排D3=2。因此答案选B。 因此对于这类题型，大家一定要牢记结论。结合排列组合问题灵活应