《组合数学课件第三章容斥原理和鸽巢原理》由会员分享，可在线阅读，更多相关《组合数学课件第三章容斥原理和鸽巢原理（151页珍藏版）》请在金锄头文库上搜索。
1、第三章 容斥原理和鸽巢原理 1 容斥原理引论 例 1，20中2或3的倍数的个数 解 2的倍数是：2，4，6，8，10，12，14，16，18，20。 10个,3.1 容斥原理引论,3的倍数是：3，6，9，12，15， 18。 6个 但答案不是10+6=16 个，因为6， 12，18在两类中重复计数，应减 去。故答案是：16-3=13,3.2 容斥原理,容斥原理研究有限集合的交或并 的计数。 DeMorgan定理 论域U，补集,有,3.2 容斥原理,(a),(b),证：(a)的证明。 设 ,则 相当于 和 同时成立，亦即,(1),3.2 容斥原理,反之，若,故,(2),由（1）和（2）得,(b)
2、的证明和（a)类似，从略.,3.2 容斥原理,DeMogan定理的推广：设,证明：只证(a). N=2时定理已证。 设定理对n是正确的，即假定：,3.2 容斥原理,正确,则,即定理对n+1也是正确的。,3.2 容斥原理,2 容斥原理,最简单的计数问题是求有限集合A和B的并的元素数目。显然有,即具有性质A或B的元素的个数等于具,3.2 容斥原理,有性质A和B的元素个数。,U,B,A,3.2 容斥原理,3.2 容斥原理,证 若AB=，则 | AB |= |A| + |B| | A | A ( BB) | | (AB)(AB)| | AB | + | AB | ( 1 ) 同理 | B | | BA
3、 | + | BA | ( 2 ) | AB |(A( BB)(B(AA)| |(AB)(AB)(BA)(BA)| | AB| + |AB | + | BA| ( 3 ),3.2 容斥原理,( 3 ) ( 1 ) ( 2 ) 得 | AB | A | B | | AB| + |AB | + | BA| ( | AB | + | AB | ) ( | BA | + | BA | ) | AB | | AB | A | + | B | AB |,3.2 容斥原理,3.2 容斥原理,A,B,C,3.2 容斥原理,例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、1
4、20人；同时修 数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学 校共有多少学生？,3.2 容斥原理,令：M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合；,3.2 容斥原理,即学校学生数为336人。,3.2 容斥原理,同理可推出：,利用数学归纳法可得一般的定理：,3.2 容斥原理,定理 设(n,k)是1,n的所有k-子集的集合, 则 证 对n用归纳法。n=2时，等式成立。 假设对n - 1，等式成立。对于n有,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,I(n,k),I(n-1,k-1),I(n-1,k
5、),此定理也可表示为：,(4),3.2 容斥原理,证：用数学归纳法证明。 已知 n=2时有,设 n-1时成立，即有：,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,其中N是集合U的元素个数，即不属于 A的元素个数等于集合的全体减去属于 A的元素的个数。一般有：,3.2 容斥原理,(5),容斥原理指的就是（4）和（5）式。,3.2 容斥原理,3 例,例1 求a,b,c,d,e,f六个字母的全排列 中不允许出现ace和df图象的排列数。 解：设A为ace作为一个元素出现的 排列集，B为 df作为一个元
6、素出现的 排列集， 为同时出现ace、df的 排列数。,3.3 例,根据容斥原理，不出现ace和df的排列数 为：,3.3 例,例2 求从1到500的整数中能被3或5 除尽的数的个数。 解： 令A为从1到500的整数中被3除 尽的数的集合，B为被5除尽的数的集合,3.3 例,被3或5除尽的数的个数为,3.3 例,例3 求由a,b,c,d四个字母构成的位符号串中，a,b,c，d至少出现一次的符号串数目。,解：令A、B、C分别为n位符号串中 不出现a，b，c符号的集合。 由于n位符号串中每一位都可取a， b，c，d四种符号中的一个，故不允许 出现a的n位符号串的个数应是,例3 求由a,b,c,d四
7、个字母构成的位符号串中，a,b,c至少出现一次的符号 串数目。,a，b，c至少出现一次的n位符号串集 合即为,3.3 例,例4。求不超过120的素数个数。,因 ，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。 设 为不超过120的数 的倍数集， =2，3，5，7。,3.3 例,3.3 例,3.3 例,3.3 例,3.3 例,注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7着四个数，又包含了1这个非素数。2， 3，5，7本身是素数。故所求的不超过 120的素数个数为： 27+4-1=30,3.3 例,例5。用26个英文字母作不
8、允许重复的 全排列，要求排除dog，god，gum， depth，thing字样的出现，求满足这些 条件的排列数。 解：所有排列中，令：,3.3 例,3.3 例,出现dog字样的排列，相当于把dog作 为一个单元参加排列，故,类似有：,由于god,dog不可能在一个排列中同 时出现，故：,类似：,3.3 例,由于gum,dog可以在dogum字样中同时 出现，故有：,类似有god和depth可以在godepth字样 中同时出现，故,god和thing可以在thingod字样中同时 出现，从而,3.3 例,3.3 例,由于god、depth、thing不可以同时出 现，故有：,其余多于3个集合的
9、交集都为空集。,3.3 例,故满足要求的排列数为：,3.3 例,例6。求完全由n个布尔变量确定的布 而函数的个数。 解：设,布尔函数类为：,由于n个布尔变量 的不 同的真值表数目与 位2进制数数目相同，故为 个。根据容斥原理，满足条件的函数数目为：,3.3 例,3.3 例,3.3 例,这10个布尔函数为：,例7。欧拉函数(n)是求小于n且与n 互素的数的个数。 解：若n分解为素数的乘积,设1到n的n个数中为 倍数的集合为,则有,3.3 例,3.3 例,3.3 例,即比60小且与60无公因子的数有16个： 7，11，13，17。19。23，29，31， 37，41，43，47，49，53，59，
10、此外 尚有一个1。,3.3 例,4 错排问题,n个元素依次给以标号1，2，n。 N个元素的全排列中，求每个元素都不 在自己原来位置上的排列数。 设 为数 在第 位上的全体排列， =1，2，n。因数字 不能动， 因而有：,3.3 例,3.4 错排问题,每个元素都不在原来位置的排列数为,3.4 错排问题,例1。数1，2，9的全排列中，求 偶数在原来位置上，其余都不在原来位 置的错排数目。 解：实际上是1，3，5，7，9五个数 的错排问题，总数为：,3.4 错排问题,例2. 在8个字母A,B,C,D,E,F,G,H的全 排列中,求使A,C,E,G四个字母不在原来 上的错排数目。,8个字母的全排列中，
11、令 分别表A,C,E,G在原来位置上的排列，则错排数为：,3.4 错排问题,3.4 错排问题,例3。求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列 数。,解：8个字母中只有4个不在原来位置 上，其余4个字母保持不动，相当于4个 元素的错排，其数目为,3.4 错排问题,故8个字母的全排列中有4个不在原来 位置上的排列数应为：C(8,4)9=630,3.4 错排问题,1. 有限制排列,3.5 棋盘多项式和有限制排列,例 4个x ，3个y，2个z的全排列中，求不出现xxxx，yyy，zz图象的排列。 解设出现xxxx的排列的集合记为A1， 设出现yyy的排列的集合记为A
12、2，,3.5 棋盘多项式和有限制排列,设出现zz的排列的集合记为A3， 全排列的个数为： 所以 |A1A2A3| =1260(60+105+280) +(12+20+30)6 =871,3.5 棋盘多项式和有限制排列,2棋子多项式,n个不同元素的一个全排列可看做n个相 同的棋子在nn的棋盘上的一个布局。布 局满足同一行（列）中有且仅有一个棋子,x,x,x,x,x,如图所示的布局对应 于排列41352。,3.5 棋盘多项式和有限制排列,可以把棋盘的形状推广到任意形状：,布子规定称为无对攻规则，棋子相当于 象棋中的车。 令r k（C）表示k个棋子布到棋盘C上的 方案数。如：,3.5 棋盘多项式和有
13、限制排列,r1( )=1，,r1( )=2，,r1( )=2，,r2( )=0，,r2( )=1。,为了形象化起见，（ ）中的图象便是棋盘 的形状。,3.5 棋盘多项式和有限制排列,定义 设C为一棋盘，称R(C)= rk(C) xk 为C的棋盘多项式。 规定 r0(C)=1，包括C=时。 设Ci是棋盘C的某一指定格子所在的行与 列都去掉后所得的棋盘；Ce是仅去掉该 格子后的棋盘。 在上面定义下，显然有 rk(C)=rk1(Ci)rk(Ce)，,k=0,3.5 棋盘多项式和有限制排列,即对任一指定的格子，要么布子，所得的 方案数为 rk1(Ci)； 要么不布子，方案数为 rk(Ce)。,设C有n
14、个格子，则 r1(C)n r1(C)r0(Ci) + r1(Ce)， r1(Ce)n1 r0(Ci)1故规定 r0(C)1是合理的,3.5 棋盘多项式和有限制排列,即对任一指定的格子，要么布子，所得的 方案数为 rk1(Ci)； 要么不布子，方案数为 rk(Ce)。 从而 R(C)= rk(C) xk rk1(Ci)+ rk(Ce)xk = x rk(Ci)xk + rk(Ce)xk xR(Ci) + R(C e) (3),k=0,k=1,k=0,k=0,3.5 棋盘多项式和有限制排列,例如：,R( )=1+ x；,R( )= xR( )+ R( )= x+ (1+ x)=1+2x；,R( )
15、= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x2,3.5 棋盘多项式和有限制排列,如果 C由相互分离的C1，C2组成，即C1 的任一格子所在的行和列中都没有C2的格 子。则有： rk(C) = ri(C1) rki(C2),i=0,k,故 R(C) = ( ri(C1) rki(C2) ) xk = ( ri(C1) xi) ( rj(C2) xj ),j=0,n,n,k,n,i=0,i=0,k=0, R(C) = R(C1) R(C2) (4),3.5 棋盘多项式和有限制排列,利用（）和（），可以把一个比较复 杂的棋盘逐步分解成相对比较简单的棋盘， 从而得到其棋盘多项式。,例 R ( ) = xR( )+R( ) = x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3,
