《信息竞赛中的容斥原理问题》由会员分享，可在线阅读，更多相关《信息竞赛中的容斥原理问题（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
