1、福建农林大学离散数学课程组福建农林大学离散数学课程组1离离 散散 数数 学学2023年8月30日星期三福建农林大学离散数学课程组福建农林大学离散数学课程组22023-8-30第一篇第一篇 预备知识预备知识第第2 2章章 计数问题计数问题福建农林大学离散数学课程组福建农林大学离散数学课程组32023-8-302.0 2.0 内容提要内容提要容斥原理与鸽笼原理容斥原理与鸽笼原理3乘法原理和加法原理乘法原理和加法原理1排列与组合排列与组合2福建农林大学离散数学课程组福建农林大学离散数学课程组42023-8-302.1 2.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1
2、计算排列组合计算排列组合2 2 利用容斥原理利用容斥原理 计算集合基数计算集合基数 3计数问题的应用计数问题的应用 2鸽笼原理的简单鸽笼原理的简单应用应用福建农林大学离散数学课程组福建农林大学离散数学课程组52023-8-302.2.1 乘法原理乘法原理 如果一些工作需要如果一些工作需要 t 步完成步完成，第一步有，第一步有 n1 种不种不同的选择，第二步有同的选择，第二步有 n2 种不同的选择，种不同的选择，第，第 t步有步有 nt 种不同的选择，那么完成这项工作所有可种不同的选择，那么完成这项工作所有可能的选择种数为：能的选择种数为：12tnnn福建农林大学离散数学课程组福建农林大学离散数
3、学课程组62023-8-302.2.2 加法原理加法原理 假定假定 X1,X2,Xt 均为集合，第均为集合，第 I 个集合个集合 Xi 有有 ni个元素。如个元素。如 X1,X2,Xt 为为两两不相交两两不相交的集合，的集合，则可以从则可以从 X1,X2,Xt 中选出的元素总数为：中选出的元素总数为：n1+n2+nt。福建农林大学离散数学课程组福建农林大学离散数学课程组72023-8-302.3 2.3 排列与组合排列与组合从某个集合中有序的选取若干个元素的问题，从某个集合中有序的选取若干个元素的问题，称为称为排列问题排列问题。福建农林大学离散数学课程组福建农林大学离散数学课程组82023-8
4、-302.3.1 2.3.1 排列问题排列问题定义定义2.3.1 从含从含 n 个不同元素个不同元素的集合的集合S中中有序有序选取选取的的 r 个元素叫做个元素叫做 S 的一个的一个，不同的，不同的总数记为总数记为 P(n,r)。如果如果r=n，则称这个排列为，则称这个排列为 S 的一个的一个，简称为简称为 S 的排列。的排列。显然显然，福建农林大学离散数学课程组福建农林大学离散数学课程组92023-8-30例例2.3.1解解 从含从含3个元素的不同集合个元素的不同集合S中有序选取中有序选取2个元素的个元素的排列总数为排列总数为6种。种。如果将这如果将这3个元素记为个元素记为A、B和和C，则，
5、则6个排列为个排列为 AB,AC,BA,BC,CB,CA。从含从含3个不同元素的集合个不同元素的集合S中有序选取中有序选取2个元素的排个元素的排列总数。列总数。福建农林大学离散数学课程组福建农林大学离散数学课程组102023-8-30定理定理2.3.1对满足对满足 rn 的正整数的正整数 n 和和 r 有有P(n,r)n(n-1)(n-(r-1)第第r位位 第第r-1位位 第第3位位 第第2位位 第第1位位nn-1n-2 n-(r-2)图图2.3.1 n-(r-1)福建农林大学离散数学课程组福建农林大学离散数学课程组112023-8-30推论推论2.3.2n个不同元素的排列共有个不同元素的排列
6、共有n！种，其中！种，其中 n!n(n1)2 1福建农林大学离散数学课程组福建农林大学离散数学课程组122023-8-30练习练习:P44 3,4,63.一枚硬币抛一枚硬币抛4次并且每次抛掷结果被记录下来。次并且每次抛掷结果被记录下来。问可能有多少种不同的正面和反面的序列问可能有多少种不同的正面和反面的序列?答答:24=16 种。种。4.某人有某人有8件衬衫、件衬衫、4条裤子、条裤子、5双鞋，双鞋，全套衣服用有多少种可能的选择？全套衣服用有多少种可能的选择？答：答：845160 种。种。6.P(4,4)=432 1=24 P(6,5)=654 32=720，P(7,2)=76=42。福建农林大
7、学离散数学课程组福建农林大学离散数学课程组132023-8-30环形环形 r-排列排列例例2.3.3 6个人围坐在圆桌上，有多少种不同的坐个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。法？通过转圈得到的坐法视为同一种坐法。解解:6个人围坐在圆桌上，有个人围坐在圆桌上，有 6!/6=120 种不同的坐法。种不同的坐法。图图2.3.2AEFBDC福建农林大学离散数学课程组福建农林大学离散数学课程组142023-8-30定理定理2.3.3含含 n 个不同元素的集合的个不同元素的集合的环形环形 r-排列数排列数 Pc(n,r)是是 (2.3.3)cP(n,r)n!P(n,r)
8、=rr(n-r)!福建农林大学离散数学课程组福建农林大学离散数学课程组152023-8-30例例2.3.4求满足下列条件的排列数。求满足下列条件的排列数。(1)10个男孩和个男孩和5个女孩个女孩站成一排站成一排，无两个女孩相邻无两个女孩相邻。(2)10个男孩和个男孩和5个女孩个女孩站成一圆圈站成一圆圈,无两个女孩相邻无两个女孩相邻.解解 (1)10个男孩的全排列为个男孩的全排列为10!，5个女孩插入到个女孩插入到10个个男孩形成的男孩形成的11个空格中的插入方法数为个空格中的插入方法数为 P(11,5)。根据乘法原理，根据乘法原理，10个男孩和个男孩和5个女孩站成一排，没个女孩站成一排，没有两
9、个女孩相邻的排列数为：有两个女孩相邻的排列数为：10!P(11,5)=（10!11!)/6!。福建农林大学离散数学课程组福建农林大学离散数学课程组162023-8-30例例2.3.4 解（续）解（续）(2)根据定理根据定理2.3.3，10个男孩站成一个圆圈的环排个男孩站成一个圆圈的环排列数为列数为 9!，5个女孩插入到个女孩插入到10男孩形成的男孩形成的10个空中的插入方个空中的插入方法数为法数为 P(10,5)。根据乘法原理，根据乘法原理，10个男孩和个男孩和5个女孩站成一个圆个女孩站成一个圆圈，没有两个女孩相邻的排列法为：圈，没有两个女孩相邻的排列法为：福建农林大学离散数学课程组福建农林大
10、学离散数学课程组172023-8-302.3.2 组合问题组合问题定义定义2.3.2 从含有从含有n个不同元素的集合个不同元素的集合S中无序选取中无序选取的的r个元素叫做个元素叫做S的一个的一个r-组合组合，不同的组合总数记，不同的组合总数记为为 C(n,r)。福建农林大学离散数学课程组福建农林大学离散数学课程组182023-8-30定理定理2.3.4对满足对满足 0m)个鸽笼，则个鸽笼，则存在一存在一个个鸽笼鸽笼至少住至少住进进 +1只鸽子。这里，只鸽子。这里，表示表示小于等于小于等于 x 的最大整数。的最大整数。1 nmx 福建农林大学离散数学课程组福建农林大学离散数学课程组342023-
11、8-30例例2.7.2 某一制造铁盘的工厂，由于设备和技术的某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制在原因只能将生产盘子的重量控制在100克克到到100.1克克之间。现需要制成之间。现需要制成重量相差不超过重量相差不超过0.005克的两铁克的两铁盘盘来配制一架天平，问该工厂来配制一架天平，问该工厂至少要生产多少铁盘至少要生产多少铁盘才能确保得到一对符合要求的铁盘。才能确保得到一对符合要求的铁盘。2.7 计数问题的应用计数问题的应用福建农林大学离散数学课程组福建农林大学离散数学课程组352023-8-30例例2.7.2 解解将铁盘按重量分类，将铁盘按重量分类，所有所有10
12、0克到克到100.005克的分为第一类；克的分为第一类；100.005克到克到100.01克的分为一类；克的分为一类；100.01克到克到100.015克的又为一类，克的又为一类，.，最后，最后，100.095克到克到100.1克为一类，共计克为一类，共计20类，类，由由鸽笼原理鸽笼原理知，若该工厂生产知，若该工厂生产21个铁盘，那么就能个铁盘，那么就能得知有两个铁盘属于同一类，因而它们之间的重量得知有两个铁盘属于同一类，因而它们之间的重量差将不超过差将不超过0.005克。克。福建农林大学离散数学课程组福建农林大学离散数学课程组362023-8-30练习练习:P44 16,2016.把把5个顶
13、点放到边长为个顶点放到边长为2的正方形中的正方形中,则其中至少有两则其中至少有两个点的距离小于等于个点的距离小于等于 。证法证法:将边长为将边长为2的正方形分成的正方形分成4块边长为块边长为1的正方形。的正方形。20.在由在由 a,b,c,d 四个字构成的四个字构成的 n 位符号串中位符号串中,求求 a,b,c 至至少出现一次的符号串的数目。少出现一次的符号串的数目。解法：解法：全集全集U=由由 a,b,c,d 四个字构成的四个字构成的 n 位符号串位符号串 A=a不出现的不出现的n 位符号串位符号串 B=b不出现的不出现的n 位符号串位符号串 C=c不出现的不出现的n 位符号串位符号串 2福
14、建农林大学离散数学课程组福建农林大学离散数学课程组372023-8-302.8 本章总结本章总结 1、乘法原理和加法原理的基本含义；、乘法原理和加法原理的基本含义；2、r-排列，全排列，环形排列，全排列，环形r排列，环排列，排列，环排列，r-组合组合的基本概念，它们之间关系和相应的计算公式；的基本概念，它们之间关系和相应的计算公式；3、容斥原理和鸽笼原理的基本概念及正确使用；、容斥原理和鸽笼原理的基本概念及正确使用；福建农林大学离散数学课程组福建农林大学离散数学课程组382023-8-30习题类型习题类型（1）计算题：计算题：涉及排列数与组合数的计算，利用涉及排列数与组合数的计算，利用容斥原理
15、的计算；容斥原理的计算；（2）证明题：证明题：涉及对鸽笼原理的应用。涉及对鸽笼原理的应用。福建农林大学离散数学课程组福建农林大学离散数学课程组392023-8-30作业作业第第44页页 17,21预习预习:第第3章章 命题逻辑命题逻辑p 经常不断地学习,你就什么都知道。你知道得越多,你就越有力量p Study Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will Be写在最后感谢聆听感谢聆听不足之处请大家批评指导不足之处请大家批评指导Please Criticize And Guide The Please Criticize And Guide The ShortcomingsShortcomings结束语结束语讲师讲师：XXXXXX XXXXXX XXXX年年XXXX月月XXXX日日
