清华离散数学(第2版)：912省公开课一等奖全国示范课微课金奖PPT课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,9,章 容斥原理,1,第1页,第,9,章 容斥原理,9.1,容斥原理,9.2,对称筛公式及其应用,2,第2页,9.1,容斥原理,9.1.1,容斥原理基本形式,容斥原理,容斥原理推论,9.1.2,容斥原理应用,计数多重集,r,-,组合数,计数限制条件元素数,计算欧拉函数值,证实组合恒等式,3,第3页,容斥原理基本形式,定理,9.1,设,S,为有穷集，,P,1,P,2,P,m,是,m,种性质，,A,i,是,S,中含有性质,P,i,元素组成子集，是,A,i,相对于,S,补集，,i,=1,2,m,.,则S,中不含有性质,P,1,P,2,P,m,元,素数为,4,第4页,证实,证实方法：数学归纳法、组合分析,证 组合分析,.,若,x,不含有任何性质，则对等式右边贡献为：,1,0+0,0+(,1),m,0=1,若,x,含有,n,条性质，,1,n,m,则对等式右边贡献为：,5,第5页,推论,推论,S,中最少含有其中一条性质元素数为,证,6,第6页,应用,计数多重集,r-,组合数,例,1,求多重集,B,=3,a,4,b,5,c,10-,组合数,解：令,S,=,x,|,x,是,a,b,c,任意重复,10-,组合,A,1,=,x,|,x,S,，,x,中最少含,4,个,a,=,x,|,x,是,a,b,c,任意,6-,组合,A,2,=,x,|,x,S,，,x,中最少含,5,个,b,=,x,|,x,是,a,b,c,任意,5-,组合,A,3,=,x,|,x,S,，,x,中最少含,6,个,c,=,x,|,x,是,a,b,c,任意,4-,组合,7,第7页,计数多重集,r-,组合数（续）,注意：性质设定与要求条件相反,性质彼此独立，不一样性质元素计数互不影响,8,第8页,应用,计数限制条件元素数,例,2,求不超出,120,素数个数,解：,112=121,，不超出,120,合数素因子可能是,2,3,5,7,，,S,=,x|x,Z,1,x,120,|,S,|=120,被,2,3,5,7,整除集合分别为,A,1A,2,A,3,A,4,：,|,A,1,|=60,，,|,A,2,|=40,，,|,A,3,|=24,，,|,A,4,|=17,|,A,1,A,2,|=20,|,A,1,A,3,|=12,|,A,1,A,4,|=8,|,A,2,A,3,|=8,|,A,2,A,4,|=5,|,A,3,A,4,|=3,|,A,1,A,2,A,3,|=4,|,A,1,A,2,A,4,|=2,|,A,1,A,3,A,4,|=1,|,A,2,A,3,A,4,|=1,，,|,A,1,A,2,A,3,A,4,|=0,N,=27+3.,9,第9页,应用,欧拉函数值,例,3,计算欧拉函数值,(,n,).,欧拉函数,：小于,n且与,n,互素自然数个数,解,n,素因子分解式,:,A,i,=,x,|0,x,n,1,，且,p,i,整除,x,，,10,第10页,应用,证实交织和恒等式,证：,S,=1,2,n,A,=1,2,m,，计数,S,中包含,A,r-,子集,.,P,j,:,在,S,r-,子集中不包含,j,j,=1,2,m,例,4,证实,11,第11页,9.2.1,对称筛公式及其应用,对称筛公式,错位排列计数,9.2.2,棋盘多项式与有限制条件排列,布棋方案与有限制条件排列对应,棋盘多项式及其性质,布棋方案数计数,9.2,对称筛公式及其应用,12,第12页,对称筛公式,令,|,S,|=,N,对称筛公式,:(,容斥原理特殊情况,),使用条件：,不一样性质对计数影响对称,.,各性质计数是独立,.,13,第13页,应用,错位排列计数,错位排列数记作,D,n,设,S,为,1,2,n,排列集合，,P,i,是其中,i,在第,i,位性质，,i,=1,2,n,.,14,第14页,错位排列实例,例,1,8,个字母,A,B,C,D,E,F,G,H,全排列中，使得,4,个,字母不在原来位置排列数,.,解：,4,个字母错排数为,15,第15页,错位排列性质,3,.,D,n,为偶数当且仅当,n,为奇数,.,4.,当,n,充分大时，,D,n,/,n,!,趋向于,1/,e,.,证实思绪：,使用组合分析，按照第,1,位是什么数分类计数,.将,n,!,个排列按照出现错位个数分类计数,归纳证实,将,D,n,值代入取极限,16,第16页,排列与布棋方案,一个棋盘由大小相同正方形方格构,成，一个方格中允许放入一个棋子,.,在向棋盘布棋时，要求任何两个棋子,既不能布在棋盘同一行，也不能布,在同一列上,.,排列,i,1,i,2,i,n,表示,:,第一行棋子放在第,i,1,列,第二行棋子放在第,i,2,列,第,n,行棋子放在第,i,n,列,步棋方案,排列：,2 5 1 3 6 4,17,第17页,排列与,n,个棋子在,n,n,棋盘布棋方案一一对应,位置有限制排列与有禁区步棋方案一一对应,布棋方案与棋盘多项式,r,k,(,C,),表示,k,个棋子在棋盘,C,上布棋方案数，则称,为,棋盘多项式,位置受限排列：,2 5 1 3 6 4,普通表示：,i,1,i,2,i,6,i,j,j,j,=1,2,6,18,第18页,棋盘多项式性质,C,i,：去掉某个给定方格所在行和列之后剩下棋盘,C,l,：去掉某个给定方格之后剩下棋盘,C,1,和,C,2,表示两个分离棋盘,则不难证实：,19,第19页,简单棋盘多项式结果,20,第20页,有禁区排列,限制一些数字不能出现在一些位置排列，对应于有禁,区放棋方案,.,有下述计数定理,.,定理,9.2,C,是,n,n,含有给定禁区棋盘，禁区对应于,1,2,n,元素在排列中不允许出现位置，则这种有,禁区排列数为,中,r,i,是,i,个棋子布置到禁区方案数,使用条件：,棋盘为,n,n,小禁区,21,第21页,定理证实,证,不考虑禁区限制，不带编号棋子布棋方案数,:,n,!,，,考虑棋子编号，布棋方案数,:,n,!,n,!,P,j,:,第,j,个棋子落入禁区性质，,j,=1,2,n,给定,1,个棋子落入禁区方案数,:,N,1,=,r,1,(,n,1)!(,n,1)!,给定,2,个棋子落入禁区方案数,:,N,2,=2!,r,2,(,n,2)!(,n,2)!,给定,k,个棋子落入禁区方案数,:,N,k,=,k,!,r,k,(,n,k,)!(,n,k,)!,n,个棋子落入禁区方案数：,N,n,=,n,!,r,n,0!0!,22,第22页,定理证实（续）,带编号棋子不落入禁区方案数,:,N,0,不带编号棋子不落入禁区方案数,:,N,二者关系：,N,0,=,N,n,!,23,第23页,应用实例,工作分配,N,=4!,6,3!+10,2 4,=24 36+20 4=4,解：禁区棋盘多项式为,依据定理,9.2,得,例,2,G,L,W,Y 4,位工作人,员，,A,B,C,D,为,4,项工作,.,每个人不能从事工作如,图中棋盘禁区所表示,.,问有,多少种分配方案？,24,第24页,应用实例,错排问题,例,3,错位排列禁区是主对角线上全部方格,关于禁区棋盘多项式以下：,25,第25页,