组合数学课件--第三章第一节容斥原理.ppt

《组合数学课件--第三章第一节容斥原理.ppt》由会员分享，可在线阅读，更多相关《组合数学课件--第三章第一节容斥原理.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.1 De Morgan3.1 De Morgan定理定理 1 1 3.2 3.2 容斥原理容斥原理 1 1 3.3 3.3 容斥原理举例容斥原理举例 1 1 3.4 3.4 棋盘多项式与有限制的排列棋盘多项式与有限制的排列 2 2 3.5 3.5 有禁区的排列有禁区的排列 2 2 3.6 3.6 广义的容斥原理广义的容斥原理 3 3 3.7 3.7 广义容斥原理的应用广义容斥原理的应用 3 3 2.8 2.8 第二类第二类StirlingStirling数的展开式数的展开式 1 1 2.9 2.9 欧拉函数欧拉函数(n)1(n)1 2.10

2、 n 2.10 n对夫妻问题对夫妻问题 3 3*2.11 *2.11 MobiusMobius反演定理反演定理 2.12 2.12 鸽巢原理鸽巢原理 4 4 2.13 2.13 鸽巢原理举例鸽巢原理举例 4 4 2.14 2.14 鸽巢原理的推广鸽巢原理的推广 4 4*2.15 Ramsey*2.15 Ramsey数数 1 3.1 De Morgan定理定理如果如果如果如果加法法则加法法则:2德摩根德摩根(De Morgan)定理：定理：若若A和和B是集合是集合U的子集，的子集，3.1 De Morgan定理定理3 德摩根德摩根(De Morgan)定理的推广：定理的推广：设设A1,A2,An

3、是是U的子集，则：的子集，则：3.1 De Morgan定理定理4 3.2 容斥原理容斥原理 一、容斥原理的两个基本公式一、容斥原理的两个基本公式加法法则是指加法法则是指:5定理定理3-1 3.2 容斥原理容斥原理 6定理定理3.1证明：证明：根据：根据：3.2 容斥原理容斥原理 7 例例3.1：一个学校只有数学，物理，化学：一个学校只有数学，物理，化学3门门课课。已知修这。已知修这3门课的学生人数分别有门课的学生人数分别有170,130,120人；同时修数学、物理两门课的学生人；同时修数学、物理两门课的学生有有45人；同时修数学、化学的有人；同时修数学、化学的有20人；同时修物人；同时修物理

4、、化学的有理、化学的有22人；同时修三门课的学生有人；同时修三门课的学生有3人，人，问这个学校共有多少学生。问这个学校共有多少学生。解：令解：令M为修数学课的学生集合；为修数学课的学生集合；P为修物为修物理课的学生集合；理课的学生集合；C为修化学课的学生集合，按为修化学课的学生集合，按照已知条件：照已知条件：3.2 容斥原理容斥原理 8假定学校的学生至少要学一门课程。假定学校的学生至少要学一门课程。=170+130+120-45-20-22+3=336。3.2 容斥原理容斥原理 9定理定理3.2 设设A1,A2,An是有限集合，则是有限集合，则 3.2 容斥原理容斥原理 10 设设N N为全集

5、为全集U U的元素个数，那么不属于的元素个数，那么不属于A A的元的元素数目等于集合的全体减去属于素数目等于集合的全体减去属于A A的元素个数。的元素个数。记作：记作：按照德摩根定理按照德摩根定理 3.2 容斥原理容斥原理 11 3.2 容斥原理容斥原理 12二、容斥原理的两种形式二、容斥原理的两种形式:3.2 容斥原理容斥原理 形式形式1：13 3.2 容斥原理容斥原理 形式形式2：*14 3.3 容斥原理举例容斥原理举例 例例3.2 3.2 求由求由a,b,c,da,b,c,d这这4 4个字符构成的个字符构成的n n位符号串中，位符号串中，a,b,ca,b,c都至少出现一次的符号串都至少出

