《第2章 计数问题优秀课件.ppt》由会员分享，可在线阅读，更多相关《第2章 计数问题优秀课件.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2 2章章 计数问题计数问题第1页，本讲稿共82页2022/10/25第一篇第一篇 预备知识预备知识第第2 2章章 计数问题计数问题第2页，本讲稿共82页2022/10/252.0 2.0 内容提要内容提要容斥原理与鸽笼原理3离散概率4乘法原理和加法原理1排列与组合2递归关系5第3页，本讲稿共82页2022/10/252.1 2.1 本章学习要求本章学习要求重点掌握一般掌握了解11乘法原理和加法原理2排列组合的计算 3利用容斥原理计算有限集合的交与并 31 离散概率2 离散概念的计 算公式及性质 21 鸽笼原理2 鸽笼原理的简单应用3 递归关系4 递归关系的建立和计算 第4页，本讲稿共82
2、页2022/10/25表表2.2.12.2.1开胃食品主食饮料种类价格(元)种类价格种类价格玉米片(Co)2.15汉堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85鱼排(F)3.15可乐(C)0.75啤酒(B)0.75第5页，本讲稿共82页2022/10/252.2.1 2.2.1 乘法原理乘法原理 如果一些工作需要如果一些工作需要t t步完成步完成，第一步有，第一步有n n1 1种不同种不同的选择，第二步有的选择，第二步有n n2 2种不同的选择，种不同的选择，第，第t t步有步有n nt t种不同的选择，那么完成这项工作所有可能的选择种不同的选择
3、，那么完成这项工作所有可能的选择种数为：种数为：第6页，本讲稿共82页2022/10/25例例2.2.2 Melissa2.2.2 Melissa病毒病毒19901990年，一种名叫年，一种名叫MelissaMelissa的病毒利用侵吞系统资源的方法来的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，子邮件传播。当字处理文档被打开时，宏从用户的地址本中宏从用户的地址本中找出前找出前5050个地址个地址，并将病毒转发给他们。用户接收到这些，并将病毒转发给他们。用户接收到这些被转发
4、的附件并将字处理文档打开后，病毒会自动继续被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。统将会死锁甚至崩溃。问经过四次转发，共有多少个接收问经过四次转发，共有多少个接收者？者？解 根据Melissa病毒的扩散原理，经过四次转发，共有50505050+505050+5050+50+1=6377551个接收者。第7页，本讲稿共82页2022/10/25例例2.2.32.2.3在一幅数字图
5、像中，若在一幅数字图像中，若每个像素点用每个像素点用8 8位进行编码位进行编码，问问每个点有多少种不同的取值。每个点有多少种不同的取值。分析分析 用用8 8位进行编码可分为位进行编码可分为8 8个步骤：选择第一位，个步骤：选择第一位，选择第二位，选择第二位，选择第八位。每一个位有两种，选择第八位。每一个位有两种选择，故根据乘法原理，选择，故根据乘法原理，8 8位编码共有位编码共有22222222=222222222=28 8=256=256种取值。种取值。解解 每个点有每个点有256(=2256(=28 8)种不同的取值。种不同的取值。第8页，本讲稿共82页2022/10/252.2.2 2.
6、2.2 加法原理加法原理 假定假定X X1 1,X,X2 2,X,Xt t均为集合，第均为集合，第i i个集合个集合X Xi i有有n ni i个元素。如个元素。如XX1 1,X,X2 2,X,Xt t 为为两两不相交两两不相交的集合，的集合，则可以从则可以从X X1 1,X,X2 2,X,Xt t中选出的元素总数为：中选出的元素总数为：n n1 1+n+n2 2+n+nt t。即集合即集合即集合即集合X X X X1 1 1 1XXXX2 2 2 2XXXXt t t t含有含有含有含有n n n n1 1 1 1+n+n+n+n2 2 2 2+n+n+n+nt t t t个元素。个元素。个
7、元素。个元素。第9页，本讲稿共82页2022/10/25例例2.2.42.2.4由由AliceAlice、BenBen、ConnieConnie、DolphDolph、EgbertEgbert和和FranciscoFrancisco六个人组成的委员会六个人组成的委员会，要，要选出一个主席、选出一个主席、一个秘书和一个出纳员。一个秘书和一个出纳员。（1 1）共有多少种选法？）共有多少种选法？（2 2）若）若主席必须从主席必须从AliceAlice和和BenBen种选出种选出，共有多少，共有多少种选法？种选法？（3 3）若）若EgbertEgbert必须有职位必须有职位，共有多少种选法？，共有多少
8、种选法？（4 4）若）若DolphDolph和和FranciscoFrancisco都有职位都有职位，共有多少种，共有多少种选法？选法？第10页，本讲稿共82页2022/10/25例例2.2.4 2.2.4 解解（1 1）根据）根据乘法原理乘法原理，可能的选法种数为，可能的选法种数为654=654=120120；（2 2）法一法一 根据题意，确定职位可分为根据题意，确定职位可分为3 3个步骤：个步骤：确定主席有确定主席有2 2种选择；主席选定后，秘书有种选择；主席选定后，秘书有5 5个人选；个人选；主席和秘书都选定后，出纳有主席和秘书都选定后，出纳有4 4个人选。根据个人选。根据乘法乘法原理原
9、理，可能的选法种数为，可能的选法种数为254=40254=40；第11页，本讲稿共82页2022/10/25例例2.2.4 2.2.4 解解(续续)法二法二 若若AliceAlice被选为主席，共有被选为主席，共有54=2054=20种方法确定其种方法确定其他职位；若他职位；若BenBen为主席，同样有为主席，同样有2020种方法确定其他种方法确定其他职位。由于两种选法得到的集合不相交，所以根据职位。由于两种选法得到的集合不相交，所以根据加法原理加法原理，共有，共有202020=4020=40种选法；种选法；第12页，本讲稿共82页2022/10/25例例2.2.4 2.2.4 解解(续续)(
10、3)(3)法一法一 将确定职位分为将确定职位分为3 3步：步：确定确定EgbertEgbert的的职位职位,有有3 3种方法；种方法；确定余下的较高职位人选确定余下的较高职位人选,有有5 5个人选；个人选；确定最后一个职位的人选确定最后一个职位的人选,有有4 4个个人选。根据人选。根据乘法原理乘法原理，共有，共有354=60354=60种选种选法；法；第13页，本讲稿共82页2022/10/25例例2.2.4 2.2.4 解解(续续)法二法二 根据根据(1)(1)的结论，的结论，如果如果EgbertEgbert为主席为主席，有，有2020种方法确定余下的职位；种方法确定余下的职位；若若Egbe
11、rtEgbert为秘书，为秘书，有有2020种种方法确定余下的职位；方法确定余下的职位；若若EgbertEgbert为出纳员为出纳员，也有，也有2020种方法确定余下的职位。由于三种选法得到的集合种方法确定余下的职位。由于三种选法得到的集合不相交，根据不相交，根据加法原理加法原理，共有，共有2020202020=6020=60种选法；种选法；第14页，本讲稿共82页2022/10/25例例2.2.4 2.2.4 解解(续续)（4 4）将给）将给DolphDolph、FranciscoFrancisco和另一个人指定职位和另一个人指定职位分为分为3 3步：步：给给DolphDolph指定职位，指
12、定职位，有有3 3个职位可选；个职位可选；给给FranciscoFrancisco指定职位，指定职位，有有2 2个职位可选；个职位可选；确定最后一个职位的人选确定最后一个职位的人选，有，有4 4个人选。个人选。根据根据乘法原理乘法原理，共有，共有324=24324=24种选法。种选法。第15页，本讲稿共82页2022/10/252.3 2.3 排列与组合排列与组合 Zeke Zeke、YungYung、XenoXeno和和WilmaWilma四个候选人竞选同一四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次
13、序打印在选票上。响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？会有多少种不同的选票呢？从某个集合中有序的选取若干个元素的问题，称为从某个集合中有序的选取若干个元素的问题，称为排列问题排列问题。第16页，本讲稿共82页2022/10/252.3.1 2.3.1 排列问题排列问题定义定义2.3.12.3.1 从含从含n n个不同元素个不同元素的集合的集合S S中中有序有序选取选取的的r r个元素叫做个元素叫做S S的一个的一个r-r-r-r-排列排列排列排列，不同的排列总数，不同的排列总数记为记为P(n,r)P(n,r)。如果。如果r=nr=n，则称这个排列为，则称这个排列
14、为S S的一的一个个全排列全排列全排列全排列，简称为，简称为S S的排列。的排列。显然显然，当当当当rnrnrnrn时，时，时，时，P(n,r)=0P(n,r)=0P(n,r)=0P(n,r)=0。第17页，本讲稿共82页2022/10/25例例2.3.12.3.1从含从含3 3个不同元素的集合个不同元素的集合S S中有序选取中有序选取2 2个元素的排个元素的排列总数。列总数。解解 从含从含3 3个元素的不同集合个元素的不同集合S S中有序选取中有序选取2 2个元素个元素的排列总数为的排列总数为6 6种。种。如果将这如果将这3 3个元素记为个元素记为A A、B B和和C C，则，则6 6个排列
15、为个排列为AB,AC,BA,BC,CB,CAAB,AC,BA,BC,CB,CA。第18页，本讲稿共82页2022/10/25定理定理2.3.12.3.1对满足对满足rnrn的正整数的正整数n n和和r r有有第r位第r-1位第3位第2位第1位nn-1n-2 n-(r-2)图2.3.1n-(r-1)第19页，本讲稿共82页2022/10/25推论推论2.3.22.3.2n n个不同元素的排列共有个不同元素的排列共有n n！种，其中！种，其中 第20页，本讲稿共82页2022/10/25例例2.3.22.3.2 A,B,C,D,E,F A,B,C,D,E,F组成的排列中，组成的排列中，（1 1）有
16、多少含有）有多少含有DEFDEF的子串？的子串？（2 2）三个字母）三个字母D D、E E和和F F相连的有多少种？相连的有多少种？解解 (1)(1)将将DEFDEF看成一个对象看成一个对象，根据推论，根据推论2.3.22.3.2，满足条件的排，满足条件的排列为列为A,B,C,DEFA,B,C,DEF的全排列，共有的全排列，共有4 4！=24=24种；种；（2 2）根据题意，满足该条件的排列分为两步：第一步）根据题意，满足该条件的排列分为两步：第一步确确定定D,ED,E和和F F三个字母的全排列三个字母的全排列，有，有3 3！种排列，第二步将！种排列，第二步将已排已排序的序的D,ED,E和和F
17、 F看成一个整体看成一个整体，与，与A,BA,B和和C C共共4 4个元素构造出个元素构造出A,B,A,B,C,D,E,FC,D,E,F的全排列，有的全排列，有4 4！种排列。又根据乘法原理，满足！种排列。又根据乘法原理，满足条件的排列总数有条件的排列总数有3 3！44！=144=144。第21页，本讲稿共82页2022/10/25例例2.3.32.3.36 6个人围坐在圆桌上，有多少种不同的坐法？通过个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。转圈得到的坐法视为同一种坐法。解解 6 6个人围坐在圆桌上，个人围坐在圆桌上，有有120120种不同的坐法。种不同的坐法。
18、图2.3.2AEFBDCn n n n个人围坐圆桌上，有个人围坐圆桌上，有个人围坐圆桌上，有个人围坐圆桌上，有(n-1)(n-1)(n-1)(n-1)！种不同的坐法，我们称！种不同的坐法，我们称！种不同的坐法，我们称！种不同的坐法，我们称这种排列为这种排列为这种排列为这种排列为环排列环排列环排列环排列，从，从，从，从n n n n个人中选出个人中选出个人中选出个人中选出r r r r个人为圆桌而坐个人为圆桌而坐个人为圆桌而坐个人为圆桌而坐称为称为称为称为环形环形环形环形r-r-r-r-排列排列排列排列。第22页，本讲稿共82页2022/10/25定理定理2.3.32.3.3含含n n个不同元素
19、的集合的个不同元素的集合的环形环形r-r-排列数排列数P Pc c(n,r)(n,r)是是 。(2.3.3)(2.3.3)第23页，本讲稿共82页2022/10/25例例2.3.42.3.4求满足下列条件的排列数。求满足下列条件的排列数。(1)101)10个男孩和个男孩和5 5个女孩个女孩站成一排站成一排，无两个女孩相邻无两个女孩相邻。(2)10(2)10个男孩和个男孩和5 5个女孩个女孩站成一圆圈站成一圆圈，无两个女孩相邻无两个女孩相邻.解解 (1)(1)根据推论根据推论2.3.22.3.2，1010个男孩的全排列为个男孩的全排列为10!10!，5 5个女孩插入到个女孩插入到1010个男孩形
20、成的个男孩形成的1111个空格中的插入方法个空格中的插入方法数为数为P(11,5)P(11,5)。根据乘法原理，。根据乘法原理，1010个男孩和个男孩和5 5个女孩个女孩站成一排，没有两个女孩相邻的排列数为：站成一排，没有两个女孩相邻的排列数为：10!P(11,5)=10!P(11,5)=（10!11!)/6!10!11!)/6!。第24页，本讲稿共82页2022/10/25例例2.3.4 2.3.4 解（续）解（续）（2 2）根据定理根据定理2.3.32.3.3，1010个男孩站成一个圆圈的个男孩站成一个圆圈的环排列数为环排列数为9 9！，！，5 5个女孩插入到个女孩插入到1010男孩形成的
21、男孩形成的1010个个空中的插入方法数为空中的插入方法数为P(10,5)P(10,5)。根据乘法原理，。根据乘法原理，1010个男孩和个男孩和5 5个女孩站成一个圆圈，没有两个女孩相个女孩站成一个圆圈，没有两个女孩相邻的排列法为：邻的排列法为：9!P(10,5)=9!P(10,5)=9!P(10,5)=9!P(10,5)=（9!10!)/5!9!10!)/5!9!10!)/5!9!10!)/5!。第25页，本讲稿共82页2022/10/252.3.2 2.3.2 组合问题组合问题定义定义2.3.22.3.2 从含有从含有n n个不同元素的集合个不同元素的集合S S中无序选中无序选取的取的r r
22、个元素叫做个元素叫做S S的一个的一个r-r-组合组合，不同的组合总，不同的组合总数记为数记为C(n,r)C(n,r)。当当当当nr=0nr=0nr=0nr=0时，规定时，规定时，规定时，规定C(n,r)=1C(n,r)=1C(n,r)=1C(n,r)=1。显然，当显然，当显然，当显然，当rnrnrnrn时，时，时，时，C(n,r)=0C(n,r)=0C(n,r)=0C(n,r)=0。第26页，本讲稿共82页2022/10/25定理定理2.3.42.3.4对满足对满足0 r n0m)m(nm)个鸽笼，则个鸽笼，则存在存在一个一个鸽笼鸽笼至少住至少住进进 +1 +1只鸽子。只鸽子。这里，这里，表
23、示小于等于表示小于等于x x的最大整数。的最大整数。第48页，本讲稿共82页2022/10/25例例2.4.62.4.6如果一个图书馆里如果一个图书馆里3030本书，共有本书，共有1200312003页，那么必页，那么必然有一本书至少有然有一本书至少有401401页。页。证明证明：设页是：设页是鸽子鸽子，书是，书是鸽笼鸽笼，把每页分配到它所，把每页分配到它所出现的书中，根据定理出现的书中，根据定理2.4.52.4.5，则存在一个，则存在一个鸽笼鸽笼至至少住进少住进即结论得证。即结论得证。第49页，本讲稿共82页鸽巢原理举例2例例2 2：证明在任意证明在任意6 6个人中，要么有个人中，要么有3
24、3个人互相个人互相认识认识，要么有要么有3 3个人互相个人互相不不认识认识。证明：证明：每个人用一个点表示，如果每个人用一个点表示，如果a a，b b认识，用红认识，用红线连接，否则绿线链接。线连接，否则绿线链接。那么就是要证明下图中存在那么就是要证明下图中存在红色红色或或绿色绿色的三角形。的三角形。红色红色三角形：三角形：3 3个互相认识的人个互相认识的人绿色绿色三角形：三角形：3 3个互相个互相不不认识的人认识的人cbae第50页，本讲稿共82页(1)(1)：a a连接的连接的5 5条边中一定有条边中一定有3 3条条绿色绿色或或红色红色的，不妨设有三条的，不妨设有三条绿色绿色的的 /*/*
25、鸽洞原理鸽洞原理*/(2)(2)如果如果bdbd边或者边或者bcbc边是边是绿色绿色，则存，则存在在绿色绿色三角形三角形abdabd或者或者abcabc。(3)(3)现在考虑现在考虑bcbc边和边和bdbd边是边是红边红边的情的情况。如果况。如果dcdc边是边是绿色绿色会构成会构成绿色绿色三角三角形形adcadc；如果；如果dcdc边是边是红色红色，会构成，会构成红红色色三角形三角形dbcdbc。证明完毕。证明完毕。鸽巢原理举例2(续)badcbadc第51页，本讲稿共82页2022/10/252.52.5 离散概率简介离散概率简介概率概率(Probability)(Probability)是
26、是1717世纪为分析博弈游戏而发世纪为分析博弈游戏而发展起来的学科，最初计算概率仅有计数一种方法。展起来的学科，最初计算概率仅有计数一种方法。本节主要介绍离散概率的基本概率、基本性质和概本节主要介绍离散概率的基本概率、基本性质和概率计算的简单例子。率计算的简单例子。第52页，本讲稿共82页2022/10/252.5.1 2.5.1 基本概念基本概念问题问题：掷出一个各面同性的骰子，求掷出偶数的概掷出一个各面同性的骰子，求掷出偶数的概率。率。其中其中“各面同性各面同性”是指当骰子掷出时，各个面是指当骰子掷出时，各个面出现的机会均等。出现的机会均等。定义定义2.5.12.5.1 能生成结果的过程称
27、为能生成结果的过程称为实验实验(experiment)(experiment)；实验的结果或结果的组合称为实验的结果或结果的组合称为事件事件(event)(event)，包含所有可能结果的事件称为包含所有可能结果的事件称为样本空间样本空间(sample(sample space)space)。第53页，本讲稿共82页2022/10/252.5.1 2.5.1 基本概念基本概念假如骰子的六个面分别标记为假如骰子的六个面分别标记为1,2,3,4,5,61,2,3,4,5,6，当掷出一个骰子时，一定能掷出，当掷出一个骰子时，一定能掷出6 6种结果中的一种结果中的一种，我们称种，我们称掷出骰子的过程为
28、掷出骰子的过程为实验实验。掷出的结果掷出的结果(假如掷出假如掷出2)2)或或结果的组合结果的组合(假如掷出假如掷出两个骰子，一个掷出两个骰子，一个掷出1 1，一个掷出，一个掷出3)3)称为称为事件事件，当掷出一个骰子时得到的当掷出一个骰子时得到的6 6种可能种可能1,2,3,4,1,2,3,4,5,65,6称为称为样本空间样本空间。第54页，本讲稿共82页2022/10/25例例2.5.12.5.1请举例说明下列实验可能发生的事件，并列出其样请举例说明下列实验可能发生的事件，并列出其样本空间。本空间。（1 1）掷出一个六个面的骰子；）掷出一个六个面的骰子；（2 2）从）从10001000个微处
29、理器中随机抽取个微处理器中随机抽取5 5个；个；（3 3）在北京人民医院选取一个婴儿。）在北京人民医院选取一个婴儿。第55页，本讲稿共82页2022/10/25例例2.5.1 2.5.1 解解可能发生的事件举例如下：可能发生的事件举例如下：（1 1）掷出一个六个面的骰子，得到的点数是）掷出一个六个面的骰子，得到的点数是4 4；（2 2）从）从10001000个微处理器中随机抽取个微处理器中随机抽取5 5个，没有发现个，没有发现次品；次品；（3 3）在北京人民医院选取了一个女婴。）在北京人民医院选取了一个女婴。各实验的样本空间为：各实验的样本空间为：（1 1）1,2,3,4,5,61,2,3,4
30、,5,6；（2 2）从）从10001000个微处理器中选取个微处理器中选取5 5个的所有组合；个的所有组合；（3 3）北京人民医院的所有婴儿。）北京人民医院的所有婴儿。第56页，本讲稿共82页2022/10/25定义定义2.5.22.5.2有限样本空间有限样本空间S S中的事件中的事件E E的概率的概率P(E)P(E)定义为：定义为：。(2.5.1)(2.5.1)其中其中|E|,|S|E|,|S|分别表示集合分别表示集合E E和和S S的基数。的基数。第57页，本讲稿共82页2022/10/25例例2.5.22.5.2掷出一个各面同性的骰子，求掷出偶数的概率。掷出一个各面同性的骰子，求掷出偶数
31、的概率。解解 设掷出偶数这个事件为设掷出偶数这个事件为E E，样本空间为，样本空间为S S，则根，则根据题意据题意|E|=3,|S|=6|E|=3,|S|=6。代入式。代入式(2.5.1)(2.5.1)，得，得P(E)=3/6=1/2P(E)=3/6=1/2。第58页，本讲稿共82页2022/10/25例例2.5.32.5.3掷出两个各面同性的骰子，求点数之和为掷出两个各面同性的骰子，求点数之和为1010的概率。的概率。解解 设点数之和为设点数之和为1010这个事件为这个事件为E E，样本空间为，样本空间为S S，则根据题意则根据题意|E|=3,|S|=36|E|=3,|S|=36。代入式。代
32、入式(2.5.1)(2.5.1)，得得P(E)=3/36=1/12 P(E)=3/36=1/12。第59页，本讲稿共82页2022/10/25例例2.5.42.5.4在福利彩票中，若彩民从在福利彩票中，若彩民从1 15252个数中选取的个数中选取的6 6个数个数与随机生成的中奖数字相同与随机生成的中奖数字相同(不计顺序不计顺序)，则可以赢，则可以赢得大奖。求一张彩票赢得大奖的概率。得大奖。求一张彩票赢得大奖的概率。解解 从从5252个数字中选取个数字中选取6 6个共有个共有C(52,6)C(52,6)种选法，即种选法，即|S|=C(52,6)|S|=C(52,6)，而得大奖的组合只有一种，即，
33、而得大奖的组合只有一种，即|E|=1|E|=1，根据式，根据式(2.5.1)(2.5.1)，得：，得：P(E)=1/C(52,6)=0.00000004P(E)=1/C(52,6)=0.00000004。第60页，本讲稿共82页2022/10/252.5.2 2.5.2 离散概率函数离散概率函数定义定义2.5.32.5.3 如果函数如果函数P P将样本空间将样本空间S S的每一个结果的每一个结果x x映射为实数映射为实数P(x)P(x)，且对任意的，且对任意的xSxS，满足，满足（1 1）0P(x)10P(x)1；（2 2）。则称函数则称函数P P是概率函数是概率函数。说明说明 条件条件(1)
34、(1)保证一个结果的概率为非负数且不超过保证一个结果的概率为非负数且不超过1 1；条件条件(2)(2)保证所有结果的概率之和为保证所有结果的概率之和为1 1，即进行实验，即进行实验后，必出现某个结果。后，必出现某个结果。第61页，本讲稿共82页2022/10/25例例2.5.52.5.5一个一面较重的骰子，一个一面较重的骰子，2 26 6以相同的机会出现，以相同的机会出现，1 1出现的机会是其他数字的出现的机会是其他数字的3 3倍。试求出倍。试求出1 16 6的概率的概率函数值。函数值。解解 设设P(2)=P(3)=P(4)=P(5)=P(6)=aP(2)=P(3)=P(4)=P(5)=P(6
35、)=a，则则P(6)=3aP(6)=3a。又因为。又因为P(1)+P(2)+P(3)+P(4)+P(1)+P(2)+P(3)+P(4)+P(5)+P(6)=1P(5)+P(6)=1，所以有，所以有5a5a3a=13a=1，即，即a=1/8a=1/8。从而从而P(2)=P(3)=P(4)=P(5)=P(6)=1/8 P(2)=P(3)=P(4)=P(5)=P(6)=1/8，P(6)=3/8P(6)=3/8。第62页，本讲稿共82页2022/10/25概率函数概率函数定义定义2.5.42.5.4 设设E E是一个事件，是一个事件，E E的概率函数的概率函数P(E)P(E)定定义为义为 。在例在例2
36、.5.52.5.5中，出现奇数点的概率则为中，出现奇数点的概率则为P(1)+P(3)+P(5)=5/8 P(1)+P(3)+P(5)=5/8。定理定理2.5.12.5.1 设设E E是一个事件，是一个事件，E E的补的概率满足的补的概率满足 。(2.5.2)(2.5.2)第63页，本讲稿共82页2022/10/25例例2.2.6 2.2.6 生日问题生日问题n n个人中，个人中，求至少有两个人生日相同求至少有两个人生日相同(同月同日不计同月同日不计年年)的概率。的概率。假定出生在某天的概率均等，忽略假定出生在某天的概率均等，忽略2 2月月2929日。日。解解 设设E E表示表示“至少两个人生日
37、相同至少两个人生日相同”，则，则 表示表示“没有两个人生日相同没有两个人生日相同”，则，则 。从而从而 。事实上，随着天数n的增加，至少两个人生日相同的概率也随着增加，当n23时，至少有两个人生日相同的概率大于1/2。第64页，本讲稿共82页2022/10/25两个事件并的概率两个事件并的概率定理定理2.5.22.5.2 设设E E1 1和和E E2 2是两个事件，则是两个事件，则 P(EP(E1 1EE2 2)=P(E)=P(E1 1)P(EP(E2 2)P(EP(E1 1EE2 2)(2.5.3)(2.5.3)如果如果E E1 1EE2 2=，即，即E E1 1与与E E2 2为不相交的事
38、件，则有下为不相交的事件，则有下面的推论。面的推论。推论推论2.5.32.5.3 设设E E1 1和和E E2 2是两个不相交的事件，则是两个不相交的事件，则 P(EP(E1 1EE2 2)=P(E)=P(E1 1)P(EP(E2 2)(2.5.4)(2.5.4)第65页，本讲稿共82页2022/10/25例例2.5.72.5.7掷出两个各面同性的骰子，得到掷出两个各面同性的骰子，得到“一对一对”(两个骰两个骰子点数相同子点数相同)或点数和为或点数和为6 6的概率是多少？的概率是多少？解解 设设E E1 1表示事件表示事件“一对一对”，E E2 2表示事件表示事件“点数和点数和为为6 6”，则
39、样本空间大小是，则样本空间大小是3636，事件事件E E1 1的种数为的种数为6,6,即即(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),事件事件E E2 2的种数为的种数为5 5，即即(1,5),(2,4),(3,3),(4,2),(5,1)(1,5),(2,4),(3,3),(4,2),(5,1)。E E1 1EE2 2的种数为的种数为1 1。第66页，本讲稿共82页2022/10/25例例2.5.7 2.5.7 解（续）解（续）从而从而 P(E P(E1 1)=1/6)=1/6 ,P(E,P(
40、E2 2)=5/36,P(E)=5/36,P(E1 1EE2 2)=)=1/36 1/36。根据式根据式(2.5.3)(2.5.3)，有，有 P(EP(E1 1EE2 2)=1/6)=1/65/365/361/36=5/181/36=5/18 。即得到即得到“一对一对”或点数和为或点数和为6 6的概率是的概率是5/185/18 。第67页，本讲稿共82页2022/10/252.62.6 递归关系递归关系递归关系递归关系可用于解决一些特定的计数问题。可用于解决一些特定的计数问题。递归关系是序列中递归关系是序列中第第n n个元素与它相邻前若干个元个元素与它相邻前若干个元素之间的关系素之间的关系。例
41、如例如第一个数是第一个数是5 5；2 2、将前一项加、将前一项加3 3得到后一项。得到后一项。5,8,11,14,5,8,11,14,递归关系递归关系a a a a1 1 1 1=5=5=5=5，a a a an n n n=a=a=a=an-1n-1n-1n-1+3+3+3+3 第68页，本讲稿共82页2022/10/25定义定义2.6.12.6.1对序列对序列a a0 0,a,a1 1,a,a2 2,a,an-1n-1,，用用a a0 0,a,a1 1,a,a2 2,a,an-1n-1中的中的某些项某些项表示表示a an n的等式称为的等式称为递归关系递归关系(recurrence rel
42、ation)(recurrence relation)。显示地给出序。显示地给出序列列a a0 0,a,a1 1,a,a2 2,的有限项的值，称为的有限项的值，称为初始条件初始条件(initial condition)(initial condition)。显然，递归关系和确定的初始条件一起，才能确定显然，递归关系和确定的初始条件一起，才能确定一个序列。一个序列。第69页，本讲稿共82页2022/10/25例例2.6.12.6.1某人投资某人投资10001000元，每年可收益元，每年可收益1212。A An n表示他在第表示他在第n n年末的总资产年末的总资产。求出定义序列。求出定义序列AAn
43、 n 的递归关系和的递归关系和初始条件。初始条件。解解 序列序列AAn n 的的递归关系和初始条件递归关系和初始条件分别为：分别为：A An n=A=An-1n-10.12A0.12An n -1-1=1.12 A=1.12 An n -1-1,n1,n1,A A0 0=1000=1000第70页，本讲稿共82页2022/10/25例例2.6.22.6.2S Sn n表示表示不含子串不含子串“111111”的的n n位字符串的个数。求出位字符串的个数。求出序列序列SSn n 的递归关系和初始条件。的递归关系和初始条件。解解 序列序列SSn n 的的递归关系和初始条件递归关系和初始条件分别为：分
44、别为：S Sn n=S=Sn-1n-1S Sn-2n-2 S Sn-3n-3，n4,n4,S S1 1=2,S=2,S2 2=4,S=4,S3 3=7=7。第71页，本讲稿共82页2022/10/252.7 2.7 计数问题的应用计数问题的应用例例2.7.1 72.7.1 7个科学工作者从事一项机密的技术研究，他们的工作个科学工作者从事一项机密的技术研究，他们的工作室装有电子锁，每位科学工作者都有打开电子锁用的室装有电子锁，每位科学工作者都有打开电子锁用的“钥匙钥匙”。为了安全起见，为了安全起见，必须有必须有4 4位在场时才能打开大门位在场时才能打开大门。试问该电。试问该电子锁子锁至少应具备多
45、少个特征至少应具备多少个特征？每位科学工作者的？每位科学工作者的“钥匙钥匙”至少至少应有多少种特征？应有多少种特征？解解 为了使任意为了使任意3 3个人在场时至少缺少一个特征而打不开门，个人在场时至少缺少一个特征而打不开门，该电子锁该电子锁至少至少应具备应具备C(7,3)=35C(7,3)=35种特征；每个科学工作者的种特征；每个科学工作者的“钥钥匙匙”至少至少要有要有C(6,3)=20C(6,3)=20种特征。种特征。第72页，本讲稿共82页2022/10/25例例2.7.22.7.2某一制造铁盘的工厂，由于设备和技术的原因只能某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制
46、在将生产盘子的重量控制在a a克到（克到（a+0.1a+0.1）克之间）克之间。现需要制成重量相差不超过现需要制成重量相差不超过0.0050.005克的两铁盘来配克的两铁盘来配制一架天平，问该工厂制一架天平，问该工厂至少要生产多少铁盘至少要生产多少铁盘才能得才能得到一对符合要求的铁盘。到一对符合要求的铁盘。第73页，本讲稿共82页2022/10/25例例2.7.2 2.7.2 解解将铁盘按重量分类，将铁盘按重量分类，所有所有a a克到克到a+0.005a+0.005克的分为第一类；克的分为第一类；a+0.005a+0.005克到克到a+0.01a+0.01克的分为一类；克的分为一类；a+0.0
47、1a+0.01克到克到a+0.015a+0.015克的又为一类，克的又为一类，.，最后，最后，a+0.095a+0.095克到克到a+0.1a+0.1克为一类，共计克为一类，共计2020类，类，由由鸽笼原理鸽笼原理知，若该工厂生产知，若该工厂生产2121个铁盘，那么就能个铁盘，那么就能得知有两个铁盘属于同一类，因而它们之间的重量得知有两个铁盘属于同一类，因而它们之间的重量差将不超过差将不超过0.0050.005克。克。第74页，本讲稿共82页2022/10/25例例2.7.3 Fibonacci2.7.3 Fibonacci数列数列假定一对新出生的兔子一个月又成熟，并且再过一假定一对新出生的兔
48、子一个月又成熟，并且再过一个月开始生出一对小兔子。按此规律，在没有兔子个月开始生出一对小兔子。按此规律，在没有兔子死亡的情形下，一对初生的兔子，一年可以繁殖成死亡的情形下，一对初生的兔子，一年可以繁殖成多少队兔子？多少队兔子？解解 因为因为F Fn n=F=Fn-1n-1+F+Fn-2n-2，所以根据迭代法，有，所以根据迭代法，有F F12 12=F=F11 11+F+F1010=2F=2F10 10+F+F9 9=3F=3F9 9+2F+2F8 8 =5F=5F8 8+3F+3F7 7=8F=8F7 7+5F+5F6 6 =89F=89F2 2+55F+55F1 1=89+55=143=89
49、+55=143。第75页，本讲稿共82页2022/10/25例例2.7.42.7.4计算下面算法中基本操作的次数算法计算下面算法中基本操作的次数算法 输入输入：s s1 1,s,s2 2,s,sn n和序列的长度。和序列的长度。输出输出：s s1 1,s,s2 2,s,sn n，按非递减顺序排列。，按非递减顺序排列。第76页，本讲稿共82页2022/10/25例例2.7.4 2.7.4（续）（续）1.selection_sorts(s,n)1.selection_sorts(s,n)2./2./基本情况基本情况3.if(n=1)4.return3.if(n=1)4.return5./5./找到
50、最大的元素找到最大的元素6.max_index=1/6.max_index=1/初始时认为初始时认为s s1 1是最大的元素是最大的元素7.for i=2 to n7.for i=2 to n8.if(s8.if(si ismax_index)/smax_index)/比较得到较大的元素，并更新最大元素比较得到较大的元素，并更新最大元素9.max_index=i 10./9.max_index=i 10./将最大的元素移至序列尾将最大的元素移至序列尾11.swap(s11.swap(sn n,smax_index),smax_index)12.selection_sort(s,n-1)12.s