电子科技大学离散数学课程组国家精品课程

电子科技大学离散数学课程组——国家精品课程离散数学电子科技大学计算机科学与工程学院示范性软件学院2019年8月5日星期一电子科技大学离散数学课程组——国家精品课程67-22019/8/5第2章计数问题计数问题是组合数学研究的主要问题之一。西班牙数学家AbrahambenMeiribnEzra(1092～1167)和法国数学家、哲学家、天文学家LevibenGerson(1288～1344)是排列与组合领域的两位早期研究者。另外，法国数学家BlaisePascal还发明了一种机械计算器，这种计算器非常类似于20世纪40年代在数字电子计算机发明之前使用的一种机械计算器。同时，计数技术在数学和计算机科学中是很重要的，特别是在《数据结构》、《算法分析与设计》等后续课程中有非常重要的应用。电子科技大学离散数学课程组——国家精品课程67-32019/8/52.0内容提要容斥原理与鸽笼原理3离散概率4乘法原理和加法原理1排列与组合2递归关系5电子科技大学离散数学课程组——国家精品课程67-42019/8/51.1本章学习要求重点掌握一般掌握了解11乘法原理和加法原理2排列组合的计算3利用容斥原理计算有限集合的交与并31离散概率2离散概念的计算公式及性质21鸽笼原理2鸽笼原理的简单应用3递归关系4递归关系的建立和计算电子科技大学离散数学课程组——国家精品课程67-52019/8/5表2.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电子科技大学离散数学课程组——国家精品课程67-62019/8/52.2.1乘法原理如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，…，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：12tn×n××n电子科技大学离散数学课程组——国家精品课程67-72019/8/5例2.2.2Melissa病毒1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？解根据Melissa病毒的扩散原理，经过四次转发，共有50×50×50×50+50×50×50+50×50+50+1=6377551个接收者。电子科技大学离散数学课程组——国家精品课程67-82019/8/5例2.2.3在一幅数字图像中，若每个像素点用8位进行编码，问每个点有多少种不同的取值。分析用8位进行编码可分为8个步骤：选择第一位，选择第二位，…，选择第八位。每一个位有两种选择，故根据乘法原理，8位编码共有2×2×2×2×2×2×2×2=28=256种取值。解每个点有256(=28)种不同的取值。电子科技大学离散数学课程组——国家精品课程67-92019/8/52.2.2加法原理假定X1,X2,…,Xt均为集合，第i个集合Xi有ni个元素。如{X1,X2,…,Xt}为两两不相交的集合，则可以从X1,X2,…,Xt中选出的元素总数为：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt个元素。电子科技大学离散数学课程组——国家精品课程67-102019/8/5例2.2.4由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选出一个主席、一个秘书和一个出纳员。（1）共有多少种选法？（2）若主席必须从Alice和Ben种选出，共有多少种选法？（3）若Egbert必须有职位，共有多少种选法？（4）若Dolph和Francisco都有职位，共有多少种选法？电子科技大学离散数学课程组——国家精品课程67-112019/8/5例2.2.4解（1）根据乘法原理，可能的选法种数为6×5×4=120；（2）[法一]根据题意，确定职位可分为3个步骤：确定主席有2种选择；主席选定后，秘书有5个人选；主席和秘书都选定后，出纳有4个人选。根据乘法原理，可能的选法种数为2×5×4=40；[法二]若Alice被选为主席，共有5×4=20种方法确定其他职位；若Ben为主席，同样有20种方法确定其他职位。由于两种选法得到的集合不相交，所以根据加法原理，共有20＋20=40种选法；电子科技大学离散数学课程组——国家精品课程67-122019/8/5例2.2.4解(续)(3)[法一]将确定职位分为3步：确定Egbert的职位,有3种方法；确定余下的较高职位人选,有5个人选；确定最后一个职位的人选,有4个人选。根据乘法原理，共有3×5×4=60种选法；[法二]根据(1)的结论，如果Egbert为主席，有20种方法确定余下的职位；若Egbert为秘书，有20种方法确定余下的职位；若Egbert为出纳员，也有20种方法确定余下的职位。由于三种选法得到的集合不相交，根据加法原理，共有20＋20＋20=60种选法；电子科技大学离散数学课程组——国家精品课程67-132019/8/5例2.2.4解(续)（4）将给Dolph、Francisco和另一个人指定职位分为3步：给Dolph指定职位，有3个职位可选；给Francisco指定职位，有2个职位可选；确定最后一个职位的人选，有4个人选。根据乘法原理，共有3×2×4=24种选法。电子科技大学离散数学课程组——国家精品课程67-142019/8/52.3排列与组合Zeke、Yung、Xeno和Wilma四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？从某个集合中有序的选取若干个元素的问题，称为排列问题。电子科技大学离散数学课程组——国家精品课程67-152019/8/52.3.1排列问题定义2.3.1从含n个不同元素的集合S中有序选取的r个元素叫做S的一个r-排列，不同的排列总数记为P(n,r)。如果r=n，则称这个排列为S的一个全排列，简称为S的排列。显然，当rn时，P(n,r)=0。电子科技大学离散数学课程组——国家精品课程67-162019/8/5例2.3.1从含3个不同元素的集合S中有序选取2个元素的排列总数。解从含3个元素的不同集合S中有序选取2个元素的排列总数为6种。如果将这3个元素记为A、B和C，则6个排列为AB,AC,BA,BC,CB,CA。电子科技大学离散数学课程组——国家精品课程67-172019/8/5定理2.3.1对满足r≤n的正整数n和r有P(n,r)=n×(n-1)(n-(r-1))第r位第r-1位第3位第2位第1位nn-1n-2……n-(r-2)n-(r-1)电子科技大学离散数学课程组——国家精品课程67-182019/8/5推论2.3.2n个不同元素的排列共有n！种，其中n!=n×(n-1)××2×1电子科技大学离散数学课程组——国家精品课程67-192019/8/5例2.3.2A,B,C,D,E,F组成的排列中，（1）有多少含有DEF的子串？（2）三个字母D、E和F相连的有多少种？解(1)将DEF看成一个对象，根据推论2.3.2，满足条件的排列为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。电子科技大学离散数学课程组——国家精品课程67-202019/8/5例2.3.36个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。解6个人围坐在圆桌上，有120种不同的坐法。AEFBDCn个人围坐圆桌上，有(n-1)！种不同的坐法，我们称这种排列为环排列，从n个人中选出r个人为圆桌而坐称为环形r-排列。电子科技大学离散数学课程组——国家精品课程67-212019/8/5定理2.3.3含n个不同元素的集合的环形r-排列数Pc(n,r)是cP(n,r)n!P(n,r)==rr×(n-r)!电子科技大学离散数学课程组——国家精品课程67-222019/8/5例2.3.4求满足下列条件的排列数。(1)10个男孩和5个女孩站成一排，无两个女孩相邻。(2)10个男孩和5个女孩站成一圆圈，无两个女孩相邻.解(1)根据推论2.3.2，10个男孩的全排列为10!，5个女孩插入到10个男孩形成的11个空格中的插入方法数为P(11,5)。根据乘法原理，10个男孩和5个女孩站成一排，没有两个女孩相邻的排列数为：10!×P(11,5)=（10!×11!)/6!。电子科技大学离散数学课程组——国家精品课程67-232019/8/5例2.3.4解（续）（2）根据定理2.3.3，10个男孩站成一个圆圈的环排列数为9！，5个女孩插入到10男孩形成的10个空中的插入方法数为P(10,5)。根据乘法原理，10个男孩和5个女孩站成一个圆圈，没有两个女孩相邻的排列法为：9!×P(10,5)=（9!×10!)/5!。电子科技大学离散数学课程组——国家精品课程67-242019/8/52.3.2组合问题定义2.3.2从含有n个不同元素的集合S中无序选取的r个元素叫做S的一个r-组合，不同的组合总数记为C(n,r)。当n≥r=0时，规定C(n,r)=1。显然，当rn时，C(n,r)=0。电子科技大学离散数学课程组——国家精品课程67-252019/8/5定理2.3.4对满足0r≤n的正整数n和r有，即证明先从n个不同元素中选出r个元素，有C(n,r)种选法，再把每一种选法选出的r个元素做全排列，有r！种排法。n!C(n,r)=r!(n-r)!电子科技大学离散数学课程组——国家精品课程67-262019/8/5定理2.3.4（续）根据乘法原理，n个元素的r排列数为：即P(n,r)n!C(n,r)==r!r!(n-r)!P(n,r)=r!C(n,r)电子科技大学离散数学课程组——国家精品课程67-272019/8/5例2.3.5一副52张的扑克牌含有4种花色：梅花、方片、红桃和黑桃；各有13种点数，分别为A,2—10,J,Q,K。试求满足下列条件的组合数。（1）手中持有5张牌称为一手牌，一手牌共有多少种可能的组合？（2）一手牌中的5张都是同一花色，共有多少种可能的组合？（3）一手牌中有3张牌点数相同，另外两张牌点数相同，共有多少种可能的组合？电子科技大学离散数学课程组——国家精品课程67-282019/8/5例2.3.5解（1）一手牌可能的组合数等于从52张牌中选出5张的可能组合数，有C(52,5)种可能的组合；（2）选同一花色的5张牌分两步进行：一选花色，有C(4,1)种，二在选定的花色中选5张牌，有C(13,5)种。据乘法原理，有C(4,1)×C(13,5)种；电子科技大学离散数学课程组——国家精品课程67-292019/8/5例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)=13×12×4×6=3744种选法。电子科技大学离散数学课程组——国家精品课程67-302019/8/52.4容斥原理与鸽笼原理容斥原理是研究若干有限集合交与并的计数问题鸽笼原理则是研究某些特定对象的存在性问题。电子科技大学离散数学课程组——国家精品课程67-3120