6、现一次的符号串的数目。的数目。解解(用指数型母函数用指数型母函数)15 例例3.2 3.2 求由求由a,b,c,da,b,c,d这这4 4个字符构成的个字符构成的n n位符号串中，位符号串中，a,b,ca,b,c都至少出现一次的符号串都至少出现一次的符号串的数目。的数目。设设A A为为n n位符号中不出现位符号中不出现a a符号的集合。符号的集合。不加限制的不加限制的n n位符号串的个数应是位符号串的个数应是4 4n n个。个。解解(用容斥原理用容斥原理)设设B,CB,C分别为分别为n n位符号中不出现位符号中不出现b,cb,c符号的集合。符号的集合。3.3 容斥原理举例容斥原理举例 16 3

7、.3 容斥原理举例容斥原理举例 17 3.3 容斥原理举例容斥原理举例 18 例例3.3 3.3 求求a,b,c,d,e,fa,b,c,d,e,f这这6 6个字母的全排列个字母的全排列中不允许出现中不允许出现aceace和和dfdf图像的排列数。图像的排列数。解：解：设设A A1 1为出现为出现aceace图像的排列集，图像的排列集，A A2 2为出现为出现dfdf图图像的排列集。像的排列集。3.3 容斥原理举例容斥原理举例 不允许出现不允许出现aceace和和dfdf的排列数为：的排列数为：19 例例3.4 N=1,2,500,3.4 N=1,2,500,求求N N中至少能被中至少能被2,3

8、,52,3,5其中之一除尽的数的数目。其中之一除尽的数的数目。解：解：N N中能被中能被a,ba,b同时除尽的数的数目：同时除尽的数的数目：N N中被中被k k除尽的数的数目为：除尽的数的数目为：3.3 容斥原理举例容斥原理举例 设设m m为为a,ba,b的最小公倍数。的最小公倍数。20设设A A1 1,A,A2 2,A,A3 3分别表示分别表示N N中为中为2,3,52,3,5的倍数的集合。的倍数的集合。例例3.4 N=1,2,500,3.4 N=1,2,500,求求N N中至少能被中至少能被2,3,52,3,5其中之一除尽的数的数目。其中之一除尽的数的数目。3.3 容斥原理举例容斥原理举例

9、 21 3.3 容斥原理举例容斥原理举例 22例例3.5 3.5 求不超过求不超过120120的素数的个数。的素数的个数。因为因为11112 2=121,=121,因此不超过因此不超过120120的合数的质因子的合数的质因子必然有小于必然有小于1111的质数，也就是不超过的质数，也就是不超过120120的合数至的合数至少是少是2,3,5,72,3,5,7中之一的倍数，中之一的倍数，解：解：3.3 容斥原理举例容斥原理举例 23设设A Ai i为不超过为不超过120120的数同时又是的数同时又是i i的倍数的集合，的倍数的集合，i=2,3,5,7.i=2,3,5,7.3.3 容斥原理举例容斥原理

10、举例 24 3.3 容斥原理举例容斥原理举例 25注意：注意：2727包括了包括了1 1这个非素数，另外这个非素数，另外2,3,5,72,3,5,7本本身是素数没有计算在内，因此满足要求的素数身是素数没有计算在内，因此满足要求的素数是是27+4-1=3027+4-1=30个。个。3.3 容斥原理举例容斥原理举例 26设设Ai为第为第i个元素在原来位置上的排列数个元素在原来位置上的排列数错排问题错排问题 3.3 容斥原理举例容斥原理举例 27 3.3 容斥原理举例容斥原理举例 283.8 第二类司特林数展开式第二类司特林数展开式 将将n n个有标志的球放进个有标志的球放进m m个无区别的盒子，个

