离散数学教案2

电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院示示 范范 性性 软软 件件 学学 院院20222022年年11 11月月2828日星期一日星期一电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程22022-11-282022-11-28第一篇第一篇 预备知识预备知识第第2 2章章 计数问题计数问题电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程32022-11-282022-11-282.0 2.0 内容提要内容提要容斥原理与鸽笼原理容斥原理与鸽笼原理3离散概率离散概率4乘法原理和加法原理乘法原理和加法原理1排列与组合排列与组合2递归关系递归关系5电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程42022-11-282022-11-282 2.1.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1乘法原理和加乘法原理和加法原理法原理2 2排列组合的计排列组合的计算算 3 3利用容斥原理利用容斥原理计算有限集合的计算有限集合的交与并交与并 31 1 离散概率离散概率2 2 离散概念的计离散概念的计 算公式及性质算公式及性质 21 1 鸽笼原理鸽笼原理2 2 鸽笼原理的简鸽笼原理的简单应用单应用3 3 递归关系递归关系4 4 递归关系的建递归关系的建立和计算立和计算 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程52022-11-282022-11-28表表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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程62022-11-282022-11-282.2.1 2.2.1 乘法原理乘法原理 如果一些工作需要如果一些工作需要t t步完成步完成，第一步有，第一步有n n1 1种种不同的选择，第二步有不同的选择，第二步有n n2 2种不同的选择，种不同的选择，第第t t步有步有n nt t种不同的选择，那么完成这项工作所种不同的选择，那么完成这项工作所有可能的选择种数为：有可能的选择种数为：tnnn21电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程72022-11-282022-11-28例例2.2.2 Melissa2.2.2 Melissa病毒病毒19901990年，一种名叫年，一种名叫MelissaMelissa的病毒利用侵吞系统资源的的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前宏从用户的地址本中找出前5050个地址个地址，并将病毒转发，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文给他们。用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？问经过四次转发，共有多少个接收者？解解 根据根据MelissaMelissa病毒的扩散原理，经过四次转发，病毒的扩散原理，经过四次转发，共有共有50505050505050+5050+50505050+5050+5050+50+150+50+1=6377551=6377551个接收者。个接收者。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82022-11-282022-11-28例例2.2.32.2.3在一幅数字图像中，若在一幅数字图像中，若每个像素点用每个像素点用8 8位进行编码位进行编码，问问每个点有多少种不同的取值。每个点有多少种不同的取值。分析分析 用用8 8位进行编码可分为位进行编码可分为8 8个步骤：选择第一位，个步骤：选择第一位，选择第二位，选择第二位，选择第八位。每一个位有两种，选择第八位。每一个位有两种选择，故根据乘法原理，选择，故根据乘法原理，8 8位编码共有位编码共有2 22 22 22 22 22 22 22=22=28 8=256=256种取值。种取值。解解 每个点有每个点有256(=2256(=28 8)种不同的取值。种不同的取值。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程92022-11-282022-11-282.2.2 2.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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程102022-11-282022-11-28例例2.2.42.2.4由由AliceAlice、BenBen、ConnieConnie、DolphDolph、EgbertEgbert和和FranciscoFrancisco六个人组成的委员会六个人组成的委员会，要，要选出一个主席、选出一个主席、一个秘书和一个出纳员。一个秘书和一个出纳员。（1 1）共有多少种选法？）共有多少种选法？（2 2）若）若主席必须从主席必须从AliceAlice和和BenBen种选出种选出，共有多少，共有多少种选法？种选法？（3 3）若）若EgbertEgbert必须有职位必须有职位，共有多少种选法？，共有多少种选法？（4 4）若）若DolphDolph和和FranciscoFrancisco都有职位都有职位，共有多少种，共有多少种选法？选法？电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程112022-11-282022-11-28例例2.2.4 2.2.4 解解（1 1）根据）根据乘法原理乘法原理，可能的选法种数为，可能的选法种数为6 65 54=4=120120；（2 2）法一法一 根据题意，确定职位可分为根据题意，确定职位可分为3 3个步骤：个步骤：确定主席有确定主席有2 2种选择；主席选定后，秘书有种选择；主席选定后，秘书有5 5个人选；个人选；主席和秘书都选定后，出纳有主席和秘书都选定后，出纳有4 4个人选。根据个人选。根据乘法乘法原理原理，可能的选法种数为，可能的选法种数为2 25 54=404=40；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程122022-11-282022-11-28例例2.2.4 2.2.4 解解(续续)法二法二 若若AliceAlice被选为主席，共有被选为主席，共有5 54=204=20种方法确定其种方法确定其他职位；若他职位；若BenBen为主席，同样有为主席，同样有2020种方法确定其他种方法确定其他职位。由于两种选法得到的集合不相交，所以根据职位。由于两种选法得到的集合不相交，所以根据加法原理加法原理，共有，共有202020=4020=40种选法；种选法；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程132022-11-282022-11-28例例2.2.4 2.2.4 解解(续续)(3)(3)法一法一 将确定职位分为将确定职位分为3 3步：步：确定确定EgbertEgbert的职位的职位,有有3 3种方法；种方法；确定余下的较高职位人选确定余下的较高职位人选,有有5 5个人选；个人选；确定最后一个职位的人选确定最后一个职位的人选,有有4 4个个人选。根据人选。根据乘法原理乘法原理，共有，共有3 35 54=604=60种选种选法；法；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程142022-11-282022-11-28例例2.2.4 2.2.4 解解(续续)法二法二 根据根据(1)(1)的结论，的结论，如果如果EgbertEgbert为主席为主席，有，有2020种方法确定余下的职位；种方法确定余下的职位；若若EgbertEgbert为秘书，为秘书，有有2020种种方法确定余下的职位；方法确定余下的职位；若若EgbertEgbert为出纳员为出纳员，也有，也有2020种方法确定余下的职位。由于三种选法得到的集合种方法确定余下的职位。由于三种选法得到的集合不相交，根据不相交，根据加法原理加法原理，共有，共有2020202020=6020=60种选法；种选法；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程152022-11-282022-11-28例例2.2.4 2.2.4 解解(续续)（4 4）将给）将给DolphDolph、FranciscoFrancisco和另一个人指定职位和另一个人指定职位分为分为3 3步：步：给给DolphDolph指定职位，指定职位，有有3 3个职位可选；个职位可选；给给FranciscoFrancisco指定职位，指定职位，有有2 2个职位可选；个职位可选；确定最后一个职位的人选确定最后一个职位的人选，有，有4 4个人选。个人选。根据根据乘法原理乘法原理，共有，共有3 32 24=244=24种选法。种选法。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程162022-11-282022-11-282.3 2.3 排列与组合排列与组合 Zeke Zeke、YungYung、XenoXeno和和WilmaWilma四个候选人竞选同一四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次序打印在选票上。响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？会有多少种不同的选票呢？从某个集合中有序的选取若干个元素的问题，称为从某个集合中有序的选取若干个元素的问题，称为排列问题排列问题。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程172022-11-282022-11-282.3.1 2.3.1 排列问题排列问题定义定义2.3.12.3.1 从含从含n n个不同元素个不同元素的集合的集合S S中中有序有序选取选取的的r r个元素叫做个元素叫做S S的一个的一个，不同的排列总数，不同的排列总数记为记为P(n,r)P(n,r)。如果。如果r=nr=n，则称这个排列为，则称这个排列为S S的一的一个个，简称为，简称为S S的排列。的排列。显然显然，电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程182022-11-282022-11-28例例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个排列为个排列为AB,AC,BA,BC,CB,CAAB,AC,BA,BC,CB,CA。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程192022-11-282022-11-28定理定理2.3.12.3.1对满足对满足rnrn的正整数的正整数n n和和r r有有P(n,r)n(n1)(n(r1)第r位第第r-1r-1位位第第3 3位位第第2 2位位第第1 1位位nn-1n-2 n-(r-2)图2.3.1n-(r-1)n-(r-1)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程202022-11-282022-11-28推论推论2.3.22.3.2n n个不同元素的排列共有个不同元素的排列共有n n！种，其中！种，其中 n!n(n1)2 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程212022-11-282022-11-28例例2.3.22.3.2 A,B,C,D,E,F A,B,C,D,E,F组成的排列中，组成的排列中，（1 1）有多少含有）有多少含有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 F看成一个整体看成一个整体，与，与A,BA,B和和C C共共4 4个元个元素构造出素构造出A,B,C,D,E,FA,B,C,D,E,F的全排列，有的全排列，有4 4！种排列。！种排列。又根据乘法原理，满足条件的排列总数有又根据乘法原理，满足条件的排列总数有3 3！4 4！=144=144。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程222022-11-282022-11-28例例2.3.32.3.36 6个人围坐在圆桌上，有多少种不同的坐法？通过个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。转圈得到的坐法视为同一种坐法。解解 6 6个人围坐在圆桌上，个人围坐在圆桌上，有有120120种不同的坐法。种不同的坐法。图图2.3.2AEFBDC电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程232022-11-282022-11-28定理定理2.3.32.3.3含含n n个不同元素的集合的个不同元素的集合的环形环形r-r-排列数排列数P Pc c(n,r(n,r)是是 。(2.3.3)(2.3.3)cP(n,r)n!P(n,r)=rr(nr)!电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程242022-11-282022-11-28例例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个男孩形成的个男孩形成的1111个空格中的插入方法个空格中的插入方法数为数为P(11,5)P(11,5)。根据乘法原理，。根据乘法原理，1010个男孩和个男孩和5 5个女孩个女孩站成一排，没有两个女孩相邻的排列数为：站成一排，没有两个女孩相邻的排列数为：10!10!P(11,5)=P(11,5)=（10!10!11!)/6!11!)/6!。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程252022-11-282022-11-28例例2.3.4 2.3.4 解（续）解（续）（2 2）根据定理根据定理2.3.32.3.3，1010个男孩站成一个圆圈的个男孩站成一个圆圈的环排列数为环排列数为9 9！，！，5 5个女孩插入到个女孩插入到1010男孩形成的男孩形成的1010个个空中的插入方法数为空中的插入方法数为P(10,5)P(10,5)。根据乘法原理，。根据乘法原理，1010个男孩和个男孩和5 5个女孩站成一个圆圈，没有两个女孩相个女孩站成一个圆圈，没有两个女孩相邻的排列法为：邻的排列法为：电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程262022-11-282022-11-282.3.2 2.3.2 组合问题组合问题定义定义2.3.22.3.2 从含有从含有n n个不同元素的集合个不同元素的集合S S中无序选中无序选取的取的r r个元素叫做个元素叫做S S的一个的一个r-r-组合组合，不同的组合总，不同的组合总数记为数记为C(n,r)C(n,r)。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程272022-11-282022-11-28定理定理2.3.42.3.4对满足对满足0 r n0m)m)个鸽笼，则个鸽笼，则存在一个存在一个鸽鸽笼笼至少住至少住进进 +1 +1只鸽子。这里，只鸽子。这里，表示小于表示小于等于等于x x的最大整数。的最大整数。mn1x 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程492022-11-282022-11-28例例2.4.62.4.6如果一个图书馆里如果一个图书馆里3030本离散数学书共有本离散数学书共有1200312003页，页，那么必然有一本离散数学书至少有那么必然有一本离散数学书至少有401401页。页。证明证明 设页是鸽子，离散数学书是鸽笼，把每页分设页是鸽子，离散数学书是鸽笼，把每页分配到它所出现的离散数学书中，根据定理配到它所出现的离散数学书中，根据定理2.4.52.4.5，则存在一个鸽笼至少住进则存在一个鸽笼至少住进即结论得证。即结论得证。401130/)112003(电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程502022-11-282022-11-282.52.5 离散概率简介离散概率简介概率概率(Probability)(Probability)是是1717世纪为分析博弈游戏而发世纪为分析博弈游戏而发展起来的学科，最初计算概率仅有计数一种方法。展起来的学科，最初计算概率仅有计数一种方法。本节主要介绍离散概率的基本概率、基本性质和概本节主要介绍离散概率的基本概率、基本性质和概率计算的简单例子。率计算的简单例子。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程512022-11-282022-11-282.5.1 2.5.1 基本概念基本概念问题问题：掷出一个各面同性的骰子，求掷出偶数的概掷出一个各面同性的骰子，求掷出偶数的概率。率。其中其中“各面同性各面同性”是指当骰子掷出时，各个面是指当骰子掷出时，各个面出现的机会均等。出现的机会均等。定义定义2.5.12.5.1 能生成结果的过程称为能生成结果的过程称为实验实验(experiment)(experiment)；实验的结果或结果的组合称为实验的结果或结果的组合称为事件事件(event)(event)，包含所有可能结果的事件称为包含所有可能结果的事件称为样本空间样本空间(sample(sample space)space)。假如骰子的六个面分别标记为假如骰子的六个面分别标记为1,2,3,4,5,61,2,3,4,5,6，当掷出一个骰子时，一定能掷出当掷出一个骰子时，一定能掷出6 6种结果中的一种，种结果中的一种，我们称我们称掷出骰子的过程为掷出骰子的过程为，掷出的结果掷出的结果(假如假如掷出掷出2)2)或或结果的组合结果的组合(假如掷出两个骰子，一个掷假如掷出两个骰子，一个掷出出1 1，一个掷出，一个掷出3)3)称为称为，当掷出一个骰子时得当掷出一个骰子时得到的到的6 6种可能种可能1,2,3,4,5,61,2,3,4,5,6称为称为。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程522022-11-282022-11-28例例2.5.12.5.1请举例说明下列实验可能发生的事件，并列出其样请举例说明下列实验可能发生的事件，并列出其样本空间。本空间。（1 1）掷出一个六个面的骰子；）掷出一个六个面的骰子；（2 2）从）从10001000个微处理器中随机抽取个微处理器中随机抽取5 5个；个；（3 3）在北京人民医院选取一个婴儿。）在北京人民医院选取一个婴儿。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程532022-11-282022-11-28例例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,5,6；（2 2）从）从10001000个微处理器中选取个微处理器中选取5 5个的所有组合；个的所有组合；（3 3）北京人民医院的所有婴儿。）北京人民医院的所有婴儿。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程542022-11-282022-11-28定义定义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的基数。的基数。EP(E)S电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程552022-11-282022-11-28例例2.5.22.5.2掷出一个各面同性的骰子，求掷出偶数的概率。掷出一个各面同性的骰子，求掷出偶数的概率。解解 设掷出偶数这个事件为设掷出偶数这个事件为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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程562022-11-282022-11-28例例2.5.32.5.3掷出两个各面同性的骰子，求点数之和为掷出两个各面同性的骰子，求点数之和为1010的概率。的概率。解解 设点数之和为设点数之和为1010这个事件为这个事件为E E，样本空间为，样本空间为S S，则根据题意则根据题意|E|=3,|S|=36|E|=3,|S|=36。代入式。代入式(2.5.1)(2.5.1)，得得P(E)=3/36=1/12 P(E)=3/36=1/12。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程572022-11-282022-11-28例例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)，而得大奖的组合只有一种，即，而得大奖的组合只有一种，即|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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程582022-11-282022-11-282.5.2 2.5.2 离散概率函数离散概率函数定义定义2.5.32.5.3 如果函数如果函数P P将样本空间将样本空间S S的每一个结果的每一个结果x x映射为实数映射为实数P(xP(x)，且对任意的，且对任意的xSxS，满足，满足（1 1）0P(x)10P(x)1；（2 2）。则称函数则称函数P P是概率函数是概率函数。x SP(x)1说明说明 条件条件(1)(1)保证一个结果的概率为非负数且不超过保证一个结果的概率为非负数且不超过1 1；条件条件(2)(2)保证所有结果的概率之和为保证所有结果的概率之和为1 1，即进行实验，即进行实验后，必出现某个结果。后，必出现某个结果。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程592022-11-282022-11-28例例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)=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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程602022-11-282022-11-28概率函数概率函数定义定义2.5.42.5.4 设设E E是一个事件，是一个事件，E E的概率函数的概率函数P(E)P(E)定定义为义为 。在例在例2.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)x EP(E)P(x)P(E)P E1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程612022-11-282022-11-28例例2.2.6 2.2.6 生日问题生日问题n n个人中，个人中，求至少有两个人生日相同求至少有两个人生日相同(同月同日不计同月同日不计年年)的概率。的概率。假定出生在某天的概率均等，忽略假定出生在某天的概率均等，忽略2 2月月2929日。日。解解 设设E E表示表示“至少两个人生日相同至少两个人生日相同”，则，则 表示表示“没有两个人生日相同没有两个人生日相同”，则，则 。从而从而 。n365364(365n1)PE365n365 364(365n1)P(E)1365事实上，事实上，随着天数随着天数n n的增加，至少两个人的增加，至少两个人生日相同的概率也随着增加生日相同的概率也随着增加，当，当n23n23时，时，至少有两个人生日相同的概率大于至少有两个人生日相同的概率大于1/21/2。E电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程622022-11-282022-11-28两个事件并的概率两个事件并的概率定理定理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为不相交的事件，则有下为不相交的事件，则有下面的推论。面的推论。推论推论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)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程632022-11-282022-11-28例例2.5.72.5.7掷出两个各面同性的骰子，得到掷出两个各面同性的骰子，得到“一对一对”(两个骰两个骰子点数相同子点数相同)或点数和为或点数和为6 6的概率是多少？的概率是多少？解解 设设E E1 1表示事件表示事件“一对一对”，E E2 2表示事件表示事件“点数和点数和为为6 6”，则样本空间大小是，则样本空间大小是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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程642022-11-282022-11-28例例2.5.7 2.5.7 解（续）解（续）从而从而 P(E P(E1 1)=1/6)=1/6 ,P(E,P(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 。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程652022-11-282022-11-282.62.6 递归关系递归关系递归关系递归关系可用于解决一些特定的计数问题。可用于解决一些特定的计数问题。递归关系是序列中递归关系是序列中第第n n个元素与它相邻前若干个元个元素与它相邻前若干个元素之间的关系素之间的关系。例如例如第一个数是第一个数是5 5；2 2、将前一项加、将前一项加3 3得到后一项。得到后一项。5,8,11,14,5,8,11,14,递归关系递归关系电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程662022-11-282022-11-28定义定义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 relation)(recurrence relation)。显示地给出序。显示地给出序列列a a0 0,a,a1 1,a,a2 2,的有限项的值，称为的有限项的值，称为初始条件初始条件(initial condition)(initial condition)。显然，递归关系和确定的初始条件一起，才能确定显然，递归关系和确定的初始条件一起，才能确定一个序列。一个序列。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程672022-11-282022-11-28例例2.6.12.6.1某人投资某人投资10001000元，每年可收益元，每年可收益1212。A An n表示他在第表示他在第n n年末的总资产年末的总资产。求出定义序列。求出定义序列AAn n 的递归关系和的递归关系和初始条件。初始条件。解解 序列序列AAn n 的的递归关系和初始条件递归关系和初始条件分别为：分别为：A An n=A An n-1-10.120.12A An n -1-1=1.12 A=1.12 An n -1-1,n1,n1,A A0 0=1000=1000电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程682022-11-282022-11-28例例2.6.22.6.2S Sn n表示表示不含子串不含子串“111111”的的n n位字符串的个数。求出位字符串的个数。求出序列序列 S Sn n 的递归关系和初始条件。的递归关系和初始条件。解解 序列序列 S Sn n 的的递归关系和初始条件递归关系和初始条件分别为：分别为：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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程692022-11-282022-11-282.7 2.7 计数问题的应用计数问题的应用例例2.7.1 72.7.1 7个科学工作者从事一项机密的技术研究，个科学工作者从事一项机密的技术研究，他们的工作室装有电子锁，每位科学工作者都有打开他们的工作室装有电子锁，每位科学工作者都有打开电子锁用的电子锁用的“钥匙钥匙”。为了安全起见，。为了安全起见，必须有必须有4 4位在场位在场时才能打开大门时才能打开大门。试问该电子锁。试问该电子锁至少应具备多少个特至少应具备多少个特征征？每位科学工作者的？每位科学工作者的“钥匙钥匙”至少应有多少种特征？至少应有多少种特征？解解 为了使任意为了使任意3 3个人在场时至少缺少一个特征而打不个人在场时至少缺少一个特征而打不开门，该电子锁开门，该电子锁至少至少应具备应具备C(7,3)=35C(7,3)=35种特征；每个科种特征；每个科学工作者的学工作者的“钥匙钥匙”至少至少要有要有C(6,3)=20C(6,3)=20种特征。种特征。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程702022-11-282022-11-28例例2.7.22.7.2某一制造铁盘的工厂，由于设备和技术的原因只能某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制在将生产盘子的重量控制在a a克到（克到（a+0.1a+0.1）克之间）克之间。现需要制成重量相差不超过现需要制成重量相差不超过0.0050.005克的两铁盘来配克的两铁盘来配制一架天平，问该工厂制一架天平，问该工厂至少要生产多少铁盘至少要生产多少铁盘才能得才能得到一对符合要求的铁盘。到一对符合要求的铁盘。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程712022-11-282022-11-28例例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.01a+0.01克到克到a+0.015a+0.015克的又为一类，克的又为一类，.，最后，最后，a+0.095a+0.095克到克到a+0.1a+0.1克为一类，共计克为一类，共计2020类，类，由由鸽笼原理鸽笼原理知，若该工厂生产知，若该工厂生产2121个铁盘，那么就能个铁盘，那么就能得知有两个铁盘属于同一类，因而它们之间的重量得知有两个铁盘属于同一类，因而它们之间的重量差将不超过差将不超过0.0050.005克。克。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程722022-11-282022-11-28例例2.7.3 Fibonacci2.7.3 Fibonacci数列数列假定一对新出生的兔子一个月又成熟，并且再过一假定一对新出生的兔子一个月又成熟，并且再过一个月开始生出一对小兔子。按此规律，在没有兔子个月开始生出一对小兔子。按此规律，在没有兔子死亡的情形下，一对初生的兔子，一年可以繁殖成死亡的情形下，一对初生的兔子，一年可以繁殖成多少队兔子？多少队兔子？解解 因为因为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+55=143。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程732022-11-282022-11-28例例2.7.42.7.4计算下面算法中基本操作的次数算法计算下面算法中基本操作的次数算法 输入输入：s s1 1,s,s2 2,s sn n和序列的长度。和序列的长度。输出输出：s s1 1,s,s2 2,s sn n，按非递减顺序排列。，按非递减顺序排列。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程742022-11-282022-11-28例例2.7.4 2.7.4（续）（续）1.1.selection_sorts(s,nselection_sorts(s,n)2./2./基本情况基本情况3.if(n=1)4.return3.if(n=1)4.return5./5./找到最大的元素找到最大的元素6.6.max_indexmax_index=1/=1/初始时认为初始时认为s s1 1是最大的元素是最大的元素7.for i=2 to n7.for i=2 to n8.if(8.if(s si i smax_indexsmax_index)/)/比较得到较大的元素，并更新最比较得到较大的元素，并更新最大元素大元素9.9.max_indexmax_index=i 10./=i 10./将最大的元素移至序列尾将最大的元素移至序列尾11.11.swap(sswap(sn n,smax_indexsmax_index)12.12.selection_sort(sselection_sort(s,n-1),n-1)13.13.电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程752022-11-282022-11-28例例2.7.4 2.7.4 解解设计算设计算n n个数排序的比较执行次数为个数排序的比较执行次数为b bn n，则该算法，则该算法中的比较语句的执行次数的中的比较语句的执行次数的递归关系递归关系为：为：b bn n=b=bn-1 n-1+n+n 1 1，其其初始条件初始条件为：为：b b1 1=0=0。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程762022-11-282022-11-28例例2.7.4 2.7.4 解（续）解（续）用用迭代法迭代法求解该递归关系：求解该递归关系：b bn n=b=bn-1n-1+n+n1=b1=bn-2n-2+n+n2+n-1 2+n-1 =b =bn-3n-3+n+n3+n3+n2+n2+n1 1=b=b1 1+1+2+1+2+n+n3+n3+n2+n2+n1 1=0+1+2+=0+1+2+n+n 3+n 3+n2+n2+n1 1=n(n-1)/2=n(n-1)/2。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程772022-11-282022-11-282.8 2.8 本章总结本章总结 1 1、乘法原理和加法原理的基本含义；、乘法原理和加法原理的基本含义；2 2、r-r-排列，全排列，环形排列，全排列，环形r r排列，环排列，排列，环排列，r-r-组合组合的基本概念，它们之间关系和相应的计算公式；的基本概念，它们之间关系和相应的计算公式；3 3、容斥原理和鸽笼原理的基本概念及正确使用；、容斥原理和鸽笼原理的基本概念及正确使用；4 4、实验、事件、样本空间、概率函数的基本概念，、实验、事件、样本空间、概率函数的基本概念，离散概率的计算；离散概率的计算；5 5、递归关系、初始条件的概念、递归关系的建立、递归关系、初始条件的概念、递归关系的建立和求解。和求解。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程782022-11-282022-11-28习题类型习题类型（1 1）基本概念题：基本概念题：涉及离散概率的基本概念；涉及离散概率的基本概念；（2 2）计算题：）计算题：涉及排列数与组合数的计算，利用涉及排列数与组合数的计算，利用容斥原理的计算，离散概率的计算和递归关系的建容斥原理的计算，离散概率的计算和递归关系的建立与求解；立与求解；（3 3）证明题：证明题：涉及对鸽笼原理的应用。涉及对鸽笼原理的应用。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程792022-11-282022-11-28习题习题第第44-4544-45页页2.2.6.8.11.14.19.20.6.8.11.14.19.20.21.24.26.27.21.24.26.27.电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程http:/202.115.21.136:8080/lssxhttp:/202.115.21.136:8080/lssx/