《[工学]离散数学-第02章-计数问题.ppt》由会员分享，可在线阅读，更多相关《[工学]离散数学-第02章-计数问题.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、工学离散数学-第02章-计数问题福建农林大学离散数学课程组福建农林大学离散数学课程组2第一篇第一篇 预备知识预备知识第第2 2章章 计数问题计数问题2021/5/222021/5/222 2福建农林大学离散数学课程组福建农林大学离散数学课程组32.0 2.0 内容提要内容提要容斥原理与鸽笼原理容斥原理与鸽笼原理3乘法原理和加法原理乘法原理和加法原理1排列与组合排列与组合22021/5/222021/5/223 3福建农林大学离散数学课程组福建农林大学离散数学课程组42.1 2.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 计算排列组合计算排列组合2 2 利用容斥
2、原理利用容斥原理 计算集合基数计算集合基数 3计数问题的应用计数问题的应用 2鸽笼原理的简单鸽笼原理的简单应用应用2021/5/222021/5/224 4福建农林大学离散数学课程组福建农林大学离散数学课程组52.2.1乘法原理乘法原理如果一些工作需要如果一些工作需要t步完成步完成，第一步有，第一步有n1种不种不同的选择，第二步有同的选择，第二步有n2种不同的选择，种不同的选择，第，第t步有步有nt种不同的选择，那么完成这项工作所有可种不同的选择，那么完成这项工作所有可能的选择种数为：能的选择种数为：2021/5/222021/5/225 5福建农林大学离散数学课程组福建农林大学离散数学课程组
3、62.2.2加法原理加法原理假定假定X1,X2,Xt均为集合，第均为集合，第I个集合个集合Xi有有ni个元素。如个元素。如X1,X2,Xt为为两两不相交两两不相交的集合，的集合，则可以从则可以从X1,X2,Xt中选出的元素总数为：中选出的元素总数为：n1+n2+nt。即集合即集合即集合即集合 X X1 1X X2 2X Xt t含有含有含有含有n n1 1+n+n2 2+n+ntt个元素。个元素。个元素。个元素。2021/5/222021/5/226 6福建农林大学离散数学课程组福建农林大学离散数学课程组72.3 2.3 排列与组合排列与组合从某个集合中有序的选取若干个元素的问题，从某个集合中
4、有序的选取若干个元素的问题，称为称为排列问题排列问题。2021/5/222021/5/227 7福建农林大学离散数学课程组福建农林大学离散数学课程组82.3.1 2.3.1 排列问题排列问题定义定义2.3.1 从含从含 n 个不同元素个不同元素的集合的集合S中中有序有序选选取的取的 r 个元素叫做个元素叫做 S 的一个的一个 r-r-排列排列排列排列，不同的，不同的r-r-排列排列排列排列总数记为总数记为 P(n,r)。如果如果r=n，则称这个排列为，则称这个排列为 S 的一个的一个全排列全排列全排列全排列，简称为简称为 S 的排列。的排列。显然显然，当当当当 rn rn 时，时，时，时，P(
5、n,r)=0P(n,r)=0。2021/5/222021/5/228 8福建农林大学离散数学课程组福建农林大学离散数学课程组9例例2.3.1解解从含从含3个元素的不同集合个元素的不同集合S中有序选取中有序选取2个元素的个元素的排列总数为排列总数为6种。种。如果将这如果将这3个元素记为个元素记为A、B和和C，则，则6个排列为个排列为AB,AC,BA,BC,CB,CA。从含从含3个不同元素的集合个不同元素的集合S中有序选取中有序选取2个元素的排个元素的排列总数。列总数。2021/5/222021/5/229 9福建农林大学离散数学课程组福建农林大学离散数学课程组10定理定理2.3.1对满足对满足r
6、n的正整数的正整数n和和r有有第第r位位第第r-1位位第第3位位第第2位位第第1位位nn-1n-2n-(r-2)图图2.3.1n-(r-1)2021/5/222021/5/221010福建农林大学离散数学课程组福建农林大学离散数学课程组11推论推论2.3.2n个不同元素的排列共有个不同元素的排列共有n！种，其中！种，其中 2021/5/222021/5/221111福建农林大学离散数学课程组福建农林大学离散数学课程组12练习练习:P443,4,63.一枚硬币抛一枚硬币抛4次并且每次抛掷结果被记录下来。次并且每次抛掷结果被记录下来。问可能有多少种不同的正面和反面的序列问可能有多少种不同的正面和反
7、面的序列?答答:24=16种。种。4.某人有某人有8件衬衫、件衬衫、4条裤子、条裤子、5双鞋，双鞋，全套衣服用有多少种可能的选择？全套衣服用有多少种可能的选择？答：答：845160种。种。6.P(4,4)=4321=24P(6,5)=65432=720，P(7,2)=76=42。2021/5/222021/5/221212福建农林大学离散数学课程组福建农林大学离散数学课程组13环形环形r-排列排列例例2.3.36个人围坐在圆桌上，有多少种不同的坐个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。法？通过转圈得到的坐法视为同一种坐法。解解:6个人围坐在圆桌上，有个人围坐在圆
8、桌上，有6!/6=120种不同的坐法。种不同的坐法。图图2.3.2AEFBDCn n个人围坐圆桌上，有个人围坐圆桌上，有个人围坐圆桌上，有个人围坐圆桌上，有(n-1)(n-1)！种不同的坐法，我们种不同的坐法，我们种不同的坐法，我们种不同的坐法，我们称这种排列为称这种排列为称这种排列为称这种排列为环排列环排列环排列环排列;从从从从 nn个人中选出个人中选出个人中选出个人中选出 r r个人围圆个人围圆个人围圆个人围圆桌而坐，称为桌而坐，称为桌而坐，称为桌而坐，称为 环形环形环形环形r-r-排列排列排列排列。2021/5/222021/5/221313福建农林大学离散数学课程组福建农林大学离散数学
9、课程组14定理定理2.3.3含含n个不同元素的集合的个不同元素的集合的环形环形r-排列数排列数Pc(n,r)是是(2.3.3)2021/5/222021/5/221414福建农林大学离散数学课程组福建农林大学离散数学课程组15例例2.3.4求满足下列条件的排列数。求满足下列条件的排列数。(1)10个男孩和个男孩和5个女孩个女孩站成一排站成一排，无两个女孩相邻无两个女孩相邻。(2)10个男孩和个男孩和5个女孩个女孩站成一圆圈站成一圆圈,无两个女孩相邻无两个女孩相邻.解解(1)10个男孩的全排列为个男孩的全排列为10!，5个女孩插入到个女孩插入到10个个男孩形成的男孩形成的11个空格中的插入方法数
10、为个空格中的插入方法数为P(11,5)。根据乘法原理，根据乘法原理，10个男孩和个男孩和5个女孩站成一排，没个女孩站成一排，没有两个女孩相邻的排列数为：有两个女孩相邻的排列数为：10!P(11,5)=（10!11!)/6!。2021/5/222021/5/221515福建农林大学离散数学课程组福建农林大学离散数学课程组16例例2.3.4解（续）解（续）(2)根据定理根据定理2.3.3，10个男孩站成一个圆圈的环排个男孩站成一个圆圈的环排列数为列数为9!，5个女孩插入到个女孩插入到10男孩形成的男孩形成的10个空中的插入方个空中的插入方法数为法数为P(10,5)。根据乘法原理，根据乘法原理，10
11、个男孩和个男孩和5个女孩站成一个圆个女孩站成一个圆圈，没有两个女孩相邻的排列法为：圈，没有两个女孩相邻的排列法为：9!P(10,5)=9!P(10,5)=（9!10!)/5!9!10!)/5!。2021/5/222021/5/221616福建农林大学离散数学课程组福建农林大学离散数学课程组172.3.2组合问题组合问题定义定义2.3.2从含有从含有n个不同元素的集合个不同元素的集合S中无序选取中无序选取的的r个元素叫做个元素叫做S的一个的一个r-组合组合，不同的组合总数记，不同的组合总数记为为C(n,r)。当当当当 nr=0nr=0时，规定时，规定时，规定时，规定 C(n,r)=1C(n,r)
12、=1。显然，当显然，当显然，当显然，当 rnrn时，时，时，时，C(n,r)=0C(n,r)=0。2021/5/222021/5/221717福建农林大学离散数学课程组福建农林大学离散数学课程组18定理定理2.3.4对满足对满足0m)个鸽笼，则个鸽笼，则存在一存在一个个鸽笼鸽笼至少住至少住进进+1只鸽子。这里，只鸽子。这里，表示表示小于等于小于等于x的最大整数。的最大整数。2021/5/222021/5/223333福建农林大学离散数学课程组福建农林大学离散数学课程组34例例2.7.2某一制造铁盘的工厂，由于设备和技术的某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制在原因只能
13、将生产盘子的重量控制在100克克到到100.1克克之间。现需要制成之间。现需要制成重量相差不超过重量相差不超过0.005克的两铁克的两铁盘盘来配制一架天平，问该工厂来配制一架天平，问该工厂至少要生产多少铁盘至少要生产多少铁盘才能确保得到一对符合要求的铁盘。才能确保得到一对符合要求的铁盘。2.7计数问题的应用计数问题的应用2021/5/222021/5/223434福建农林大学离散数学课程组福建农林大学离散数学课程组35例例2.7.2解解将铁盘按重量分类，将铁盘按重量分类，所有所有100克到克到100.005克的分为第一类；克的分为第一类；100.005克到克到100.01克的分为一类；克的分为
14、一类；100.01克到克到100.015克的又为一类，克的又为一类，.，最后，最后，100.095克到克到100.1克为一类，共计克为一类，共计20类，类，由由鸽笼原理鸽笼原理知，若该工厂生产知，若该工厂生产21个铁盘，那么就能个铁盘，那么就能得知有两个铁盘属于同一类，因而它们之间的重量得知有两个铁盘属于同一类，因而它们之间的重量差将不超过差将不超过0.005克。克。2021/5/222021/5/223535福建农林大学离散数学课程组福建农林大学离散数学课程组362023/3/6练习练习:P4416,2016.把把5个顶点放到边长为个顶点放到边长为2的正方形中的正方形中,则其中至少有两则其中
15、至少有两个点的距离小于等于个点的距离小于等于。17.证法证法:将边长为将边长为2的正方形分成的正方形分成4块边长为块边长为1的正方形。的正方形。20.在由在由a,b,c,d四个字构成的四个字构成的n位符号串中位符号串中,求求a,b,c至少至少出现一次的符号串的数目。出现一次的符号串的数目。21.解法：解法：全集全集U=由由a,b,c,d四个字构成的四个字构成的n位符号串位符号串22.A=a不出现的不出现的n位符号串位符号串23.B=b不出现的不出现的n位符号串位符号串24.C=c不出现的不出现的n位符号串位符号串2021/5/222021/5/223636福建农林大学离散数学课程组福建农林大学
16、离散数学课程组372.8本章总结本章总结1、乘法原理和加法原理的基本含义；、乘法原理和加法原理的基本含义；2、r-排列，全排列，环形排列，全排列，环形r排列，环排列，排列，环排列，r-组合组合的基本概念，它们之间关系和相应的计算公式；的基本概念，它们之间关系和相应的计算公式；3、容斥原理和鸽笼原理的基本概念及正确使用；、容斥原理和鸽笼原理的基本概念及正确使用；2021/5/222021/5/223737福建农林大学离散数学课程组福建农林大学离散数学课程组38习题类型习题类型（1）计算题：计算题：涉及排列数与组合数的计算，利用涉及排列数与组合数的计算，利用容斥原理的计算；容斥原理的计算；（2）证
17、明题：证明题：涉及对鸽笼原理的应用。涉及对鸽笼原理的应用。2021/5/222021/5/223838福建农林大学离散数学课程组福建农林大学离散数学课程组39作业作业第第44页页17,21预习预习:第第3章章命题逻辑命题逻辑2021/5/222021/5/223939人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。