11、无区别的盒子，而且无一空盒，其方案数用而且无一空盒，其方案数用S(n,mS(n,m)来表示。来表示。考虑考虑n n个有标志的球，放进个有标志的球，放进m m个有区别个有区别的盒子，得到无一空盒的方案数。的盒子，得到无一空盒的方案数。m!S(n,mm!S(n,m)。*293.8 第二类司特林数展开式第二类司特林数展开式 A Ai i表示第表示第i i个盒为空个盒为空,其它盒任意的方案数，其它盒任意的方案数，i=1,2,mi=1,2,m。求求n n个有标志的球，放进个有标志的球，放进m m个有区别的盒子，个有区别的盒子，无一空盒的方案数。无一空盒的方案数。303.8 第二类司特林数展开式第二类司特

12、林数展开式31 n n个有标志的球，放进个有标志的球，放进m m个有区别的盒子，个有区别的盒子，无一空盒的方案数为：无一空盒的方案数为：3.8 第二类司特林数展开式第二类司特林数展开式*32 n n个有标志的球，放进个有标志的球，放进m m个无区别的盒个无区别的盒子，无一空盒的方案数为：子，无一空盒的方案数为：n n个有标志的球，放进个有标志的球，放进m m个有区别的盒子，个有区别的盒子，无一空盒的方案数为：无一空盒的方案数为：3.8 第二类司特林数展开式第二类司特林数展开式*33 欧拉函数欧拉函数(n)(n)为求小于为求小于n n且与且与n n互素的数的个互素的数的个数数.若若n n分解为不

13、同的素数分解为不同的素数p p1 1,p,p2 2,p pk k之积之积:求求(n)的表达式的表达式:令令N=1,2,nN=1,2,n中中p pi i的倍数的数的集合为的倍数的数的集合为A Ai i3.9 欧拉函数欧拉函数(n)343.9 欧拉函数欧拉函数(n)35*3.9 欧拉函数欧拉函数(n)36练习题练习题 解：设某甲与第解：设某甲与第i i会朋友相遇的会议集合会朋友相遇的会议集合为为A Ai i，i=1,2,3,4,5,6i=1,2,3,4,5,6。3.1 3.1 某甲参加一种会议某甲参加一种会议,会上有会上有6 6位朋友位朋友,某某甲和其中每一个人在会上各相遇甲和其中每一个人在会上各

14、相遇1212次次,每两个人各每两个人各相遇相遇6 6次次,每每3 3个人各相遇个人各相遇4 4次次,每每4 4个人各相遇个人各相遇3 3次次,每每5 5个人各相遇个人各相遇2 2次次,每每6 6个人各相遇个人各相遇1 1次次,1,1人也没遇人也没遇到的有到的有5 5次次,问某甲共参加几次会议。问某甲共参加几次会议。37练习题练习题 解：设某甲与第解：设某甲与第i i会朋友相遇的会议集合会朋友相遇的会议集合为为A Ai i，i=1,2,3,4,5,6i=1,2,3,4,5,6。3.1 3.1 某甲参加一种会议某甲参加一种会议,会上有会上有6 6位朋友位朋友,某某甲和其中每一个人在会上各相遇甲和其

15、中每一个人在会上各相遇1212次次,每两个人各每两个人各相遇相遇6 6次次,每每3 3个人各相遇个人各相遇4 4次次,每每4 4个人各相遇个人各相遇3 3次次,每每5 5个人各相遇个人各相遇2 2次次,每每6 6个人各相遇个人各相遇1 1次次,1,1人也没遇人也没遇到的有到的有5 5次次,问某甲共参加几次会议。问某甲共参加几次会议。=612-156+204-153+62-1=612-156+204-153+62-1 =72-90+80-45+12-1=28 =72-90+80-45+12-1=28共共3333次次383.62,3.62,一书架有一书架有m m层，分别放置层，分别放置m m类不同

16、种类的书，每层类不同种类的书，每层n n册，现将书架上的图书全部取出清理，清理过程要求不册，现将书架上的图书全部取出清理，清理过程要求不打乱所在的类别，试问：打乱所在的类别，试问：(a)ma)m类书全不在各自原来层次上的方案数有多少？类书全不在各自原来层次上的方案数有多少？同层还放同类的书同层还放同类的书,书可以不在原来的位置书可以不在原来的位置.(b)(b)每层的每层的n n本书都不在原来位置上的方案数等于多少？本书都不在原来位置上的方案数等于多少？同层还放同类的书同层还放同类的书,同类的书可不在原来层上同类的书可不在原来层上.(c)mc)m层书都不在原来层次，每层层书都不在原来层次，每层n

