《容斥原理.ppt》由会员分享，可在线阅读，更多相关《容斥原理.ppt（35页珍藏版）》请在三一文库上搜索。
1、第三章 容斥原理与鸽巢原理,3.1 容斥原理 3.2 鸽巢原理,3.1 容斥原理,容斥原理 有禁区的排列 广义容斥原理,1. 容斥原理,已学过的：如加法法则，母函数方法等；,两个计数原理：容斥原理和Polya计数定理。,例1 求不超过20的正整数中2或3的倍数的个数。,2的倍数：2，4，6，8，10，12，14，16，18，20。共10个；,3的倍数是：3，6，9，12，15，18。共6个；,答案是10+6=16个吗？,否！因为6，12，18在两类中重复计数，应减去，,故答案是：16-3=13。,对于求两个有限集合A和B的并集的元素数目：,定理1,即具有性质A或B的元素的个数等于具有性质A的元
2、素个数和具有性质B的元素个数的和，减去同时具有性质A和B的元素个数。,定理2,例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理、化学的22人；同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？,令A、B、C分别为修数学、物理、化学的学生集合。,即学校共有336名学生。,类似的，对于四个集合有：,规律1：n个集合取1,2,n个做交集(所有可能)；,规律2：正负号交叉出现。,对于一般的n个有限集合：,定理3,又因为 所以有：,这两个公式就是容斥原理，分别针对并集和交集
3、。,例3 求从1到500的整数中能被3或5除尽的数的个数。,令A、B分别表示1到500的整数中能被3、5除尽的数的集合，则,因此能被3或5除尽的数的个数为：,例4 求由abcdef这六个字符组成的全排列中不允许出现ace和df图象的排列数。,令A、B分别表示出现ace、df图象的排列的集合。,而全集的元素个数为|U|=6!，,A中是出现ace图象的排列，即ace作为一个元素参加排列，因此有|A|=4!。,类似有|B|=5!，|AB|=3！。,因此满足条件的排列数为：,例5 求4个x，3个y，2个z组成的全排列中不允许出现xxxx，yyy和zz图象的排列数。,令ABC表示出现xxxx、yyy、z
4、z图象的排列的集合。,A中的排列是把xxxx作为一个元素参加排列，注意有3个y和2个z，因此|A|=6!/(3!2!)=60。,类似有|B|=7!/(4!2!)=105， |C|=8!/(4!3!)=280， |AB|=4!/2!=12，|BC|=6!/4!=30，|AC|=5!/3!=20, |AB C |=3!=6，|U|=9!/(4!3!2!)=1260。,因此满足条件的排列数为：,例6 求由abcd这4个字符构成的n位符号串中，a、b、c都至少出现一次的数目。,令A、B、C分别表示不出现a、b、c的符号串的集合。,A中不出现a，即符号串的每一位只能取bcd之一，有三种选择，因此|A|=
5、3n。,类似有|B|=|C|= 3n ， |AB|=|BC|=|AC|= 2n，|AB C |= 1n=1，|U|= 4n。,因此满足条件的符号串的数目为：,例7 用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。,令Ai (i=1,2,3,4,5)分别表示出现以上五个单词之一的排列的集合。,A1中的集合是把dog作为一个元素参加排列，因此有|A1|=24!。,类似有：|A2|=|A3|=24!， |A4|=|A5|=22! 。,由于dog和god不能同时出现，所以|A1A2|=0。,由于dog和gum可以以dogu
6、m的方式出现，所以有|A1A3|=22!。,类似有：|A1A4|=0， |A1A5|=0。,类似有：|A2A3|=0，|A2A4|=20!， |A2A5|=20!，,|A3A4|=20!， |A3A5|=20!， |A4A5|=19!。,因此满足条件的排列数为：,例8 欧拉函数y(n)，是指小于n且与n互素的正整数的个数。,令Ai (i=1,2,k)分别表示1到n这n个整数中pi的倍数组成的集合。,则显然有|U|=n，|Ai|=n/pi。,注意到所有的素数互不相同，所以|AiAj|=n/(pi pj)。,类似有：|AiAjAk|=n/(pi pj pk)。,设n的因数分解为：,其中p1,pk是
7、互不相同的素数。,其他的都可以依此类推。,因此小于n且与n互素的正整数的个数为：,例如60=2235，所以,即比60小且与60互素的数有16个： 1，7，11，13，17, 19, 23，29，31，37，41，43，47，49，53，59。,例9 错排问题，是指1到n每个元素都不在自己原来位置上的排列的数目。,令Ai (i=1,2,n)表示元素i在位置i的排列的集合。,则显然有|U|=n!，|Ai|=(n-1)!。,类似有：|AiAj|=(n-2)!， |AiAjAk|=(n-3)!，,因此n个元素的错排数为：,例10 第二类Stirling数，是指m个不同的球放到n个相同的盒子里，且无一空
8、盒的方案数。,令Ai (i=1,2,n)表示第i个盒子为空的放法的集合。,则显然有|U|=nm，|Ai|=(n-1)m。,类似有：|AiAj|=(n-2)m， |AiAjAk|=(n-3)m，,因此第二类Stirling数为：,先考虑盒子都不相同的情形。,即：,例11 求方程x1+x2+x3=15的非负整数解的数目。,这个问题相当于15个相同的球放入3个不同的盒子的不同方案数，为C(15+3-1,15)=C(17,2)。,令U为全体非负整数解，A1为其中x15的整数解，A2为其中x26的整数解，A3为其中x37的整数解。,则|U|=C(17,2)。A1相当于求线性方程,(x1+6)+x2+x3
9、=15,类似有：|A2|=C(8+3-1,8)=C(10,2)，,但如果加上条件 呢？,的非负整数解，其个数为|A1|=C(9+3-1,9)=C(11,2)。,|A3|=C(7+3-1,8)=C(9,2)。,A1A2相当于求线性方程,(x1+6)+(x2+7)+x3=15,类似有：|A1A3|=C(3,2)， |A2A3|=C(2,2)。,因此方程满足条件 的非负整数解数目为：,的非负整数解，| A1A2 |=C(2+3-1,2)=C(4,2)。,A1A2A3相当于求线性方程,(x1+6)+(x2+7)+(x3+8)=15,的非负整数解，|A1A2A3 |=0。,例12 n对夫妻问题围圆桌而坐
10、，所有夫妻都相邻的方案数为：(n-1)!2n。,令Ai (i=1,2,n) 表示第i对夫妻相邻的方案的集合。,易有：|Ai|=2(2n-2)!，,|AiAj|=22(2n-3)!，,因此n对夫妻都不相邻的方案数为：,所有夫妻都不相邻的方案数呢？,|AiAj An |=2n(n-1)!，,2. 有禁区的排列,先看一个例子：设对于1234的排列P=P1P2P3P4，规定P13，P21,4，P32,4，P42。,这样的排列对应于有禁区的布子，即左图中有斜线的格子表示禁区，禁区内不能布子。,这就是所谓有禁区的排列。,为了求解有禁区的排列问题，除了容斥原理外，还需要另一个工具：棋盘多项式。,n个不同元素
11、的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行、列中有且仅有一个棋子。,如左图对应于41352。,可以把棋盘的形状推广到任意形状，布子规定同上。,令rk(C)表示k个棋子布到棋盘C上的方案数。,设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。,则显然有：rk(C) = rk-1(Ci ) + rk(Ce )。,定义：称 为对应于棋盘C的棋盘多项式。,约定对任何棋盘C，r0(C)=1。,注意到rk(C) = rk-1(Ci ) + rk(Ce )，因此有,另外，如果C由相互分离的C1和C2两部分组成，则,于是有,利用定义和这两个公
12、式可以计算出棋盘多项式。,=x(1+ x)2+(1+2x)2=1+5x+6x2+x3;,=x(1+ x)(1+2x)+(1+2x)(1+3x+x2)=1+6x+10x2+4x3。,下面回到有禁区的排列问题，有如下的定理：,定理：设rk是k个棋子布入禁区的方案数，则有禁区的布子(即禁区内不能布子)方案数为：,例13 现有1234四名工人，ABCD四项工作，要求1不干B，2不干BC，3不干CD，4不干D。问有多少种安排方案？,如左图，斜线区域表示禁区。,方案数为：4!-63!+102!-41!=4。,例14 再解错排问题。,对应于棋盘上对角线格子为禁区的布子问题。,棋盘多项式为：,即：rk(C)=
13、C(n,k)。,因此错排方案数为：,3. 广义容斥原理,例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理、化学的22人；同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？,若把问题改为“单修一门数学的学生有多少？”“只修一门课的学生有多少？”“只修两门课的学生有多少？”呢？,仍然用A、B、C分别表示修数学、物理、化学的学生的集合。,类似有,因此,同样的方法还可以得到：,设与性质1,2,n相关的元素有N个，设Ai表示具有性质i的元素的集合。引进记号：,b(m)表示刚
14、好具有m个性质的元素的个数。,利用这些记号，上面的两个公式可以写成：,b(1)=a(1)-2a(2)+3a(3)；,b(2)=a(2)-3a(3)。,一般的我们有如下的结论：,定理(广义容斥原理)：,特别的，当m=0时，,这实际就是前面介绍过的容斥原理的两个公式中的第二个(求集合交集的元素个数)。,例15 某校有12个教师，已知教数学的有8位，教物理的有6位，教化学的5位；数理5位，数化4位，理、化3位；数理化3位。问教其他课的有几位？只教一门的有几位？只教两门的有几位？,令A1, A2, A3分别表示教数学物理化学的教师的集合。,则有：a(0)12，a(1)|A1|+|A2|+|A3|8+6
15、+519; a(2)|A1A2|+ |A1A3|+|A2A3|12； a(3)|A1A2A3|3；,因此教其他课，只教一门，只教两门的分别为：,b(0)=a(0)-a(1)+a(2)-a(3)=2；,b(1)=a(1)-2a(2)+3a(3)=4；,b(2)=a(2)-3a(3)=3。,例16 错排问题的推广：从1到n这n个整数中取r个进行排列，得到a1a2ar。要求其中刚好有k个数满足ai=i。,这样的错排数用D(n,r,k)来表示。,例如，3个中取2个的排列数有P(3,2)=6个，其中,令Ai表示满足ai=i的排列的集合，则,D(3,2,0)= 3， 21 31 23,D(3,2,1)= 2， 13 32,D(3,2,2)= 1， 12,因此有：,