信息竞赛中的容斥原理问题.ppt
容斥原理和鸽巢原理容斥原理和鸽巢原理 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)类似，从略类似，从略.容斥原理容斥原理DeMogan定理的推广：设 证明证明：只证(a).N=2时定理已证。设定理对n是正确的，即假定：容斥原理容斥原理正确即定理对n+1也是正确的。容斥原理容斥原理2 容斥原理容斥原理 最简单的计数问题是求有限集合A和B的并的元素数目。显然有即具有性质A或B的元素的个数等于具(1)定理定理：容斥原理容斥原理有性质A和B的元素个数。UBA 容斥原理容斥原理 容斥原理容斥原理证证若AB=，则|AB|=|A|+|B|A|A(BB)|(AB)(AB)|AB|+|AB|(1)同理|B|BA|+|BA|(2)|AB|(A(BB)(B(AA)|(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|定理：定理：(2)容斥原理容斥原理 容斥原理容斥原理ABC 容斥原理容斥原理 例例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？容斥原理容斥原理令：令：M为修数学的学生集合；P 为修物理的学生集合；C 为修化学的学生集合；容斥原理容斥原理即学校学生数为336人。容斥原理容斥原理同理可推出：利用数学归纳法可得一般的定理：容斥原理容斥原理 定理定理设(n,k)是1,n的所有k-子集的集合,则|Ai|=(1)k-1|Ai|证证对n用归纳法。n=2时，等式成立。假设对n-1，等式成立。对于n有 容斥原理容斥原理ni=1k=1n 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)容斥原理容斥原理 证：证：用数学归纳法证明。已知 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!-(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的合数必然是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作为一个单元参加排列，故类似有：由于god,dog不可能在一个排列中同 时出现，故：类似：类似：例例 由于gum,dog可以在dogum字样中同时出现，故有：类似有god和depth可以在godepth字样中同时出现，故 god和thing可以在thingod字样中同时出现，从而 例例 例例 由于god、depth、thing不可以同时出现，故有：其余多于3个集合的交集都为空集。例例 故满足要求的排列数为：例例 例例6。求完全由n个布尔变量确定的布而函数的个数。解：解：设 布尔函数类为：由于n个布尔变量 的不同的真值表数目与 位2进制数数目相同，故为 个。根据容斥原理，满足条件的函数数目为：例例 例例 例例这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 错排问题错排问题