17、 n本书也不在原来位置上本书也不在原来位置上的方案数又是多少？的方案数又是多少？同层还放同类的书同层还放同类的书.习习 题题解解:设设39习习 题题*40 总结总结一、有限制的排列一、有限制的排列 对有重复的排列或无重复的排列，可以对一对有重复的排列或无重复的排列，可以对一个或多个元素的个或多个元素的出现次数出现次数进行限制，也可以对某进行限制，也可以对某些元素些元素出现的位置进行限制出现的位置进行限制，这两种情况统称为，这两种情况统称为有限制条件的排列。有限制条件的排列。1 1、解决这些问题的工具有：、解决这些问题的工具有：(1)(1)、指数型母函数：、指数型母函数：(3)(3)、递推关系：

18、、递推关系：(2)(2)、容斥原理：、容斥原理：41(1)(1)指数型母函数指数型母函数 主要解决限制元素出现次数的排列主要解决限制元素出现次数的排列问题问题 例例1 求求1,3,5,7,9这这5个数字组成的个数字组成的n位数位数个数，要求其中个数，要求其中3出现的次数为偶数，其它出现的次数为偶数，其它数字出现的次数无限制。数字出现的次数无限制。总结总结42(2)(2)、容斥原理：、容斥原理：既可解决限制元素出现次数的问题，也能既可解决限制元素出现次数的问题，也能解决元素出现位置的问题解决元素出现位置的问题 典型特征是：问题能够化为集合问题：典型特征是：问题能够化为集合问题：例例2 2 求求a

19、,b,c,d,e,fa,b,c,d,e,f这这6 6个字母的全个字母的全排列中不允许出现排列中不允许出现abab和和dede图像的排列数。图像的排列数。总结总结43(3)(3)递推关系递推关系 既可解决限制元素出现次数的问题，也能解既可解决限制元素出现次数的问题，也能解决元素出现位置的问题决元素出现位置的问题 典型特征是：写出递推关系典型特征是：写出递推关系(4)(4)棋盘多项式棋盘多项式解决无重复排列元素出现位置的问题解决无重复排列元素出现位置的问题 例例3:3:甲乙丙丁甲乙丙丁4 4个人住店个人住店,有有4 4个房间个房间1,2,3,4,1,2,3,4,甲不住甲不住1,2,31,2,3号房

20、间号房间,乙不住乙不住2,3,42,3,4房间房间,丙不住丙不住1 1、4 4号房间号房间,丁不住丁不住1,2,41,2,4号房间号房间,求满足求满足要求的方案数。要求的方案数。总结总结44第第3章章 容斥原理与鸽巢原理容斥原理与鸽巢原理 3.1 De Morgan3.1 De Morgan定理定理 1 1 3.2 3.2 容斥原理容斥原理 1 1 3.3 3.3 容斥原理举例容斥原理举例 1 1 3.4 3.4 棋盘多项式与有限制的排列棋盘多项式与有限制的排列 2 2 3.5 3.5 有禁区的排列有禁区的排列 2 2 3.6 3.6 广义的容斥原理广义的容斥原理 3 3 3.7 3.7 广义容斥原理的应用广义容斥原理的应用 3 3 2.8 2.8 第二类第二类StirlingStirling数的展开式数的展开式 1 1 2.9 2.9 欧拉函数欧拉函数(n)1(n)1 2.10 n 2.10 n对夫妻问题对夫妻问题 3 3*2.11 *2.11 MobiusMobius反演定理反演定理 2.12 2.12 鸽巢原理鸽巢原理 4 4 2.13 2.13 鸽巢原理举例鸽巢原理举例 4 4 2.14 2.14 鸽巢原理的推广鸽巢原理的推广 4 4*2.15 Ramsey*2.15 Ramsey数数 45