《信息竞赛中的容斥原理问题》由会员分享,可在线阅读,更多相关《信息竞赛中的容斥原理问题(61页珍藏版)》请在金锄头文库上搜索。
1、容斥原理和鸽巢原理1 容斥原理引论 例 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, 容斥原理,容斥原理研究有限集合的交或并 的计数。 DeMorgan定理 论域U,补集,有, 容斥原理,(a),(b),证:(a)的证明。 设 ,则 相当于 和 同时成立,亦即,(1), 容斥原理,反之,若,故,(2),由(1)和(2)得,(b)的证明和(a)类似,从略., 容斥
2、原理,DeMogan定理的推广:设,证明:只证(a). N=2时定理已证。 设定理对n是正确的,即假定:, 容斥原理,正确,即定理对n+1也是正确的。, 容斥原理,2 容斥原理,最简单的计数问题是求有限集合A和B的并的元素数目。显然有,即具有性质A或B的元素的个数等于具, 容斥原理,有性质A和B的元素个数。,U,B,A, 容斥原理, 容斥原理,证 若AB=,则 | AB |= |A| + |B| | A | A ( BB) | (AB)(AB)| AB | + | AB | ( 1 ) 同理 | B | | BA | + | BA | ( 2 ) | AB |(A( BB)(B(AA)| |(
3、AB)(AB)(BA)(BA)| | AB| + |AB | + | BA| ( 3 ), 容斥原理,( 3 ) ( 1 ) ( 2 ) 得 | AB | A | B | | AB| + |AB | + | BA|( | AB | + | AB | )( | BA | + | BA | ) | AB | | AB | A | + | B | AB |, 容斥原理, 容斥原理,A,B,C, 容斥原理,例 一个学校只有三门课程:数学、物理、化学。已知修这三门课的学生分别有170、130、120人;同时修 数学、物理两门课的学生45人;同时修数学、化学的20人;同时修物理化学的22人。同时修三门的3
4、人。问这学 校共有多少学生?, 容斥原理,令:M为修数学的学生集合;P 为修物理的学生集合;C 为修化学的学生集合;, 容斥原理,即学校学生数为336人。, 容斥原理,同理可推出:,利用数学归纳法可得一般的定理:, 容斥原理,定理 设(n,k)是1,n的所有k- 子集的集合, 则|Ai | = (1)k-1 | Ai |证 对n用归纳法。n=2时,等式成立。假设对n - 1,等式成立。对于n有, 容斥原理,n,i=1,k=1,n,I(n,k),iI, 容斥原理,I(n-1,k),I(n-1,k),iI, 容斥原理,I(n,k),I(n-1,k-1),I(n-1,k),此定理也可表示为:,(4)
5、, 容斥原理,证:用数学归纳法证明。 已知 n=2时有,设 n-1时成立,即有:, 容斥原理, 容斥原理, 容斥原理, 容斥原理, 容斥原理, 容斥原理, 容斥原理, 容斥原理,其中N是集合U的元素个数,即不属于 A的元素个数等于集合的全体减去属于 A的元素的个数。一般有:, 容斥原理,(5),容斥原理指的就是(4)和(5)式。, 容斥原理,例,例1 求a,b,c,d,e,f六个字母的全排列 中不允许出现ace和df图象的排列数。解:设A为ace作为一个元素出现的 排列集,B为 df作为一个元素出现的 排列集, 为同时出现ace、df的 排列数。, 例,根据容斥原理,不出现ace和df的排列数
6、 为:,=6!- (5!+4!)+3!=582, 例,例2 求从1到500的整数中能被3或5 除尽的数的个数。解: 令A为从1到500的整数中被3除 尽的数的集合,B为被5除尽的数的集合, 例,被3或5除尽的数的个数为,例3 求由a,b,c,d四个字母构成的位符号串中,a,b,c,d至少出现一次的符号 串数目。, 例,解:令A、B、C分别为n位符号串中 不出现a,b,c符号的集合。由于n位符号串中每一位都可取a, b,c,d四种符号中的一个,故不允许 出现a的n位符号串的个数应是, 例,a,b,c至少出现一次的n位符号串集 合即为, 例,例4。求不超过120的素数个数。,因 ,故不超过120的
7、合数必然是2、3、5、7的倍数,而且不超过120的合数的因子不可能都超过11。设 为不超过120的数 的倍数集, =2,3,5,7。, 例, 例, 例, 例, 例,注意:27并非就是不超过120的素数个数,因为这里排除了2,3,5,7着四个数,又包含了1这个非素数。2, 3,5,7本身是素数。故所求的不超过 120的素数个数为:27+4-1=30, 例,例5。用26个英文字母作不允许重复的 全排列,要求排除dog,god,gum, depth,thing字样的出现,求满足这些 条件的排列数。解:所有排列中,令:, 例, 例,出现dog字样的排列,相当于把dog作 为一个单元参加排列,故,类似有
8、:,由于god,dog不可能在一个排列中同时出现,故:,类似:, 例,由于gum,dog可以在dogum字样中同时 出现,故有:,类似有god和depth可以在godepth字样 中同时出现,故,god和thing可以在thingod字样中同时 出现,从而, 例, 例,由于god、depth、thing不可以同时出 现,故有:,其余多于3个集合的交集都为空集。, 例,故满足要求的排列数为:, 例,例6。求完全由n个布尔变量确定的布 而函数的个数。解:设,布尔函数类为:,由于n个布尔变量 的不 同的真值表数目与 位2进制数数目相同,故为 个。根据容斥原理,满足条件的函数数目为:, 例, 例, 例
9、,这10个布尔函数为: x1x2,x1x2,x1x2, x1x2, x1x2,x1x2,x1x2, x1x2, (x1x2)(x1x2), (x1x2)(x1x2),4 错排问题,n个元素依次给以标号1,2,n。 N个元素的全排列中,求每个元素都不 在自己原来位置上的排列数。设 为数 在第 位上的全体排列,=1,2,n。因数字 不能动, 因而有:, 例, 错排问题,每个元素都不在原来位置的排列数为, 错排问题,例1。数1,2,9的全排列中,求 偶数在原来位置上,其余都不在原来位 置的错排数目。解:实际上是1,3,5,7,9五个数 的错排问题,总数为:, 错排问题,例2. 在8个字母A,B,C,D,E,F,G,H的全 排列中,求使A,C,E,G四个字母不在原来 上的错排数目。,8个字母的全排列中,令 分别表A,C,E,G在原来位置上的排列,则错排数为:, 错排问题, 错排问题,例3。求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列 数。,解:8个字母中只有4个不在原来位置 上,其余4个字母保持不动,相当于4个 元素的错排,其数目为, 错排问题,故8个字母的全排列中有4个不在原来 位置上的排列数应为:C(8,4)9=630, 错排问题,