清华离散数学(第2版)：.ppt

1,第9章容斥原理,2,第9章容斥原理,9.1容斥原理9.2对称筛公式及其应用,3,9.1容斥原理,9.1.1容斥原理的基本形式容斥原理容斥原理的推论9.1.2容斥原理的应用计数多重集的r-组合数计数限制条件的元素数计算欧拉函数的值证明组合恒等式,4,容斥原理的基本形式,定理9.1设S为有穷集，P1,P2,Pm是m种性质，Ai是S中具有性质Pi的元素构成的子集，是Ai相对于S的补集，i=1,2,m.则S中不具有性质P1,P2,Pm的元素数为,5,证明,证明方法：数学归纳法、组合分析证组合分析.若x不具有任何性质，则对等式右边贡献为：10+00+(1)m0=1若x具有n条性质，1nm,则对等式右边的贡献为：,6,推论,推论S中至少具有其中一条性质的元素数为,证,7,应用计数多重集的r-组合数,例1求多重集B=3a,4b,5c的10-组合数解：令S=x|x是a,b,c任意重复的10-组合A1=x|xS，x中至少含4个a=x|x是a,b,c的任意6-组合A2=x|xS，x中至少含5个b=x|x是a,b,c的任意5-组合A3=x|xS，x中至少含6个c=x|x是a,b,c的任意4-组合,8,计数多重集的r-组合数（续）,注意：性质的设定与要求条件相反性质彼此独立，不同性质的元素计数互不影响,9,应用计数限制条件的元素数,例2求不超过120的素数个数解：112=121，不超过120的合数的素因子可能是2,3,5,7，S=x|xZ,1x120,|S|=120被2,3,5,7整除的集合分别为A1,A2,A3,A4：|A1|=60，|A2|=40，|A3|=24，|A4|=17|A1A2|=20,|A1A3|=12,|A1A4|=8,|A2A3|=8,|A2A4|=5,|A3A4|=3|A1A2A3|=4,|A1A2A4|=2,|A1A3A4|=1,|A2A3A4|=1，|A1A2A3A4|=0,N=27+3.,10,应用欧拉函数的值,例3计算欧拉函数的值(n).欧拉函数：小于n且与n互素的自然数的个数解n的素因子分解式:Ai=x|0xn1，且pi整除x，,11,应用证明交错和的恒等式,证：S=1,2,n,A=1,2,m，计数S中包含A的r-子集.Pj:在S的r-子集中不包含j,j=1,2,m,例4证明,12,9.2.1对称筛公式及其应用对称筛公式错位排列计数9.2.2棋盘多项式与有限制条件的排列布棋方案与有限制条件排列的对应棋盘多项式及其性质布棋方案数的计数,9.2对称筛公式及其应用,13,对称筛公式,令,|S|=N,对称筛公式:(容斥原理的特殊情况)使用条件：不同性质对计数的影响对称.各性质计数是独立的.,14,应用错位排列计数,错位排列数记作Dn,设S为1,2,n的排列的集合，Pi是其中i在第i位的性质，i=1,2,n.,15,错位排列实例,例18个字母A,B,C,D,E,F,G,H的全排列中，使得4个字母不在原来位置的排列数.,解：4个字母的错排数为,16,错位排列的性质,3.Dn为偶数当且仅当n为奇数.,4.当n充分大时，Dn/n!趋向于1/e.,证明思路：使用组合分析，按照第1位是什么数分类计数.将n!个排列按照出现错位的个数分类计数归纳证明将Dn的值代入取极限,17,排列与布棋方案,一个棋盘由大小相同的正方形方格构成，一个方格中允许放入一个棋子.在向棋盘布棋时，要求任何两个棋子既不能布在棋盘的同一行，也不能布在同一列上.,排列i1i2in表示:第一行的棋子放在第i1列第二行的棋子放在第i2列第n行的棋子放在第in列,步棋方案,排列：251364,18,排列与n个棋子在nn棋盘的布棋方案一一对应位置有限制的排列与有禁区的步棋方案一一对应,布棋方案与棋盘多项式,rk(C)表示k个棋子在棋盘C上的布棋方案数，则称,为棋盘多项式,位置受限的排列：251364一般表示：i1i2i6ijj,j=1,2,6,19,棋盘多项式的性质,Ci：去掉某个给定方格所在的行和列之后剩余棋盘Cl：去掉某个给定方格之后剩余棋盘C1和C2表示两个分离的棋盘则不难证明：,20,简单棋盘多项式的结果,21,有禁区的排列,限制某些数字不能出现在某些位置的排列，对应于有禁区的放棋方案.有下述计数定理.定理9.2C是nn的具有给定禁区的棋盘，禁区对应于1,2,n的元素在排列中不允许出现的位置，则这种有禁区的排列数为中ri是i个棋子布置到禁区的方案数使用条件：棋盘为nn,小禁区,22,定理证明,证不考虑禁区限制，不带编号棋子的布棋方案数:n!，考虑棋子编号，布棋方案数:n!n!Pj:第j个棋子落入禁区的性质，j=1,2,n给定的1个棋子落入禁区的方案数:N1=r1(n1)!(n1)!给定的2个棋子落入禁区的方案数:N2=2!r2(n2)!(n2)!给定的k个棋子落入禁区的方案数:Nk=k!rk(nk)!(nk)!n个棋子落入禁区的方案数：Nn=n!rn0!0!,23,定理证明（续）,带编号的棋子不落入禁区的方案数:N0不带编号的棋子不落入禁区的方案数:N两者关系：N0=Nn!,24,应用实例工作分配,N=4!63!+1024=2436+204=4,解：禁区的棋盘多项式为,根据定理9.2得,例2G,L,W,Y4位工作人员，A,B,C,D为4项工作.每个人不能从事的工作如图中棋盘的禁区所示.问有多少种分配方案？,25,应用实例错排问题,例3错位排列的禁区是主对角线上的所有方格关于禁区的棋盘多项式如下：,