《[工学]离散数学-第02章-计数问题》由会员分享，可在线阅读，更多相关《[工学]离散数学-第02章-计数问题（39页珍藏版）》请在金锄头文库上搜索。
1、,离 散 数 学,2019年8月18日星期日,2019/8/18,第一篇 预备知识,第2章 计数问题,2019/8/18,2.0 内容提要,2019/8/18,2.1 本章学习要求,2019/8/18,2.2.1 乘法原理,如果一些工作需要 t 步完成，第一步有 n1 种不同的选择，第二步有 n2 种不同的选择， ，第 t步有 nt 种不同的选择，那么完成这项工作所有可能的选择种数为：,2019/8/18,2.2.2 加法原理,假定 X1, X2, , Xt 均为集合，第 I 个集合 Xi 有 ni个元素。如 X1, X2, , Xt 为两两不相交的集合，则可以从 X1, X2, , Xt 中
2、选出的元素总数为： n1 + n2 + + nt。,即集合 X1X2Xt 含有 n1 + n2 + + nt 个元素。,2019/8/18,2.3 排列与组合,从某个集合中有序的选取若干个元素的问题，称为排列问题。,2019/8/18,2.3.1 排列问题,定义2.3.1 从含 n 个不同元素的集合S中有序选取的 r 个元素叫做 S 的一个 r -排列，不同的r -排列总数记为 P(n, r)。 如果r = n，则称这个排列为 S 的一个全排列，简称为 S 的排列。 显然，当 rn 时，P(n, r) = 0。,2019/8/18,例2.3.1,解 从含3个元素的不同集合S中有序选取2个元素的
3、排列总数为6种。 如果将这3个元素记为A、B和C，则6个排列为 AB, AC, BA, BC, CB, CA。,从含3个不同元素的集合S中有序选取2个元素的排列总数。,2019/8/18,定理2.3.1,对满足 rn 的正整数 n 和 r 有,2019/8/18,推论2.3.2,n个不同元素的排列共有n！种，其中,2019/8/18,练习: P44 3,4,6,3. 一枚硬币抛4次并且每次抛掷结果被记录下来。 问可能有多少种不同的正面和反面的序列? 答: 24=16 种。 4. 某人有8件衬衫、4条裤子、5双鞋， 全套衣服用有多少种可能的选择？ 答：845160 种。 6. P(4,4)= 4
4、32 1= 24 P(6,5)= 654 32= 720， P(7,2)= 76= 42。,2019/8/18,环形 r-排列,例2.3.3 6个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。 解: 6个人围坐在圆桌上，有 6!/6=120 种不同的坐法。,n个人围坐圆桌上，有 (n-1)！种不同的坐法，我们称这种排列为环排列; 从 n 个人中选出 r 个人围圆桌而坐，称为 环形r -排列。,2019/8/18,定理2.3.3,含 n 个不同元素的集合的环形 r-排列数 Pc(n,r) 是 (2.3.3),2019/8/18,例2.3.4,求满足下列条件的排列数。 (1
5、)10个男孩和5个女孩站成一排，无两个女孩相邻。 (2)10个男孩和5个女孩站成一圆圈, 无两个女孩相邻. 解 (1) 10个男孩的全排列为10!，5个女孩插入到10个 男孩形成的11个空格中的插入方法数为 P(11,5)。 根据乘法原理，10个男孩和5个女孩站成一排，没有两个女孩相邻的排列数为： 10! P(11,5) =（10!11!)/6! 。,2019/8/18,例2.3.4 解（续）,(2) 根据定理2.3.3，10个男孩站成一个圆圈的环排列数为 9!， 5个女孩插入到10男孩形成的10个空中的插入方法数为 P(10,5)。 根据乘法原理，10个男孩和5个女孩站成一个圆圈，没有两个女
6、孩相邻的排列法为： 9! P(10,5) =（9!10!)/5!。,2019/8/18,2.3.2 组合问题,定义2.3.2 从含有n个不同元素的集合S中无序选取的r个元素叫做S的一个r -组合，不同的组合总数记为 C(n,r)。 当 nr = 0 时，规定 C(n,r) = 1。 显然，当 rn 时，C(n,r) = 0。,2019/8/18,定理2.3.4,对满足 0 r n 的正整数 n 和 r 有，,2019/8/18,例2.3.5,一副52张的扑克牌含有4种花色：梅花、方片、红桃和黑桃；各有13种点数，分别为A, 210, J, Q, K。试求满足下列条件的组合数。 （1）手中持有5
7、张牌称为一手牌，一手牌共有多少种可能的组合？ 解: 有 C(52,5) 种可能的组合。,2019/8/18,（2）一手牌中的5张都是同一花色，共有多少种可能的组合？,解： 分两步进行： 一选花色，有 C(4,1) 种， 二在选定的花色中选5张牌，有 C(13,5) 种。 据乘法原理，有 C(4,1)C(13,5) 种。,2019/8/18,（3）一手牌中有3张牌点数相同，另外两张牌点数相同，共有多少种可能的组合？,解：该组合问题需四步完成： 一选第一个点数， 有 C(13,1) 种； 二选第二个点数， 有 C(12,1) 种： 三选第一点数的3张牌，有 C(4,3) 种； 四选第二点数的2张牌
8、，有 C(4,2) 种。 根据乘法原理，共有 C(13,1)C(12,1)C(4,3)C(4,2) = 131246 = 3744 种选法。,2019/8/18,2.4 容斥原理与鸽笼原理,容斥原理是研究若干有限集合交与并的计数问题。 鸽笼原理则是研究某些特定对象的存在性问题。,2019/8/18,2.4.1 容斥原理,定义2.4.1 所谓容斥，是指我们计算某类物体的数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补偿。这种原理称为容斥原理，又称为包含排斥原理。,2019/8/18,定理2.4.1,设A和B是任意有限集合，有 |AB| = |A|B|AB
9、|。 分析 由图2.4.1容易看出， 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是任意有限集合，则,2019/8/18,三个集合的情形,定理2.4.3 设 A, B 和 C 是任意三个有限集合, 有 (2.4.3) 推论2.4.4 设 U 为全集, A, B 和 C 是任意有限集合，则 (2.4.4),2019/8/18,例2.4.2,调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数
10、学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人对三种课程都选修。问 （1）调查中三种课程都不选的学生有多少？ （2）调查中只选修计算机科学课程的学生有多少？,2019/8/18,例2.4.2 解,设A、B、C分别表示选修数学课程，计算机课程和商贸课程的人构成的集合， 则三种课程都不选的学生集合为 , 只选修计算机科学课程学生的集合为 。 |U|=260, |A|=64, |B|=94, |C|=58, |AC|=28, |AB|=26, |BC|=22, |ABC|=14,2019/8/18,例2.4.2 解（续）,（1）利用容斥原理得 （2）,2019/8/18,容斥原理的推
11、广,定理2.4.5 设A1, A2, , An是任意n个有限集合，则 推论2.4.6 设U为全集，A1, A2, , An是任意n个有限集合，则,2019/8/18,2.4.2 鸽笼原理(也称抽屉原理),定理2.4.7 若有n+1只鸽子住进n个鸽笼，则有一个鸽笼至少住进2只鸽子。 证明(反证法) 假设每个鸽笼至多住进1只鸽子，则n个鸽笼至多住进n只鸽子，这与有n+1只鸽子矛盾。故存在一个鸽笼至少住进2只鸽子。,注意：（1）鸽笼原理仅提供了存在性证明； （2）使用鸽笼原理，必须能够正确识别鸽子和鸽笼，并且能够计算出鸽子数和鸽巢数。,2019/8/18,例2.4.4,抽屉里有3双手套，问从中至少取
12、多少只，才能保证配成一双？ 答：4只。,2019/8/18,例2.4.5 设1到10中任意选出六个数, 那么其中有两个数的和是11。,证明 (1) 构造5个鸽笼： A1=1,10，A2=2,9，A3=3,8， A4=4,7，A5=5,6 (2) 选出的6个数为鸽子. 根据鸽笼原理，所选出的6个数中一定有两个数属于同一个集合，这两个数的和为11。,2019/8/18,定理2.4.5,若有n只鸽子住进 m (nm) 个鸽笼，则存在一个鸽笼至少住进 +1只鸽子。这里， 表示小于等于 x 的最大整数。,2019/8/18,例2.7.2 某一制造铁盘的工厂，由于设备和技术的原因只能将生产盘子的重量控制在
13、100克到100.1克之间。现需要制成重量相差不超过0.005克的两铁盘来配制一架天平，问该工厂至少要生产多少铁盘才能确保得到一对符合要求的铁盘。,2.7 计数问题的应用,2019/8/18,例2.7.2 解,将铁盘按重量分类， 所有100克到100.005克的分为第一类； 100.005克到100.01克的分为一类； 100.01克到100.015克的又为一类，.， 最后，100.095克到100.1克为一类，共计20类， 由鸽笼原理知，若该工厂生产21个铁盘，那么就能得知有两个铁盘属于同一类，因而它们之间的重量差将不超过0.005克。,2019/8/18,练习: P44 16, 20,把5
14、个顶点放到边长为2的正方形中, 则其中至少有两个点的距离小于等于 。 证法: 将边长为2的正方形分成4块边长为1的正方形。 在由 a,b,c,d 四个字构成的 n 位符号串中, 求 a,b,c 至少出现一次的符号串的数目。 解法：全集U = 由 a,b,c,d 四个字构成的 n 位符号串 A = a不出现的n 位符号串 B = b不出现的n 位符号串 C = c不出现的n 位符号串 ,2019/8/18,2.8 本章总结,1、乘法原理和加法原理的基本含义； 2、r-排列，全排列，环形r排列，环排列，r-组合的基本概念，它们之间关系和相应的计算公式； 3、容斥原理和鸽笼原理的基本概念及正确使用；,2019/8/18,习题类型,（1）计算题：涉及排列数与组合数的计算，利用容斥原理的计算； （2）证明题：涉及对鸽笼原理的应用。,2019/8/18,作业,第44页 17, 21 预习: 第3章 命题逻辑,
