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

1,第3章容斥原理与鸽巢原理,3.1DeMorgan定理13.2容斥原理13.3容斥原理举例13.4棋盘多项式与有限制的排列23.5有禁区的排列23.6广义的容斥原理33.7广义容斥原理的应用32.8第二类Stirling数的展开式12.9欧拉函数(n)12.10n对夫妻问题3*2.11Mobius反演定理2.12鸽巢原理42.13鸽巢原理举例42.14鸽巢原理的推广4*2.15Ramsey数,2,3.1DeMorgan定理,如果,如果,加法法则:,3,德摩根(DeMorgan)定理：若A和B是集合U的子集，,3.1DeMorgan定理,4,德摩根(DeMorgan)定理的推广：设A1,A2,An是U的子集，则：,3.1DeMorgan定理,5,3.2容斥原理,一、容斥原理的两个基本公式,加法法则是指:,6,定理3-1,3.2容斥原理,7,定理3.1,证明：,根据：,3.2容斥原理,8,例3.1：一个学校只有数学，物理，化学3门课。已知修这3门课的学生人数分别有170,130,120人；同时修数学、物理两门课的学生有45人；同时修数学、化学的有20人；同时修物理、化学的有22人；同时修三门课的学生有3人，问这个学校共有多少学生。,解：令M为修数学课的学生集合；P为修物理课的学生集合；C为修化学课的学生集合，按照已知条件：,3.2容斥原理,9,假定学校的学生至少要学一门课程。,=170+130+120-45-20-22+3=336。,3.2容斥原理,10,定理3.2设A1,A2,An是有限集合，则,3.2容斥原理,11,设N为全集U的元素个数，那么不属于A的元素数目等于集合的全体减去属于A的元素个数。记作：,按照德摩根定理,3.2容斥原理,12,3.2容斥原理,13,二、容斥原理的两种形式:,3.2容斥原理,形式1：,14,3.2容斥原理,形式2：,*,15,3.3容斥原理举例,例3.2求由a,b,c,d这4个字符构成的n位符号串中，a,b,c都至少出现一次的符号串的数目。,解(用指数型母函数),16,例3.2求由a,b,c,d这4个字符构成的n位符号串中，a,b,c都至少出现一次的符号串的数目。,设A为n位符号中不出现a符号的集合。,不加限制的n位符号串的个数应是4n个。,解(用容斥原理),设B,C分别为n位符号中不出现b,c符号的集合。,3.3容斥原理举例,17,3.3容斥原理举例,18,3.3容斥原理举例,19,例3.3求a,b,c,d,e,f这6个字母的全排列中不允许出现ace和df图像的排列数。,解：,设A1为出现ace图像的排列集，A2为出现df图像的排列集。,3.3容斥原理举例,不允许出现ace和df的排列数为：,20,例3.4N=1,2,500,求N中至少能被2,3,5其中之一除尽的数的数目。,解：,N中能被a,b同时除尽的数的数目：,N中被k除尽的数的数目为：,3.3容斥原理举例,设m为a,b的最小公倍数。,21,设A1,A2,A3分别表示N中为2,3,5的倍数的集合。,例3.4N=1,2,500,求N中至少能被2,3,5其中之一除尽的数的数目。,3.3容斥原理举例,22,3.3容斥原理举例,23,例3.5求不超过120的素数的个数。,因为112=121,因此不超过120的合数的质因子必然有小于11的质数，也就是不超过120的合数至少是2,3,5,7中之一的倍数，,解：,3.3容斥原理举例,24,设Ai为不超过120的数同时又是i的倍数的集合，i=2,3,5,7.,3.3容斥原理举例,25,3.3容斥原理举例,26,注意：27包括了1这个非素数，另外2,3,5,7本身是素数没有计算在内，因此满足要求的素数是27+4-1=30个。,3.3容斥原理举例,27,设Ai为第i个元素在原来位置上的排列数,错排问题,3.3容斥原理举例,28,3.3容斥原理举例,29,3.8第二类司特林数展开式,将n个有标志的球放进m个无区别的盒子，而且无一空盒，其方案数用S(n,m)来表示。,考虑n个有标志的球，放进m个有区别的盒子，得到无一空盒的方案数。,m!S(n,m)。,*,30,3.8第二类司特林数展开式,Ai表示第i个盒为空,其它盒任意的方案数，i=1,2,m。,求n个有标志的球，放进m个有区别的盒子，无一空盒的方案数。,31,3.8第二类司特林数展开式,32,n个有标志的球，放进m个有区别的盒子，无一空盒的方案数为：,3.8第二类司特林数展开式,*,33,n个有标志的球，放进m个无区别的盒子，无一空盒的方案数为：,n个有标志的球，放进m个有区别的盒子，无一空盒的方案数为：,3.8第二类司特林数展开式,*,34,欧拉函数(n)为求小于n且与n互素的数的个数.,若n分解为不同的素数p1,p2,pk之积:求(n)的表达式:,令N=1,2,n中pi的倍数的数的集合为Ai,3.9欧拉函数(n),35,3.9欧拉函数(n),36,*,3.9欧拉函数(n),37,练习题,解：设某甲与第i会朋友相遇的会议集合为Ai，i=1,2,3,4,5,6。,3.1某甲参加一种会议,会上有6位朋友,某甲和其中每一个人在会上各相遇12次,每两个人各相遇6次,每3个人各相遇4次,每4个人各相遇3次,每5个人各相遇2次,每6个人各相遇1次,1人也没遇到的有5次,问某甲共参加几次会议。,38,练习题,解：设某甲与第i会朋友相遇的会议集合为Ai，i=1,2,3,4,5,6。,3.1某甲参加一种会议,会上有6位朋友,某甲和其中每一个人在会上各相遇12次,每两个人各相遇6次,每3个人各相遇4次,每4个人各相遇3次,每5个人各相遇2次,每6个人各相遇1次,1人也没遇到的有5次,问某甲共参加几次会议。,=612-156+204-153+62-1=72-90+80-45+12-1=28,共33次,3.62,一书架有m层，分别放置m类不同种类的书，每层n册，现将书架上的图书全部取出清理，清理过程要求不打乱所在的类别，试问：(a)m类书全不在各自原来层次上的方案数有多少？同层还放同类的书,书可以不在原来的位置.(b)每层的n本书都不在原来位置上的方案数等于多少？同层还放同类的书,同类的书可不在原来层上.(c)m层书都不在原来层次，每层n本书也不在原来位置上的方案数又是多少？同层还放同类的书.,习题,解:设,40,习题,*,41,总结,一、有限制的排列,对有重复的排列或无重复的排列，可以对一个或多个元素的出现次数进行限制，也可以对某些元素出现的位置进行限制，这两种情况统称为有限制条件的排列。,1、解决这些问题的工具有：,(1)、指数型母函数：,(3)、递推关系：,(2)、容斥原理：,42,(1)指数型母函数,主要解决限制元素出现次数的排列问题,例1求1,3,5,7,9这5个数字组成的n位数个数，要求其中3出现的次数为偶数，其它数字出现的次数无限制。,总结,43,(2)、容斥原理：,既可解决限制元素出现次数的问题，也能解决元素出现位置的问题典型特征是：问题能够化为集合问题：,例2求a,b,c,d,e,f这6个字母的全排列中不允许出现ab和de图像的排列数。,总结,44,(3)递推关系,既可解决限制元素出现次数的问题，也能解决元素出现位置的问题典型特征是：写出递推关系,(4)棋盘多项式,解决无重复排列元素出现位置的问题,例3:甲乙丙丁4个人住店,有4个房间1,2,3,4,甲不住1,2,3号房间,乙不住2,3,4房间,丙不住1、4号房间,丁不住1,2,4号房间,求满足要求的方案数。,总结,45,第3章容斥原理与鸽巢原理,3.1DeMorgan定理13.2容