第2章-计数问题课件

电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离 散 数 学电子科技大学计算机科学与工程学院示 范 性 软 件 学 院14 14 七月七月 2024 2024电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-2 2第第2 2章章 计数问题计数问题 计计数数问问题题是是组组合合数数学学研研究究的的主主要要问问题题之之一一。西西班班牙牙数数学学家家Abraham Abraham ben ben Meir Meir ibn ibn Ezra(1092Ezra(10921167)1167)和和法法国国数数学学家家、哲哲学学家家、天天文文学学家家Levi Levi ben ben Gerson(1288Gerson(12881344)1344)是是排排列列与与组组合合领领域域的的两两位位早早期期研研究究者者。另另外外，法法国国数数学学家家Blaise Blaise PascalPascal还还发发明明了了一一种种机机械械计计算算器器，这这种种计计算算器器非非常常类类似似于于2020世世纪纪4040年年代代在在数数字字电电子子计计算算机机发发明明之之前前使使用用的的一一种种机机械械计计算算器器。同同时时，计计数数技技术术在在数数学学和和计计算算机机科科学学中中是是很很重重要要的的，特特别别是是在在数数据据结结构构、算算法法分分析析与与设计等后续课程中有非常重要的应用。设计等后续课程中有非常重要的应用。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-3 32.0 2.0 内容提要内容提要容斥原理与鸽笼原理容斥原理与鸽笼原理3离散概率离散概率4乘法原理和加法原理乘法原理和加法原理1排列与组合排列与组合2递归关系递归关系5电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-4 41.1 1.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1乘法原理和加乘法原理和加法原理法原理2 2排列组合的计排列组合的计算算 3 3利用容斥原理利用容斥原理计算有限集合的计算有限集合的交与并交与并 31 1 离散概率离散概率2 2 离散概念的计离散概念的计 算公式及性质算公式及性质 21 1 鸽笼原理鸽笼原理2 2 鸽笼原理的简鸽笼原理的简单应用单应用3 3 递归关系递归关系4 4 递归关系的建递归关系的建立和计算立和计算 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5 5表表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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6 62.2.1 2.2.1 乘法原理乘法原理 如如果果一一些些工工作作需需要要t t步步完完成成，第第一一步步有有n n1 1种种不不同同的的选选择择，第第二二步步有有n n2 2种种不不同同的的选选择择，第第t t步步有有n nt t种种不不同同的的选选择择，那那么么完完成成这这项项工工作作所所有可能的选择种数为：有可能的选择种数为：电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-7 7例例2.2.2 Melissa2.2.2 Melissa病毒病毒19901990年年，一一种种名名叫叫MelissaMelissa的的病病毒毒利利用用侵侵吞吞系系统统资资源源的的方方法法来来破破坏坏计计算算机机系系统统，通通过过以以含含恶恶意意宏宏的的字字处处理理文文档档为为附附件件的的电电子子邮邮件件传传播播。当当字字处处理理文文档档被被打打开开时时，宏宏从从用用户户的的地地址址本本中中找找出出前前5050个个地地址址，并并将将病病毒毒转转发发给给他他们们。用用户户接接收收到到这这些些被被转转发发的的附附件件并并将将字字处处理理文文档档打打开开后后，病病毒毒会会自自动动继继续续转转发发，不不断断往往复复扩扩散散。病病毒毒非非常常快快速速地地转转发发邮邮件件，将将被被转转发发的的邮邮件件临临时时存存储储在在某某个个磁磁盘盘上上，当当磁磁盘盘占占满满后后，系系统统将将会会死死锁锁甚甚至至崩崩溃溃。问经过四次转发，共有多少个接收者？问经过四次转发，共有多少个接收者？解解 根据根据MelissaMelissa病毒的扩散原理，经过四次转发，病毒的扩散原理，经过四次转发，共有共有50505050+505050+5050+50+150505050+505050+5050+50+1=6377551=6377551个接收者。个接收者。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-8 8例例2.2.32.2.3在在一一幅幅数数字字图图像像中中，若若每每个个像像素素点点用用8 8位位进进行行编编码码，问问每个点有多少种不同的取值。每个点有多少种不同的取值。分分析析 用用8 8位位进进行行编编码码可可分分为为8 8个个步步骤骤：选选择择第第一一位位，选选择择第第二二位位，选选择择第第八八位位。每每一一个个位位有有两两种种选选 择择，故故 根根 据据 乘乘 法法 原原 理理，8 8位位 编编 码码 共共 有有22222222=222222222=28 8=256=256种取值。种取值。解解 每个点有每个点有256(=2256(=28 8)种不同的取值。种不同的取值。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-9 92.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。即集合即集合即集合即集合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个元素。个元素。个元素。个元素。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1010例例2.2.42.2.4由由 AliceAlice、BenBen、ConnieConnie、DolphDolph、EgbertEgbert和和FranciscoFrancisco六六个个人人组组成成的的委委员员会会，要要选选出出一一个个主主席席、一个秘书和一个出纳员。一个秘书和一个出纳员。（1 1）共有多少种选法？）共有多少种选法？（2 2）若若主主席席必必须须从从AliceAlice和和BenBen种种选选出出，共共有有多多少少种选法？种选法？（3 3）若）若EgbertEgbert必须有职位必须有职位，共有多少种选法？，共有多少种选法？（4 4）若若DolphDolph和和FranciscoFrancisco都都有有职职位位，共共有有多多少少种种选法？选法？电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1111例例2.2.4 2.2.4 解解（1 1）根根据据乘乘法法原原理理，可可能能的的选选法法种种数数为为654=654=120120；（2 2）法法一一 根根据据题题意意，确确定定职职位位可可分分为为3 3个个步步骤骤：确确定定主主席席有有2 2种种选选择择；主主席席选选定定后后，秘秘书书有有5 5个个人人选选；主主席席和和秘秘书书都都选选定定后后，出出纳纳有有4 4个个人人选选。根根据据乘乘法法原理原理，可能的选法种数为，可能的选法种数为254=40254=40；法法二二 若若AliceAlice被被选选为为主主席席，共共有有54 54=2020种种方方法法确确定定其其他他职职位位；若若BenBen为为主主席席，同同样样有有2020种种方方法法确确定定其其他他职职位位。由由于于两两种种选选法法得得到到的的集集合合不不相相交交，所所以根据以根据加法原理加法原理，共有，共有202020=4020=40种选法；种选法；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1212例例2.2.4 2.2.4 解解(续续)(3)(3)法法一一 将将确确定定职职位位分分为为3 3步步：确确定定EgbertEgbert的的职职位位,有有3 3种种方方法法；确确定定余余下下的的较较高高职职位位人人选选,有有5 5个个人人选选；确确定定最最后后一一个个职职位位的的人人选选,有有4 4个个人人选选。根根据据乘法原理乘法原理，共有，共有354=60354=60种选法；种选法；法法二二 根根据据(1)(1)的的结结论论，如如果果EgbertEgbert为为主主席席，有有2020种种方方法法确确定定余余下下的的职职位位；若若EgbertEgbert为为秘秘书书，有有2020种种方方法法确确定定余余下下的的职职位位；若若EgbertEgbert为为出出纳纳员员，也也有有2020种种方方法法确确定定余余下下的的职职位位。由由于于三三种种选选法法得得到到的的集集合合不相交，根据不相交，根据加法原理加法原理，共有，共有2020202020=6020=60种选法；种选法；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1313例例2.2.4 2.2.4 解解(续续)（4 4）将将给给DolphDolph、FranciscoFrancisco和和另另一一个个人人指指定定职职位位分为分为3 3步：步：给给DolphDolph指定职位，指定职位，有有3 3个职位可选；个职位可选；给给FranciscoFrancisco指定职位，指定职位，有有2 2个职位可选；个职位可选；确定最后一个职位的人选确定最后一个职位的人选，有，有4 4个人选。个人选。根据根据乘法原理乘法原理，共有，共有324=24324=24种选法。种选法。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-14142.3 2.3 排列与组合排列与组合 ZekeZeke、YungYung、XenoXeno和和WilmaWilma四四个个候候选选人人竞竞选选同同一一职职位位。为为了了使使选选票票上上人人名名的的次次序序不不对对投投票票者者产产生生影影响响，有有必必要要将将每每一一种种可可能能的的人人名名次次序序打打印印在在选选票票上上。会有多少种不同的选票呢？会有多少种不同的选票呢？从从某某个个集集合合中中有有序序的的选选取取若若干干个个元元素素的的问问题题，称称为为排列问题排列问题。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-15152.3.1 2.3.1 排列问题排列问题定定义义2.3.12.3.1 从从含含n n个个不不同同元元素素的的集集合合S S中中有有序序选选取取的的r r个个元元素素叫叫做做S S的的一一个个r r r r-排排排排列列列列，不不同同的的排排列列总总数数记记为为P(n,P(n,r)r)。如如果果r r=n n，则则称称这这个个排排列列为为S S的的一一个个全排列全排列全排列全排列，简称为，简称为S S的排列。的排列。显然显然，当当当当rnrnrnrn时，时，时，时，P(n,r)=0P(n,r)=0P(n,r)=0P(n,r)=0。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1616例例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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1717定理定理2.3.12.3.1对满足对满足rnrn的正整数的正整数n n和和r r有有第第r r位位第第r-1r-1位位第第3 3位位第第2 2位位第第1 1位位n nn-1n-1n-2n-2 n-(r-2)n-(r-2)n-(r-1)n-(r-1)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1818推论推论2.3.22.3.2n n个不同元素的排列共有个不同元素的排列共有n n！种，其中！种，其中 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1919例例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,D,E E和和F F三三个个字字母母的的全全排排列列，有有3 3！种种排排列列，第第二二步步将将已已排排序序的的D,D,E E和和F F看看成成一一个个整整体体，与与A,A,B B和和C C共共4 4个个元元素素构构造造出出A,A,B,B,C,C,D,D,E,E,F F的的全全排排列列，有有4 4！种种排排列列。又根据乘法原理，满足条件的排列总数有又根据乘法原理，满足条件的排列总数有3 3！44！=144=144。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-2020例例2.3.32.3.36 6个个人人围围坐坐在在圆圆桌桌上上，有有多多少少种种不不同同的的坐坐法法？通通过过转圈得到的坐法视为同一种坐法。转圈得到的坐法视为同一种坐法。解解 6 6个人围坐在圆桌上，个人围坐在圆桌上，有有120120种不同的坐法。种不同的坐法。A AE EF FB BD DC Cn n n n个人围坐圆桌上，有个人围坐圆桌上，有个人围坐圆桌上，有个人围坐圆桌上，有(n-1)(n-1)(n-1)(n-1)！种不同的坐法，我们称！种不同的坐法，我们称！种不同的坐法，我们称！种不同的坐法，我们称这种排列为这种排列为这种排列为这种排列为环排列环排列环排列环排列，从，从，从，从n n n n个人中选出个人中选出个人中选出个人中选出r r r r个人为圆桌而坐个人为圆桌而坐个人为圆桌而坐个人为圆桌而坐称为称为称为称为环形环形环形环形r-r-r-r-排列排列排列排列。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-2121定理定理2.3.32.3.3含含n n个不同元素的集合的个不同元素的集合的环形环形r-r-排列数排列数P Pc c(n,r)(n,r)是是电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-2222例例2.3.42.3.4求满足下列条件的排列数。求满足下列条件的排列数。(1)10(1)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,P(11,5)5)。根根据据乘乘法法原原理理，1010个个男男孩孩和和5 5个个女女孩孩站成一排，没有两个女孩相邻的排列数为：站成一排，没有两个女孩相邻的排列数为：10!P(11,5)=10!P(11,5)=（10!11!)/6!10!11!)/6!。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-2323例例2.3.4 2.3.4 解（续）解（续）（2 2）根根据据定定理理2.3.32.3.3，1010个个男男孩孩站站成成一一个个圆圆圈圈的的环环排排列列数数为为9 9！，5 5个个女女孩孩插插入入到到1010男男孩孩形形成成的的1010个个空空中中的的插插入入方方法法数数为为P(10,P(10,5)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!。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-24242.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)。当当当当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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-2525定理定理2.3.42.3.4对满足对满足0 r n0n)m(mn)个个鸽鸽笼笼，则则存存在在一一个个鸽鸽笼笼至至少少住住进进 只只鸽鸽子子。这这里里，表表示小于等于示小于等于x x的最大整数。的最大整数。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-4747例例2.4.62.4.6如如果果一一个个图图书书馆馆里里3030本本离离散散数数学学书书共共有有12031203页页，那那么必然有一本离散数学书至少有么必然有一本离散数学书至少有4141页。页。证证明明 设设页页是是鸽鸽子子，离离散散数数学学书书是是鸽鸽笼笼，把把每每页页分分配配到到它它所所出出现现的的离离散散数数学学书书中中，根根据据定定理理2.4.52.4.5，则存在一个鸽笼至少住进则存在一个鸽笼至少住进 =41=41，即结论得证。即结论得证。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-48482.52.5 离散概率简介离散概率简介 概概率率(Probability)(Probability)是是1717世世纪纪为为分分析析博博弈弈游游戏戏而而发发展展起起来来的的学学科科，最最初初计计算算概概率率仅仅有有计计数数一一种种方方法。法。本本节节主主要要介介绍绍离离散散概概率率的的基基本本概概率率、基基本本性性质质和概率计算的简单例子。和概率计算的简单例子。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-49492.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称为称为样本空间样本空间样本空间样本空间。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5050例例2.5.12.5.1请请举举例例说说明明下下列列实实验验可可能能发发生生的的事事件件，并并列列出出其其样样本空间。本空间。（1 1）掷出一个六个面的骰子；）掷出一个六个面的骰子；（2 2）从）从10001000个微处理器中随机抽取个微处理器中随机抽取5 5个；个；（3 3）在北京人民医院选取一个婴儿。）在北京人民医院选取一个婴儿。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5151例例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）北京人民医院的所有婴儿。）北京人民医院的所有婴儿。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5252定义定义2.5.22.5.2有限样本空间有限样本空间S S中的事件中的事件E E的概率的概率P(E)P(E)定义为：定义为：其中其中|E|,|S|E|,|S|分别表示集合分别表示集合E E和和S S的基数。的基数。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5353例例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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5454例例2.5.32.5.3掷出两个各面同性的骰子，求点数之和为掷出两个各面同性的骰子，求点数之和为1010的概率。的概率。解解 设设点点数数之之和和为为1010这这个个事事件件为为E E，样样本本空空间间为为S S，则则根根据据题题意意|E|E|=3,3,|S|S|=3636。代代入入式式(2.5.1)(2.5.1)，得得P(E)=3/36=1/12 P(E)=3/36=1/12。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5555例例2.5.42.5.4在在福福利利彩彩票票中中，若若彩彩民民从从1 15252个个数数中中选选取取的的6 6个个数数与与随随机机生生成成的的中中奖奖数数字字相相同同(不不计计顺顺序序)，则则可可以以赢赢得大奖。求一张彩票赢得大奖的概率。得大奖。求一张彩票赢得大奖的概率。解解 从从5252个个数数字字中中选选取取6 6个个共共有有C(52,C(52,6)6)种种选选法法，即即|S|S|=C(52,C(52,6)6)，而而得得大大奖奖的的组组合合只只有有一一种种，即即|E|=1|E|=1，根据概率的定义，得：，根据概率的定义，得：P(E)=1/C(52,6)=0.00000004P(E)=1/C(52,6)=0.00000004。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-56562.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)(1)保证一个结果的概率为非负数且不超过保证一个结果的概率为非负数且不超过1 1；条件条件(2)(2)保证所有结果的概率之和为保证所有结果的概率之和为1 1，即进行实验，即进行实验后，必出现某个结果。后，必出现某个结果。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5757例例2.5.52.5.5一一个个一一面面较较重重的的骰骰子子，2 26 6以以相相同同的的机机会会出出现现，1 1出出现现的的机机会会是是其其他他数数字字的的3 3倍倍。试试求求出出1 16 6的的概概率率函数值。函数值。解解 设设P(2)P(2)=P(3)P(3)=P(4)P(4)=P(5)P(5)=P(6)P(6)=a a，则则P(6)P(6)=3a3a。又又因因为为P(1)+P(1)+P(2)+P(2)+P(3)+P(3)+P(4)+P(4)+P(5)+P(5)+P(6)P(6)=1 1，所所以以有有5a5a3a 3a=1 1，即即a a=1/81/8。从从而而P(2)P(2)=P(3)P(3)=P(4)P(4)=P(5)P(5)=P(6)P(6)=1/8=1/8，P(6)=3/8P(6)=3/8。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5858概率函数概率函数定定义义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的补的概率满足的补的概率满足电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5959例例2.2.6 2.2.6 生日问题生日问题n n个个人人中中，求求至至少少有有两两个个人人生生日日相相同同(同同月月同同日日不不计计年年)的的概概率率。假假定定出出生生在在某某天天的的概概率率均均等等，忽忽略略2 2月月2929日。日。解解 设设E E表表示示“至至少少两两个个人人生生日日相相同同”，则则表表示示“没有两个人生日相同没有两个人生日相同”，则，则 从而从而 事实上，事实上，随着天数随着天数n n的增加，至少两个人的增加，至少两个人生日相同的概率也随着增加生日相同的概率也随着增加，当，当n23n23时，时，至少有两个人生日相同的概率大于至少有两个人生日相同的概率大于1/21/2。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6060两个事件并的概率两个事件并的概率定理定理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)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6161例例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),事件事件E2E2的种数为的种数为5 5，即即(1,5),(2,4),(3,3),(4,2),(5,1)(1,5),(2,4),(3,3),(4,2),(5,1)。E1E2E1E2的种数为的种数为1 1。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6262例例2.5.7 2.5.7 解（续）解（续）从而从而 P(EP(E1 1)=1/6=1/6 ,P(EP(E2 2)=5/36,5/36,P(EP(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-67-63632.62.6 递归关系递归关系递归关系递归关系可用于解决一些特定的计数问题。可用于解决一些特定的计数问题。递递归归关关系系是是序序列列中中第第n n个个元元素素与与它它相相邻邻前前若若干干个个元元素之间的关系素之间的关系。例如例如1 1、第一个数是、第一个数是5 5；2 2、将前一项加、将前一项加3 3得到后一项。得到后一项。5,8,11,14,5,8,11,14,递归关系递归关系a a1 1=5=5，a an n=a=an-1n-1+3+3 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6464定义定义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 n-1 1中中的的某某些些项项表表示示a an n的的等等式式称称为为递递归归关关系系(recurrence(recurrence relation)relation)。显显示示地地给给出出序序列列a a0 0,a a1 1,a a2 2,的的有有限限项项的的值值，称称为为初初始始条条件件(initial condition)(initial condition)。显显然然，递递归归关关系系和和确确定定的的初初始始条条件件一一起起，才才能能确确定定一个序列。一个序列。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6565例例2.6.12.6.1某某人人投投资资10001000元元，每每年年可可收收益益1212。A An n表表示示他他在在第第n n年年末末的的总总资资产产。求求出出定定义义序序列列AAn 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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6666例例2.6.22.6.2S Sn n表表示示不不含含子子串串“111”111”的的n n位位字字符符串串的的个个数数。求求出出序列序列SSn n 的递归关系和初始条件。的递归关系和初始条件。解解 序列序列SSn 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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-67672.7 2.7 计数问题的应用计数问题的应用例例2.7.12.7.1 7 7个个科科学学工工作作者者从从事事一一项项机机密密的的技技术术研研究究，他他们们的的工工作作室室装装有有电电子子锁锁，每每位位科科学学工工作作者者都都有有打打开开电电子子锁锁用用的的“钥钥匙匙”。为为了了安安全全起起见见，必必须须有有4 4位位在在场场时时才才能能打打开开大大门门。试试问问该该电电子子锁锁至至少少应应具具备备多多少少个个特特征征？每每位位科科学学工工作作者者的的“钥钥匙匙”至至少少应应有有多多少少种种特特征征？解解 为为了了使使任任意意3 3个个人人在在场场时时至至少少缺缺少少一一个个特特征征而而打打不不开开门门，该该电电子子锁锁应应具具备备C(7,3)=35C(7,3)=35种种特特征征；每每个个科科学学工工作者的作者的“钥匙钥匙”至少要有至少要有C(6,3)=20C(6,3)=20种特征。种特征。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6868例例2.7.22.7.2某某一一制制造造铁铁盘盘的的工工厂厂，由由于于设设备备和和技技术术的的原原因因只只能能将将生生产产盘盘子子的的重重量量控控制制在在a a克克到到（a+0.1a+0.1）克克之之间间。现现需需要要制制成成重重量量相相差差不不超超过过0.0050.005克克的的两两铁铁盘盘来来配配制制一一架架天天平平，问问该该工工厂厂至至少少要要生生产产多多少少铁铁盘盘才才能能得得到一对符合要求的铁盘。到一对符合要求的铁盘。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6969例例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克。克。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-7070例例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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-7171例例2.7.42.7.4计算下面算法中基本操作的次数算法计算下面算法中基本操作的次数算法 输入输入：s1,s2,sns1,s2,sn和序列的长度。和序列的长度。输出输出：s1,s2,sns1,s2,sn，按非递减顺序排列。，按非递减顺序排列。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-7272例例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./找到最大的元素找到最大的元素6.max_index=1/6.max_index=1/初始时认为初始时认为s1s1是最大的元素是最大的元素7.for i=2 to n7.for i=2 to n8.8.if if(sismax_index)/(sismax_index)/比比较较得得到到较较大大的的元元素素，并并更更新新最最大元素大元素9.max_index=i 10./9.max_index=i 10./将最大的元素移至序列尾将最大的元素移至序列尾11.swap(sn,smax_index)11.swap(sn,smax_index)12.selection_sort(s,n-1)12.selection_sort(s,n-1)13.13.电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-7373例例2.7.4 2.7.4 解解设设计计算算n n个个数数排排序序的的比比较较执执行行次次数数为为b bn n，则则该该算算法法中的比较语句的执行次数的中的比较语句的执行次数的递归关系递归关系为：为：b bn n=b=bn-1 n-1+n 1+n 1，其其初始条件初始条件为：为：b b1 1=0=0。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-7474例例2.7.4 2.7.4 解（续）解（续）用用迭代法迭代法求解该递归关系：求解该递归关系：b bn n=b=bn-1n-1+n1+n1 =b =bn-2n-2+n2+n-1+n2+n-1 =b =bn-3n-3+n3+n2+n1+n3+n2+n1 =b =b1 1+1+2+n3+n2+n1+1+2+n3+n2+n1 =0+1+2+=0+1+2+n 3+n2+n1+n 3+n2+n1 =n(n-1)/2 =n(n-1)/2。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-75752.8 2.8 本章总结本章总结 1.1.乘法原理和加法原理的基本含义；乘法原理和加法原理的基本含义；2.2.r-r-排排列列，全全排排列列，环环形形r r排排列列，环环排排列列，r-r-组组合合的基本概念，它们之间关系和相应的计算公式；的基本概念，它们之间关系和相应的计算公式；3.3.容斥原理和鸽笼原理的基本概念及正确使用；容斥原理和鸽笼原理的基本概念及正确使用；4.4.实实验验、事事件件、样样本本空空间间、概概率率函函数数的的基基本本概概念念，离散概率的计算；离散概率的计算；5.5.递递归归关关系系、初初始始条条件件的的概概念念、递递归归关关系系的的建建立立和求解。和求解。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-7676习题类型习题类型（1 1）基本概念题：基本概念题：涉及离散概率的基本概念；涉及离散概率的基本概念；（2 2）计计算算题题：涉涉及及排排列列数数与与组组合合数数的的计计算算，利利用用容容斥斥原原理理的的计计算算，离离散散概概率率的的计计算算和和递递归归关关系系的的建建立与求解；立与求解；（3 3）证明题：证明题：涉及对鸽笼原理的应用。涉及对鸽笼原理的应用。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-7777习题习题第第44-4544-45页页14.14.19.19.20.20.21.21.电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程202.115.21.136:8080/lssx202.115.21.136:8080/lssx/Thank you拯畏怖汾关炉烹霉躲渠早膘岸缅兰辆坐蔬光膊列板哮瞥疹傻俘源拯割宜跟三叉神经痛-治疗三叉神经痛-治疗