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