1、2022-8-5计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-8-5计算机应用技术研究所计算机应用技术研究所2第第1 1章章 集合与计数集合与计数（下）（下）2022-8-52022-8-5集合的基本知识集合的基本知识1 1 可数集与不可数集可数集与不可数集2 2高级计数技术高级计数技术4 4 基本计数技术基本计数技术3 3&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所4基本计数技术基本计数技术&基本计数技术基本计数技
2、术J 加法原理与乘法原理加法原理与乘法原理4 容斥原理与鸽笼原理容斥原理与鸽笼原理4 排列计数与组合计数排列计数与组合计数2022-8-5计算机应用技术研究所计算机应用技术研究所6&加法原理加法原理假定假定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 t2022-8-5计算机应用技术研究所计算机应用技
3、术研究所7&乘法原理乘法原理12t12tn n n n n n&基本计数技术基本计数技术4 加法原理与乘法原理加法原理与乘法原理J 容斥原理与鸽笼原理容斥原理与鸽笼原理4 排列计数与组合计数排列计数与组合计数2022-8-5计算机应用技术研究所计算机应用技术研究所9&基本容斥原理基本容斥原理UA BABABA-BA-BB-AB-A【定理定理】设设A A和和B B是任意有限是任意有限集合，有：集合，有：|AB|=|A|AB|=|A|B|B|AB|AB|【推论推论】设设U U为全集，为全集，A A，B B是任意是任意有限集合，有：有限集合，有：ABU(AB)AB2022-8-5计算机应用技术研究所
4、计算机应用技术研究所10&例例 题题【例例】在在2020个大学生中，有个大学生中，有1010人爱好音人爱好音乐，有乐，有8 8人爱好美术，有人爱好美术，有6 6人既爱好音乐人既爱好音乐又爱好美术。问：又爱好美术。问：（1 1）爱好音乐或美术的学生有多少？）爱好音乐或美术的学生有多少？（2 2）既不爱好音乐又不爱好美术的学）既不爱好音乐又不爱好美术的学生有多少？生有多少？2022-8-5计算机应用技术研究所计算机应用技术研究所11&基本容斥原理基本容斥原理【定理定理】设设A,BA,B和和C C是任意有限集合，有：是任意有限集合，有：AABBC=(A+B+C)-(AC=(A+B+C)-(AB+AB
5、+AC+BC+BC)+AC)+ABBC C【推论推论】设设U U为全集，为全集，A A，B B和和C C是任意有限是任意有限集合，有：集合，有：AABBC=U-(A+B+C)C=U-(A+B+C)+(A+(AB+AB+AC+BC+BC)-AC)-ABBC C2022-8-5计算机应用技术研究所计算机应用技术研究所12&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所13&广义容斥原理广义容斥原理【定理定理】设设A A1 1,A,A2 2,A,An n是任意是任意n n个有限集合，则：个有限集合，则：【推论推论】设设U U为全集，为全集，A A1 1,A,A2 2,A,An n
6、是任意是任意n n个有限集个有限集合，则合，则2022-8-5计算机应用技术研究所计算机应用技术研究所14&例例 题题【例例】2424名科技人员中，会英、日、德、法语的分名科技人员中，会英、日、德、法语的分别为别为1313、5 5、1010和和9 9人，同时会英语、日语的有人，同时会英语、日语的有2 2人，人，同时会英语和德语、同时会英语和法语、同时会德同时会英语和德语、同时会英语和法语、同时会德语和法语两种语言的均为语和法语两种语言的均为4 4人，会日语的人既不会法人，会日语的人既不会法语也不会德语。试求：语也不会德语。试求：(1)(1)同时会英、德、法语的人数为多少？同时会英、德、法语的人
7、数为多少？(2)(2)只会一种语言的人数各为多少？只会一种语言的人数各为多少？2022-8-5计算机应用技术研究所计算机应用技术研究所15&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所16&鸽笼原理鸽笼原理2022-8-5计算机应用技术研究所计算机应用技术研究所17&鸽笼原理鸽笼原理2022-8-5计算机应用技术研究所计算机应用技术研究所18&鸽笼原理鸽笼原理鸽笼原理（鸽笼原理（Pigeonhole PrinciplePigeonhole Principle）又称）又称为抽屉原理、鸽舍原理，是指如下定理：为抽屉原理、鸽舍原理，是指如下定理：【定理定理】(鸽笼原理鸽笼原理)
8、若有若有n+1n+1只鸽子住进只鸽子住进n n个鸽笼，则个鸽笼，则鸽笼鸽笼2 2只鸽子。只鸽子。2022-8-5计算机应用技术研究所计算机应用技术研究所19&注意点注意点 （1 1）鸽笼原理仅提供了）鸽笼原理仅提供了存在性证明存在性证明；（2 2）使用鸽笼原理，必须能够）使用鸽笼原理，必须能够正确识别正确识别鸽子鸽子(对象对象)和和鸽巢鸽巢(某类要求的特征某类要求的特征)，并且，并且能够计算出鸽子数和鸽巢数。能够计算出鸽子数和鸽巢数。2022-8-5计算机应用技术研究所计算机应用技术研究所20&例例 题题【例例】抽屉里有抽屉里有3 3双不一样的手套，从中双不一样的手套，从中至少取多少只，才能保
9、证配成一双？至少取多少只，才能保证配成一双？【例例】证明从证明从1 1到到1010中任意选出六个数，中任意选出六个数，其中必有有两个数的和是其中必有有两个数的和是1111。2022-8-5计算机应用技术研究所计算机应用技术研究所21&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所22&增强鸽笼原理增强鸽笼原理【定理定理】若有若有n n只鸽子住进只鸽子住进m(nm)m(nm)个鸽笼，个鸽笼，则则存在一个存在一个鸽笼鸽笼至少住至少住进进 只只鸽子。这里，鸽子。这里，表示小于等于表示小于等于x x的最大的最大整数。整数。n-1n-1+1+1m mx x 2022-8-5计算机应用
10、技术研究所计算机应用技术研究所23&例例 题题【例例】如果一个图书馆里如果一个图书馆里3030本离散数学本离散数学书共有书共有1200312003页，那么必然有一本离散数页，那么必然有一本离散数学书至少有学书至少有401401页。页。【例例】如果离散数学课有如果离散数学课有5 5个可能的成绩个可能的成绩ABCDEABCDE，那么一个班最少有多少名学生才，那么一个班最少有多少名学生才能保证至少能保证至少6 6名学生得到相同的分数。名学生得到相同的分数。2022-8-5计算机应用技术研究所计算机应用技术研究所24&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所25&例例 题题【
11、例例】(拉姆齐理论拉姆齐理论)假定一组有假定一组有6 6个人，个人，任两个人或者是朋友或者是敌人。证明任两个人或者是朋友或者是敌人。证明在这组人中要么存在在这组人中要么存在3 3个人彼此都是朋友，个人彼此都是朋友，要么存在要么存在3 3个人彼此都是敌人。个人彼此都是敌人。2022-8-5计算机应用技术研究所计算机应用技术研究所26&例例 题题【分析分析】令令A A是这是这6 6人中任意一个，则由广义鸽巢原人中任意一个，则由广义鸽巢原理知：组里其他理知：组里其他5 5人中至少有人中至少有3 3人是人是A A的朋友，或至少的朋友，或至少有有3 3个人是个人是A A的敌人。的敌人。若是前一种情况，假
12、定若是前一种情况，假定B B、C C、D D是是A A的朋友。如果这的朋友。如果这3 3人中有人中有2 2人也是朋友，那么这人也是朋友，那么这2 2人和人和A A构成彼此是朋友构成彼此是朋友的的3 3人组。人组。否则，否则，B B、C C、D D构成彼此为敌人的构成彼此为敌人的3 3人组。人组。对于后一种情况，即当对于后一种情况，即当A A存在存在3 3个或更多的敌人时，个或更多的敌人时，可以用类似方法处理。可以用类似方法处理。&基本计数技术基本计数技术4 加法原理与乘法原理加法原理与乘法原理4 容斥原理与鸽笼原理容斥原理与鸽笼原理J 排列计数与组合计数排列计数与组合计数&排列与组合排列与组合
13、无重复排列无重复排列无重复组合无重复组合可重复排列可重复排列可重复组合可重复组合2022-8-5计算机应用技术研究所计算机应用技术研究所29&无重复排列无重复排列 【定义定义从含从含n n个不同元素的集合个不同元素的集合S S中有序选取中有序选取的的r r个元素叫做个元素叫做S S的一个的一个r-r-排列，不同的排列总排列，不同的排列总数记为数记为P(n,r)P(n,r)。如果。如果r=nr=n，则称这个排列为，则称这个排列为S S的一个的一个全排列，简称为全排列，简称为S S的排列。的排列。显然，当显然，当rnrn时，时，P(n,r)=0P(n,r)=0。2022-8-5计算机应用技术研究所
14、计算机应用技术研究所30&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所31&环形排列环形排列A AE EF FB BD DC C2022-8-5计算机应用技术研究所计算机应用技术研究所32&环形排列环形排列【定义定义n n个人围坐圆桌上，有个人围坐圆桌上，有(n-1)(n-1)！种不同！种不同的坐法，我们称这种排列为的坐法，我们称这种排列为，从，从n n个人中个人中选出选出r r个人为圆桌而坐称为个人为圆桌而坐称为。【定理定理含含n n个不同元素的集合的环形个不同元素的集合的环形r-r-排列数排列数Pc(n,r)Pc(n,r)是是c cP(n,r)n!P(n,r)n!P(
15、n,r)=P(n,r)=rrrr(n-r)!(n-r)!2022-8-5计算机应用技术研究所计算机应用技术研究所33&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所34&例例 题题求满足下列条件的排列数。求满足下列条件的排列数。(1)101)10个男孩和个男孩和5 5个女孩个女孩站成一排站成一排，无两无两个女孩相邻。个女孩相邻。(2)10(2)10个男孩和个男孩和5 5个女孩个女孩站成一圆圈站成一圆圈，无无两个女孩相邻两个女孩相邻。2022-8-5计算机应用技术研究所计算机应用技术研究所35&无重复组合无重复组合【定义定义】从含有从含有n n个不同元素的集合个不同元素的集合
16、S S中无序选中无序选取的取的r r个元素叫做个元素叫做S S的一个的一个r-r-组合组合，不同的组合，不同的组合总数记为总数记为C(n,r)C(n,r)。【定理定理】对满足对满足0 r n0 r n的正整数的正整数n n和和r r有有n!n!C(n,r)=C(n,r)=r!(n-r)!r!(n-r)!2022-8-5计算机应用技术研究所计算机应用技术研究所36&例例 题题 【例例】一副一副5252张的扑克牌含有张的扑克牌含有4 4种花色：梅花、方片、红桃和种花色：梅花、方片、红桃和黑桃；各有黑桃；各有1313种点数，分别为种点数，分别为A,2-10,J,Q,KA,2-10,J,Q,K。试求满
17、足。试求满足下列条件的组合数。下列条件的组合数。（1 1）5 5张牌称为一手牌，一手牌共有多少种可能的组合？张牌称为一手牌，一手牌共有多少种可能的组合？（2 2）一手牌）一手牌5 5张都是同一花色，有多少种可能的组合？张都是同一花色，有多少种可能的组合？（3 3）一手牌有）一手牌有3 3张牌点数相同，另外两张牌点数相同，共张牌点数相同，另外两张牌点数相同，共有多少种可能的组合？有多少种可能的组合？2022-8-5计算机应用技术研究所计算机应用技术研究所37&例例 题题 在在1 1到到300300中选三个不同的数，并且这中选三个不同的数，并且这三个数之和能被三个数之和能被3 3整除，问有多少种方
18、式？整除，问有多少种方式？多少个多少个1212位二进制串包含位二进制串包含 a)a)恰好恰好3 3个个1 1？b)b)至多至多3 3个个1 1？c)c)至少至少3 3个个1 1？d)0d)0的个数与的个数与1 1的个数相等？的个数相等？2022-8-5计算机应用技术研究所计算机应用技术研究所38&可重复排列可重复排列重集的概念所谓重集，就是在指定范围内满足给定条件、且所谓重集，就是在指定范围内满足给定条件、且允许多个相同对象同时出现的所有对象构成的总允许多个相同对象同时出现的所有对象构成的总体，重集中每个对象仍然称为该集合的元素，重体，重集中每个对象仍然称为该集合的元素，重集中相同元素的个数称
19、为元素的重数。集中相同元素的个数称为元素的重数。2022-8-5计算机应用技术研究所计算机应用技术研究所39&可重复排列可重复排列2022-8-5计算机应用技术研究所计算机应用技术研究所40&可重复排列可重复排列2022-8-5计算机应用技术研究所计算机应用技术研究所41&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所42&可重复排列可重复排列2022-8-5计算机应用技术研究所计算机应用技术研究所43&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所44&可重复组合可重复组合 【例例】从包含苹果、橙子、和梨的框子里选从包含苹果、橙子、和梨的框子里选4 4
20、个水果。如果不关心选择水果的顺序，且只关个水果。如果不关心选择水果的顺序，且只关心水果的类型，那么当框中每类水果至少有心水果的类型，那么当框中每类水果至少有4 4个个时有多少种选法？时有多少种选法？2022-8-5计算机应用技术研究所计算机应用技术研究所45&有重复组合有重复组合共有共有1515种方式：种方式：4 4个苹果；个苹果；4 4个橙子；个橙子；4 4个梨；个梨；3 3个苹果，个苹果，1 1个橙子；个橙子；3 3个苹果，个苹果，1 1个梨；个梨；3 3个梨，个梨，1 1个苹果；个苹果；3 3个橙子，个橙子，1 1个梨；个梨；3 3个梨，个梨，1 1个苹果；个苹果；3 3 个梨，个梨，1
21、 1个橙子；个橙子；2 2个苹果，个苹果，2 2个橙子；个橙子；2 2个苹果，个苹果，2 2个梨；个梨；2 2个橙子，个橙子，2 2个梨个梨2 2个苹果，个苹果，1 1个橙子，个橙子，1 1个梨；个梨；2 2个橙子，个橙子，1 1个苹果，个苹果，1 1个梨个梨2 2个梨，个梨，1 1个苹果，个苹果，1 1个橙子。个橙子。这个解是从这个解是从3 3个元素的集合个元素的集合 苹果、梨、橙子苹果、梨、橙子 中允许重复的中允许重复的4 4组合数。组合数。2022-8-5计算机应用技术研究所计算机应用技术研究所46&有重复组合有重复组合 【例例】从包含从包含1 1美元、美元、2 2美元、美元、5 5美元
22、、美元、1010美元、美元、2020美元、美元、5050美元及美元及100100美元的钱袋中美元的钱袋中选选5 5张纸币，有多少种方式？假定不管纸币张纸币，有多少种方式？假定不管纸币被选的次序，同种币值的纸币都是不加区被选的次序，同种币值的纸币都是不加区别的，并且至少每张纸币有别的，并且至少每张纸币有5 5张。张。2022-8-5计算机应用技术研究所计算机应用技术研究所47&有重复组合有重复组合 假设一个零钱盒子有假设一个零钱盒子有7 7个隔间，每个保存一种纸个隔间，每个保存一种纸币，如下图所示。这些隔间被币，如下图所示。这些隔间被6 6块隔板分开，每选择块隔板分开，每选择1 1张张纸币就在相
23、应的隔间里放置纸币就在相应的隔间里放置1 1个标记。针对选择个标记。针对选择5 5张纸币张纸币的的3 3种不同方式给出了这种对应，其中的竖线表示种不同方式给出了这种对应，其中的竖线表示6 6个隔个隔板，星表示板，星表示5 5张纸币。张纸币。2022-8-5计算机应用技术研究所计算机应用技术研究所48&有重复组合有重复组合2022-8-5计算机应用技术研究所计算机应用技术研究所49&有重复组合有重复组合 选择选择5 5张纸币的方法数对应了安排张纸币的方法数对应了安排6 6条竖线和条竖线和5 5颗星颗星的方法数。因此，选择的方法数。因此，选择5 5张纸币的方法数就是从张纸币的方法数就是从1111个
24、可个可能的位置选能的位置选5 5颗星位置的方法数。颗星位置的方法数。这对应了从含这对应了从含1111个物体的集合中无序地选择个物体的集合中无序地选择5 5个物个物体的方法数，可以有体的方法数，可以有C(11,5)C(11,5)种方法种方法.因此从因此从7 7类纸币的袋中选择类纸币的袋中选择5 5张纸币的方式数有：张纸币的方式数有：11!(11,5)4625!6!C2022-8-5计算机应用技术研究所计算机应用技术研究所50&有重复组合有重复组合【分析分析】用用n-1n-1条竖线标记条竖线标记n n个不同的单元。每当集合的第个不同的单元。每当集合的第i i个元素出现个元素出现在组合中，第在组合中
25、，第i i个单元就包含一颗星。例如，个单元就包含一颗星。例如，4 4种元素集合的一个种元素集合的一个6 6组合组合用用3 3条竖线和条竖线和6 6颗星表示。例如颗星表示。例如*|*|*表示表示2 2个第一元素、个第一元素、1 1个第二元素、个第二元素、0 0个第三元素和个第三元素和3 3个第四元素的组合。个第四元素的组合。因此，包含因此，包含n-1n-1条竖线和条竖线和r r颗星的每一个不同的表对应了颗星的每一个不同的表对应了n n元素集合元素集合的一个允许重复的的一个允许重复的r r组合。组合。这种表的个数就是这种表的个数就是C(n-1+r,r),C(n-1+r,r),因为每个表对应了从包含
26、因为每个表对应了从包含r r颗星颗星和和n-1n-1条竖线的条竖线的n-1+rn-1+r个位置来放个位置来放r r颗星的一种选择。颗星的一种选择。2022-8-5计算机应用技术研究所计算机应用技术研究所51&有重复组合有重复组合【例例】方程方程x x1 1+x+x2 2+x+x3 3=11 =11 有多少个解？其中有多少个解？其中x x1 1,x,x2 2,x,x3 3是非负整数。是非负整数。【分析分析】一个解对应了从一个解对应了从3 3元素集合中选元素集合中选1111个元素的方式，个元素的方式，以使得以使得x1x1选自第一类，选自第一类，x2x2选自第二类，选自第二类，x3x3选自第三类。选
27、自第三类。因此，解的个数等于因此，解的个数等于3 3元素集合允许重复的元素集合允许重复的1111组合数：组合数：13 12(311,11)(13,11)(13,2)781 2CCC2022-8-5计算机应用技术研究所计算机应用技术研究所522022-8-52022-8-5 集合的基本知识集合的基本知识1 1 可数集与不可数集可数集与不可数集2 2基本计数技术基本计数技术3 3 高级计数技术高级计数技术4 4&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所54高级计数技术高级计数技术&高级计数技术高级计数技术 如果求解问题在本质上具有动态演化动态演化性质性质，或
28、者问题比较复杂比较复杂必须考察其演变历史，那么，对这类问题的计数必须考察问题状态的演变过程和规律，此时基于静态思维的基本计数技术基于静态思维的基本计数技术就不能满足要求。&高级计数技术高级计数技术J 递推关系计数法递推关系计数法4 递推关系的求解递推关系的求解4 生成函数计数法生成函数计数法&递推关系计数法递推关系计数法&例例 题题&例例 题题&例例 题题&例例 题题&例例 题题&高级计数技术高级计数技术4 递推关系计数法递推关系计数法J 递推关系的求解递推关系的求解4 生成函数计数法生成函数计数法&递推关系求解递推关系求解两种基本方法：两种基本方法：第一、迭代求解法第二、特征根求解法&迭代求解法迭代求解法&例例 题题&例例 题题&特征根求解法特征根求解法&特征根求解法特征根求解法&特征方程与特征根特征方程与特征根&特征根求解法特征根求解法&特征根求解法特征根求解法&例例 题题&例例 题题&高级计数技术高级计数技术4 递推关系计数法递推关系计数法4 递推关系的求解递推关系的求解J 生成函数计数法生成函数计数法&生成函数的概念生成函数的概念&基本原理基本原理&例例 题题&例例 题题&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所81
