离散数学教案.ppt

,电子科技大学离散数学课程组国家精品课程,离 散 数 学,电子科技大学,计算机科学与工程学院示 范 性 软 件 学 院,2023年10月17日星期二,2023/10/17,第一篇 预备知识,第2章 计数问题,2023/10/17,2.0 内容提要,2023/10/17,2.1 本章学习要求,2023/10/17,表,2023/10/17,2.2.1 乘法原理,如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：,2023/10/17,例2.2.2 Melissa病毒,1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？,解 根据Melissa病毒的扩散原理，经过四次转发，共有50505050+505050+5050+50+1=6377551个接收者。,2023/10/17,例,在一幅数字图像中，若每个像素点用8位进行编码，问每个点有多少种不同的取值。分析 用8位进行编码可分为8个步骤：选择第一位，选择第二位，选择第八位。每一个位有两种选择，故根据乘法原理，8位编码共有22222222=28=256种取值。解 每个点有256(=28)种不同的取值。,2023/10/17,2.2.2 加法原理,假定X1,X2,Xt均为集合，第i个集合Xi有ni个元素。如X1,X2,Xt为两两不相交的集合，则可以从X1,X2,Xt中选出的元素总数为：n1+n2+nt。,即集合X1X2Xt含有n1+n2+nt个元素。,2023/10/17,例,由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选出一个主席、一个秘书和一个出纳员。（1）共有多少种选法？（2）若主席必须从Alice和Ben种选出，共有多少种选法？（3）若Egbert必须有职位，共有多少种选法？（4）若Dolph和Francisco都有职位，共有多少种选法？,2023/10/17,例2.2.4 解,（1）根据乘法原理，可能的选法种数为654=120；（2）法一 根据题意，确定职位可分为3个步骤：确定主席有2种选择；主席选定后，秘书有5个人选；主席和秘书都选定后，出纳有4个人选。根据乘法原理，可能的选法种数为254=40；,2023/10/17,例2.2.4 解(续),法二 若Alice被选为主席，共有54=20种方法确定其他职位；若Ben为主席，同样有20种方法确定其他职位。由于两种选法得到的集合不相交，所以根据加法原理，共有2020=40种选法；,2023/10/17,例2.2.4 解(续),(3)法一 将确定职位分为3步：确定Egbert的职位,有3种方法；确定余下的较高职位人选,有5个人选；确定最后一个职位的人选,有4个人选。根据乘法原理，共有354=60种选法；,2023/10/17,例2.2.4 解(续),法二 根据(1)的结论，如果Egbert为主席，有20种方法确定余下的职位；若Egbert为秘书，有20种方法确定余下的职位；若Egbert为出纳员，也有20种方法确定余下的职位。由于三种选法得到的集合不相交，根据加法原理，共有202020=60种选法；,2023/10/17,例2.2.4 解(续),（4）将给Dolph、Francisco和另一个人指定职位分为3步：给Dolph指定职位，有3个职位可选；给Francisco指定职位，有2个职位可选；确定最后一个职位的人选，有4个人选。根据乘法原理，共有324=24种选法。,2023/10/17,2.3 排列与组合,Zeke、Yung、Xeno和Wilma四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？从某个集合中有序的选取若干个元素的问题，称为排列问题。,2023/10/17,2.3.1 排列问题,定义 从含n个不同元素的集合S中有序选取的r个元素叫做S的一个r-排列，不同的排列总数记为P(n,r)。如果r=n，则称这个排列为S的一个全排列，简称为S的排列。显然，当rn时，P(n,r)=0。,2023/10/17,例,从含3个不同元素的集合S中有序选取2个元素的排列总数。解 从含3个元素的不同集合S中有序选取2个元素的排列总数为6种。如果将这3个元素记为A、B和C，则6个排列为AB,AC,BA,BC,CB,CA。,2023/10/17,定理,对满足rn的正整数n和r有,2023/10/17,推论,n个不同元素的排列共有n！种，其中,2023/10/17,例,A,B,C,D,E,F组成的排列中，（1）有多少含有DEF的子串？（2）三个字母D、E和F相连的有多少种？解(1)将DEF看成一个对象，根据推论，满足条件的排列为A,B,C,DEF的全排列，共有4！=24种；（2）根据题意，满足该条件的排列分为两步：第一步确定D,E和F三个字母的全排列，有3！种排列，第二步将已排序的D,E和F看成一个整体，与A,B和C共4个元素构造出A,B,C,D,E,F的全排列，有4！种排列。又根据乘法原理，满足条件的排列总数有3！4！=144。,2023/10/17,例,6个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。解 6个人围坐在圆桌上，有120种不同的坐法。,n个人围坐圆桌上，有(n-1)！种不同的坐法，我们称这种排列为环排列，从n个人中选出r个人为圆桌而坐称为环形r-排列。,2023/10/17,定理,含n个不同元素的集合的环形r-排列数Pc(n,r)是。(2.3.3),2023/10/17,例,求满足下列条件的排列数。(1)10个男孩和5个女孩站成一排，无两个女孩相邻。(2)10个男孩和5个女孩站成一圆圈，无两个女孩相邻.解(1)根据推论，10个男孩的全排列为10!，5个女孩插入到10个男孩形成的11个空格中的插入方法数为P(11,5)。根据乘法原理，10个男孩和5个女孩站成一排，没有两个女孩相邻的排列数为：10!P(11,5)=（10!11!)/6!。,2023/10/17,例2.3.4 解（续）,（2）根据定理，10个男孩站成一个圆圈的环排列数为9！，5个女孩插入到10男孩形成的10个空中的插入方法数为P(10,5)。根据乘法原理，10个男孩和5个女孩站成一个圆圈，没有两个女孩相邻的排列法为：9!P(10,5)=（9!10!)/5!。,2023/10/17,2.3.2 组合问题,定义 从含有n个不同元素的集合S中无序选取的r个元素叫做S的一个r-组合，不同的组合总数记为C(n,r)。当nr=0时，规定C(n,r)=1。显然，当rn时，C(n,r)=0。,2023/10/17,定理,对满足0 r n的正整数n和r有，即 证明 先从n个不同元素中选出r个元素，有C(n,r)种选法，再把每一种选法选出的r个元素做全排列，有r！种排法。,2023/10/17,定理（续）,根据乘法原理，n个元素的r排列数为：即,2023/10/17,例,一副52张的扑克牌含有4种花色：梅花、方片、红桃和黑桃；各有13种点数，分别为A,210,J,Q,K。试求满足下列条件的组合数。（1）手中持有5张牌称为一手牌，一手牌共有多少种可能的组合？（2）一手牌中的5张都是同一花色，共有多少种可能的组合？（3）一手牌中有3张牌点数相同，另外两张牌点数相同，共有多少种可能的组合？,2023/10/17,例2.3.5 解,（1）一手牌可能的组合数等于从52张牌中选出5张的可能组合数，有C(52,5)种可能的组合；（2）选同一花色的5张牌分两步进行：一选花色，有C(4,1)种，二在选定的花色中选5张牌，有C(13,5)种。据乘法原理，有C(4,1)C(13,5)种；,2023/10/17,例2.3.5 解（续）,（3）该组合问题需四步完成：一选第一个点数，有C(13,1)种；二选第二个点数，有C(12,1)种：三选第一点数的3张牌，有C(4,3)种；四选第二点数的2张牌，有C(4,2)种。根据乘法原理，共有C(13,1)C(12,1)C(4,3)C(4,2)=131246=3744种选法。,2023/10/17,2.4 容斥原理与鸽笼原理,容斥原理是研究若干有限集合交与并的计数问题鸽笼原理则是研究某些特定对象的存在性问题。,2023/10/17,2.4.1 容斥原理,定义 所谓容斥，是指我们计算某类物体的数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补偿。这种原理称为容斥原理(The Principle of Inclusion-exclusion)，又称为包含排斥原理。,2023/10/17,定理,设A和B是任意有限集合，有|AB|=|A|B|AB|。分析 由图容易看出，AB=(A-B)(AB)(B-A)，A=(A-B)(AB)，B=(AB)(B-A)。,AB,A-B,B-A,推论2.4.2设U为全集，A和B是任意有限集合，则,2023/10/17,例,对所给的集合验证定理。（1）A=1,2,3,4，B=2,3,5,6,8；（2）A=1,2,3,4，B=5,6,7,8。根据定理，需先计算AB和AB，再计算|A|,|B|和|AB|，然后代入公式(2.4.1)两端，验证等式即可。,分析,解(1)AB=1,2,3,4,5,6,8，AB=2,3|AB|=7,|AB|=2。又|A|=4,|B|=5，|A|B|AB|=452=7=|AB|即定理成立；(2)略。,2023/10/17,三个集合的情形,定理 设A，B和C是任意三个有限集合，有(2.4.3)推论设U为全集，A，B和C是任意有限集合，则(2.4.4),2023/10/17,例,调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人对三种课程都选修。问（1）调查中三种课程都不选的学生有多少？（2）调查中只选修计算机科学课程的学生有多少？,2023/10/17,例2.4.2 解,设A、B、C分别表示选修数学课程，计算机课程和商贸课程的人构成的集合，则三种课程都不选的学生集合为，只选修计算机科学课程学生的集合为。,2023/10/17,例2.4.2 解（续）,（1）|U|=260,|A|=64,|B|=94,|C|=58,|AC|=28,|AB|=26,|BC|=22,|AB C|=14，所以利用容斥原理得=106;（2）,2023/10/17,容斥原理的推广,定理 设A1,A2,An是任意n个有限集合，则推论 设U为全集，A1,A2,An是任意n个有限集合，则,2023/10/17,例,对24名科技人员进行掌握外语情况的调查，其统计资料如下：会英、日、德、法语的人数分别为13、5、10和9。其中同时会英语、日语的人数为2；同时会英语和德语、同时会英语和法语、同时会德语和法语两种语言的人数均为4；会日语的人既不会法语也不会德语。试求(1)只会一种语言的人数各为多少？(2)同时会英、德、法语的人数为多少？,2023/10/17,例2.4.3 解,设A、B、C、D分别为会英、日、德、法语的人的集合，由已知条件可知：|A|13，|B|5，|C|10，|D|9，|AB|2，|AC|AD|CD|4，|BC|BD|0,|ABC|ABD|BCD|0，|ABCD|0，|ABCD|24，,2023/10/17,例2.4.3 解（续）,利用容斥原理，并代入已知条件得 24135109244400 000|ACD|0。得:|ACD|1，即同时会英、德、法语的只有1人。,2023/10/17,例2.4.3 解（续）,设只会英、日、德、法语的人数分别为x1,x2,x3,x4，则 x1|A|(BCD)A|A|(BA)(CA)(DA)|对BA、CA、DA应用容斥原理，得|(BA)(CA)(DA)|24400109故，x113-94。类似地可求出：x23，x33，x42。,2023/10/17,2.4.2 鸽笼原理,鸽笼原理（Pigeonhole Principle）又称为抽屉原理、鸽舍原理，是指如下定理。定理2.4.7(鸽笼原理)若有n+1只鸽子住进n个鸽笼，则有一个鸽笼至少住进2只鸽子。证明(反证法)假设每个鸽笼至多住进1只鸽子，则n个鸽笼至多住进n只鸽子，这与有n+1只鸽子矛盾。故存在一个鸽笼至少住进2只鸽子。,注意：（1）鸽笼原理仅提供了存在性证明；（2）使用鸽笼原理，必须能够正确识别鸽子(对象)和鸽巢(某类要求的特征)，并且能够计算出鸽子数和鸽巢数。,2023/10/17,例,抽屉里有3双手套，问从中至少取多少只，才能保证配成一双？答：4只。,2023/10/17,例,设1到10中任意选出六个数，那么其中有两个数的和是11。证明(1)构造5个鸽笼：A1=1,10，A2=2,9，A3=3,8，A4=4,7，A5=5,6(2)选出的6个数为鸽子.根据鸽笼原理，所选出的6个数中一定有两个数属于同一个集合，这两个数的和为11。,2023/10/17,定理,若有n只鸽子住进m(nm)个鸽笼，则存在一个鸽笼至少住进+1只鸽子。这里，表示小于等于x的最大整数。,2023/10/17,例,如果一个图书馆里30本离散数学书共有12003页，那么必然有一本离散数学书至少有401页。证明 设页是鸽子，离散数学书是鸽笼，把每页分配到它所出现的离散数学书中，根据定理，则存在一个鸽笼至少住进即结论得证。,2023/10/17,2.5 离散概率简介,概率(Probability)是17世纪为分析博弈游戏而发展起来的学科，最初计算概率仅有计数一种方法。本节主要介绍离散概率的基本概率、基本性质和概率计算的简单例子。,2023/10/17,2.5.1 基本概念,问题：掷出一个各面同性的骰子，求掷出偶数的概率。其中“各面同性”是指当骰子掷出时，各个面出现的机会均等。定义 能生成结果的过程称为实验(experiment)；实验的结果或结果的组合称为事件(event)，包含所有可能结果的事件称为样本空间(sample space)。,假如骰子的六个面分别标记为1,2,3,4,5,6，当掷出一个骰子时，一定能掷出6种结果中的一种，我们称掷出骰子的过程为实验，掷出的结果(假如掷出2)或结果的组合(假如掷出两个骰子，一个掷出1，一个掷出3)称为事件，当掷出一个骰子时得到的6种可能1,2,3,4,5,6称为样本空间。,2023/10/17,例,请举例说明下列实验可能发生的事件，并列出其样本空间。（1）掷出一个六个面的骰子；（2）从1000个微处理器中随机抽取5个；（3）在北京人民医院选取一个婴儿。,2023/10/17,例2.5.1 解,可能发生的事件举例如下：（1）掷出一个六个面的骰子，得到的点数是4；（2）从1000个微处理器中随机抽取5个，没有发现次品；（3）在北京人民医院选取了一个女婴。各实验的样本空间为：（1）1,2,3,4,5,6；（2）从1000个微处理器中选取5个的所有组合；（3）北京人民医院的所有婴儿。,2023/10/17,定义,有限样本空间S中的事件E的概率P(E)定义为：。(2.5.1)其中|E|,|S|分别表示集合E和S的基数。,2023/10/17,例,掷出一个各面同性的骰子，求掷出偶数的概率。解 设掷出偶数这个事件为E，样本空间为S，则根据题意|E|=3,|S|=6。代入式(2.5.1)，得P(E)=3/6=1/2。,2023/10/17,例,掷出两个各面同性的骰子，求点数之和为10的概率。解 设点数之和为10这个事件为E，样本空间为S，则根据题意|E|=3,|S|=36。代入式(2.5.1)，得P(E)=3/36=1/12。,2023/10/17,例,在福利彩票中，若彩民从152个数中选取的6个数与随机生成的中奖数字相同(不计顺序)，则可以赢得大奖。求一张彩票赢得大奖的概率。解 从52个数字中选取6个共有C(52,6)种选法，即|S|=C(52,6)，而得大奖的组合只有一种，即|E|=1，根据式(2.5.1)，得：P(E)=1/C(52,6)=0.00000004。,2023/10/17,2.5.2 离散概率函数,定义 如果函数P将样本空间S的每一个结果x映射为实数P(x)，且对任意的xS，满足（1）0P(x)1；（2）。则称函数P是概率函数。,说明 条件(1)保证一个结果的概率为非负数且不超过1；条件(2)保证所有结果的概率之和为1，即进行实验后，必出现某个结果。,2023/10/17,例,一个一面较重的骰子，26以相同的机会出现，1出现的机会是其他数字的3倍。试求出16的概率函数值。解 设P(2)=P(3)=P(4)=P(5)=P(6)=a，则P(6)=3a。又因为P(1)+P(2)+P(3)+P(4)+P(5)+P(6)=1，所以有5a3a=1，即a=1/8。从而P(2)=P(3)=P(4)=P(5)=P(6)=1/8，P(6)=3/8。,2023/10/17,概率函数,定义 设E是一个事件，E的概率函数P(E)定义为。在例中，出现奇数点的概率则为P(1)+P(3)+P(5)=5/8。定理 设E是一个事件，E的补的概率满足。(2.5.2),2023/10/17,例2.2.6 生日问题,n个人中，求至少有两个人生日相同(同月同日不计年)的概率。假定出生在某天的概率均等，忽略2月29日。解 设E表示“至少两个人生日相同”，则 表示“没有两个人生日相同”，则。从而。,事实上，随着天数n的增加，至少两个人生日相同的概率也随着增加，当n23时，至少有两个人生日相同的概率大于1/2。,2023/10/17,两个事件并的概率,定理 设E1和E2是两个事件，则 P(E1E2)=P(E1)P(E2)P(E1E2)(2.5.3)如果E1E2=，即E1与E2为不相交的事件，则有下面的推论。推论 设E1和E2是两个不相交的事件，则 P(E1E2)=P(E1)P(E2)(2.5.4),2023/10/17,例,掷出两个各面同性的骰子，得到“一对”(两个骰子点数相同)或点数和为6的概率是多少？解 设E1表示事件“一对”，E2表示事件“点数和为6”，则样本空间大小是36，事件E1的种数为6,即(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),事件E2的种数为5，即(1,5),(2,4),(3,3),(4,2),(5,1)。E1E2的种数为1。,2023/10/17,例2.5.7 解（续）,从而 P(E1)=1/6,P(E2)=5/36,P(E1E2)=1/36。根据式(2.5.3)，有 P(E1E2)=1/65/361/36=5/18。即得到“一对”或点数和为6的概率是5/18。,2023/10/17,2.6 递归关系,递归关系可用于解决一些特定的计数问题。递归关系是序列中第n个元素与它相邻前若干个元素之间的关系。例如第一个数是5；2、将前一项加3得到后一项。5,8,11,14,递归关系,2023/10/17,定义,对序列a0,a1,a2,an-1,，用a0,a1,a2,an-1中的某些项表示an的等式称为递归关系(recurrence relation)。显示地给出序列a0,a1,a2,的有限项的值，称为初始条件(initial condition)。显然，递归关系和确定的初始条件一起，才能确定一个序列。,2023/10/17,例,某人投资1000元，每年可收益12。An表示他在第n年末的总资产。求出定义序列An的递归关系和初始条件。解 序列An的递归关系和初始条件分别为：An=An-10.12An-1=1.12 An-1,n1,A0=1000,2023/10/17,例,Sn表示不含子串“111”的n位字符串的个数。求出序列Sn的递归关系和初始条件。解 序列Sn的递归关系和初始条件分别为：Sn=Sn-1Sn-2 Sn-3，n4,S1=2,S2=4,S3=7。,2023/10/17,2.7 计数问题的应用,例2.7.1 7个科学工作者从事一项机密的技术研究，他们的工作室装有电子锁，每位科学工作者都有打开电子锁用的“钥匙”。为了安全起见，必须有4位在场时才能打开大门。试问该电子锁至少应具备多少个特征？每位科学工作者的“钥匙”至少应有多少种特征？解 为了使任意3个人在场时至少缺少一个特征而打不开门，该电子锁至少应具备C(7,3)=35种特征；每个科学工作者的“钥匙”至少要有C(6,3)=20种特征。,2023/10/17,例,某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制在a克到（a+0.1）克之间。现需要制成重量相差不超过0.005克的两铁盘来配制一架天平，问该工厂至少要生产多少铁盘才能得到一对符合要求的铁盘。,2023/10/17,例2.7.2 解,将铁盘按重量分类，所有a克到a+0.005克的分为第一类；a+0.005克到a+0.01克的分为一类；a+0.01克到a+0.015克的又为一类，.，最后，a+0.095克到a+0.1克为一类，共计20类，由鸽笼原理知，若该工厂生产21个铁盘，那么就能得知有两个铁盘属于同一类，因而它们之间的重量差将不超过0.005克。,2023/10/17,例2.7.3 Fibonacci数列,假定一对新出生的兔子一个月又成熟，并且再过一个月开始生出一对小兔子。按此规律，在没有兔子死亡的情形下，一对初生的兔子，一年可以繁殖成多少队兔子？解 因为Fn=Fn-1+Fn-2，所以根据迭代法，有F12=F11+F10=2F10+F9=3F9+2F8=5F8+3F7=8F7+5F6=89F2+55F1=89+55=143。,2023/10/17,例,计算下面算法中基本操作的次数算法 输入：s1,s2,sn和序列的长度。输出：s1,s2,sn，按非递减顺序排列。,2023/10/17,例2.7.4（续）,1.selection_sorts(s,n)2./基本情况3.if(n=1)4.return5./找到最大的元素6.max_index=1/初始时认为s1是最大的元素7.for i=2 to n8.if(sismax_index)/比较得到较大的元素，并更新最大元素9.max_index=i 10./将最大的元素移至序列尾11.swap(sn,smax_index)12.selection_sort(s,n-1)13.,2023/10/17,例2.7.4 解,设计算n个数排序的比较执行次数为bn，则该算法中的比较语句的执行次数的递归关系为：bn=bn-1+n 1，其初始条件为：b1=0。,2023/10/17,例2.7.4 解（续）,用迭代法求解该递归关系：bn=bn-1+n1=bn-2+n2+n-1=bn-3+n3+n2+n1=b1+1+2+n3+n2+n1=0+1+2+n 3+n2+n1=n(n-1)/2。,2023/10/17,2.8 本章总结,1、乘法原理和加法原理的基本含义；2、r-排列，全排列，环形r排列，环排列，r-组合的基本概念，它们之间关系和相应的计算公式；3、容斥原理和鸽笼原理的基本概念及正确使用；4、实验、事件、样本空间、概率函数的基本概念，离散概率的计算；5、递归关系、初始条件的概念、递归关系的建立和求解。,2023/10/17,习题类型,（1）基本概念题：涉及离散概率的基本概念；（2）计算题：涉及排列数与组合数的计算，利用容斥原理的计算，离散概率的计算和递归关系的建立与求解；（3）证明题：涉及对鸽笼原理的应用。,2023/10/17,习题,第44-45页2.6.8.11.14.19.20.21.24.26.27.,Thank You!,http:/202.115.21.136:8080/lssx/,