组合数学第三章容斥原理和鸽巢原理.ppt

关于组合数学第三章容斥原理和鸽巢原理现在学习的是第1页，共150页 3的倍数是：3，6，9，12，15，18。6个 但答案不是10+6=16 个，因为6，12，18在两类中重复计数，应减 去。故答案是：16-3=133.2 容斥原理容斥原理现在学习的是第2页，共150页 容斥原理容斥原理研究有限集合的研究有限集合的交或并交或并 的计数的计数。DeMorgan定理定理 论域论域U，补集补集,有有3.2 容斥原理容斥原理(a)(b)现在学习的是第3页，共150页证证：(a)的证明。设 ,则 相当于 和同时成立，亦即 (1)3.2 容斥原理容斥原理现在学习的是第4页，共150页反之，若故(2)由（1）和（2）得(b)的证明和（的证明和（a)类似，从略类似，从略.3.2 容斥原理容斥原理现在学习的是第5页，共150页DeMogan定理的推广：设 证明证明：只证(a).N=2时定理已证。设定理对n是正确的，即假定：3.2 容斥原理容斥原理现在学习的是第6页，共150页正确即定理对n+1也是正确的。3.2 容斥原理容斥原理现在学习的是第7页，共150页2 容斥原理容斥原理 最简单的计数问题是求有限集合A和B的并的元素数目。显然有即具有性质A或B的元素的个数等于具(1)定理定理：3.2 容斥原理容斥原理现在学习的是第8页，共150页有性质A和B的元素个数。UBA3.2 容斥原理容斥原理现在学习的是第9页，共150页3.2 容斥原理容斥原理证证若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)现在学习的是第10页，共150页3.2 容斥原理容斥原理(3)(1)(2)得|AB|A|B|AB|+|AB|+|BA|(|AB|+|AB|)(|BA|+|BA|)|AB|AB|A|+|B|AB|现在学习的是第11页，共150页定理：定理：(2)3.2 容斥原理容斥原理现在学习的是第12页，共150页3.2 容斥原理容斥原理现在学习的是第13页，共150页ABC3.2 容斥原理容斥原理现在学习的是第14页，共150页 例例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？3.2 容斥原理容斥原理现在学习的是第15页，共150页令：令：M为修数学的学生集合；P 为修物理的学生集合；C 为修化学的学生集合；3.2 容斥原理容斥原理现在学习的是第16页，共150页即学校学生数为336人。3.2 容斥原理容斥原理现在学习的是第17页，共150页同理可推出：利用数学归纳法可得一般的定理：3.2 容斥原理容斥原理现在学习的是第18页，共150页 定理定理设(n,k)是1,n的所有k-子集的集合,则|Ai|=(1)k-1|Ai|证证对n用归纳法。n=2时，等式成立。假设对n-1，等式成立。对于n有 3.2 3.2 容斥原理容斥原理ni=1k=1n I(n,k)iI现在学习的是第19页，共150页3.2 3.2 容斥原理容斥原理 I(n-1,k)I(n-1,k)iI现在学习的是第20页，共150页3.2 3.2 容斥原理容斥原理 I(n,k)I(n-1,k-1)I(n-1,k)此定理也可表示为：现在学习的是第21页，共150页定理：定理：设是有限集合，则(4)3.2 容斥原理容斥原理现在学习的是第22页，共150页 证：证：用数学归纳法证明。已知 n=2时有设 n-1时成立，即有：3.2 容斥原理容斥原理3.2 容斥原理容斥原理现在学习的是第23页，共150页3.2 容斥原理容斥原理现在学习的是第24页，共150页3.2 容斥原理容斥原理现在学习的是第25页，共150页3.2 容斥原理容斥原理现在学习的是第26页，共150页3.2 容斥原理容斥原理现在学习的是第27页，共150页3.2 容斥原理容斥原理现在学习的是第28页，共150页3.2 容斥原理容斥原理现在学习的是第29页，共150页其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。一般有：3.2 容斥原理容斥原理现在学习的是第30页，共150页(5)容斥原理指的就是（4）和（5）式。3.2 容斥原理容斥原理现在学习的是第31页，共150页3 例例 例例1 求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。解：解：设A为ace作为一个元素出现的排列集，B为 df作为一个元素出现的排列集，为同时出现ace、df的排列数。3.3 例例现在学习的是第32页，共150页根据容斥原理，不出现ace和df的排列数为：=6!-(5!+4!)+3!=582 3.3 例例现在学习的是第33页，共150页 例例2 求从1到500的整数中能被3或5除尽的数的个数。解：解：令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合3.3 例例现在学习的是第34页，共150页被3或5除尽的数的个数为 例例3 求由a,b,c,d四个字母构成的位符号串中，a,b,c,d至少出现一次的符号串数目。3.3 例例现在学习的是第35页，共150页 解：解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是3.3 例例现在学习的是第36页，共150页 a，b，c至少出现一次的n位符号串集合即为3.3 例例现在学习的是第37页，共150页 例例4。求不超过120的素数个数。因 ，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。设 为不超过120的数 的倍数集，=2，3，5，7。3.3 例例现在学习的是第38页，共150页3.3 例例现在学习的是第39页，共150页3.3 例例现在学习的是第40页，共150页3.3 例例现在学习的是第41页，共150页3.3 例例现在学习的是第42页，共150页 注意：注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7着四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求的不超过120的素数个数为：27+4-1=303.3 例例现在学习的是第43页，共150页 例例5。用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。解：解：所有排列中，令：3.3 例例现在学习的是第44页，共150页3.3 例例现在学习的是第45页，共150页 出现dog字样的排列，相当于把dog作为一个单元参加排列，故类似有：由于god,dog不可能在一个排列中同 时出现，故：类似：类似：3.3 例例现在学习的是第46页，共150页 由于gum,dog可以在dogum字样中同时出现，故有：类似有god和depth可以在godepth字样中同时出现，故 god和thing可以在thingod字样中同时出现，从而 3.3 例例现在学习的是第47页，共150页3.3 例例现在学习的是第48页，共150页 由于god、depth、thing不可以同时出现，故有：其余多于3个集合的交集都为空集。3.3 例例现在学习的是第49页，共150页 故满足要求的排列数为：3.3 例例现在学习的是第50页，共150页 例例6。求完全由n个布尔变量确定的布而函数的个数。解：解：设 布尔函数类为：由于n个布尔变量 的不同的真值表数目与 位2进制数数目相同，故为 个。根据容斥原理，满足条件的函数数目为：3.3 例例现在学习的是第51页，共150页3.3 例例现在学习的是第52页，共150页3.3 例例这10个布尔函数为：x1x2，x1x2，x1x2，x1x2，x1x2，x1x2，x1x2，x1x2，(x1x2)(x1x2)，(x1x2)(x1x2)现在学习的是第53页，共150页 例例7。欧拉函数(n)是求小于n且与n互素的数的个数。解：解：若n分解为素数的乘积 设1到n的n个数中为 倍数的集合为则有则有3.3 例例现在学习的是第54页，共150页3.3 例例现在学习的是第55页，共150页3.3 例例现在学习的是第56页，共150页即比60小且与60无公因子的数有16个：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一个1。3.3 例例现在学习的是第57页，共150页 4 错排问题错排问题 n个元素依次给以标号1，2，n。N个元素的全排列中，求每个元素都不在自己原来位置上的排列数。设 为数 在第 位上的全体排列，=1，2，n。因数字 不能动，因而有：3.3 例例现在学习的是第58页，共150页3.4 错排问题错排问题现在学习的是第59页，共150页每个元素都不在原来位置的排列数为3.4 错排问题错排问题现在学习的是第60页，共150页 例例1。数1，2，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。解：解：实际上是1，3，5，7，9五个数的错排问题，总数为：3.4 错排问题错排问题现在学习的是第61页，共150页 例例2.在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。8个字母的全排列中，令分别表A,C,E,G在原来位置上的排列，则错排数为：3.4 错排问题错排问题现在学习的是第62页，共150页3.4 错排问题错排问题现在学习的是第63页，共150页 例例3。求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列数。解：解：8个字母中只有4个不在原来位置上，其余4个字母保持不动，相当于4个元素的错排，其数目为3.4 错排问题错排问题现在学习的是第64页，共150页 故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)9=6303.4 错排问题错排问题现在学习的是第65页，共150页5 棋盘多项式和有限制排列棋盘多项式和有限制排列1.有限制排列有限制排列3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列 例例4个x，3个y，2个z的全排列中，求不出现xxxx，yyy，zz图象的排列。解解设出现xxxx的排列的集合记为A1，|A1|=60;设出现yyy的排列的集合记为A2，|A2|=105；6!1!3!2!4!2!7!现在学习的是第66页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列 设出现zz的排列的集合记为A3，|A3|=280；|A1A2|=12；|A1A3|=20；|A2A3|=30；|A1A2A3|=3!=6；全排列的个数为：=1260；所以：|A1A2A3|=1260(60+105+280)+(12+20+30)6 =871 4!3!8!4!2!5!3!6!4!9!2!3!4!现在学习的是第67页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列2棋子多项式 n个不同元素的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子xxxxx 如图所示的布局对应于排列41352。现在学习的是第68页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列 可以把棋盘的形状推广到任意形状：布子规定称为无对攻规则，棋子相当于 象棋中的车。令r k（C）表示k个棋子布到棋盘C上的方案数。如：现在学习的是第69页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列r1()=1，r1()=2，r1()=2，r2()=0，r2()=1。为了形象化起见，（）中的图象便是棋盘的形状。现在学习的是第70页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列定义定义设C为一棋盘，称R(C)=rk(C)xk为C的棋盘多项式。规定 r0(C)=1，包括C=时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有rk(C)=rk1(Ci)rk(Ce)，k=0现在学习的是第71页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列即对任一指定的格子，要么布子，所得的方案数为 rk1(Ci)；要么不布子，方案数为 rk(Ce)。设C有n个格子，则 r1(C)nr1(C)r0(Ci)+r1(Ce)，r1(Ce)n1 r0(Ci)1故规定 r0(C)1是合理的现在学习的是第72页，共150页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=0k=0k=0k=0现在学习的是第73页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列例如：R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=x R()+R()=x(1+x)+1+x =1+2x+x2现在学习的是第74页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列 如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：rk(C)=ri(C1)rki(C2)i=0k故R(C)=(ri(C1)rki(C2)xk =(ri(C1)xi)(rj(C2)xj)j=0nnkni=0i=0k=0 R(C)=R(C1)R(C2)(4)现在学习的是第75页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列利用（）和（），可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。例例R()=xR()+R()=x(1+x)2 +(1+2x)2 =1+5x+6x2+x3*R()=xR()+R()=1+6x+10 x2+4x3现在学习的是第76页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列有禁区的排列例设对于排列P=P1 P2 P3 P4，规定P1，P、，P2、，P42。1 2 3 4P1P2P3P412 4 314 3223431 214这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。现在学习的是第77页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列定理定理设 ri 为 I个棋子布入禁区的方案数，i=1,2,3,n。有禁区的布子方案数（即禁区内不布子的方案数）为 r0 n!r1(n1)!r2(n2)!(1)nrn(1)k rk(nk)!k=0n证证设Ai 为第i个棋子布入禁区，其他棋子任意布的方案集，i=1,2,3,n。现在学习的是第78页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列则所有棋子都不布入禁区的方案数为A1A2Ann！(1)kAiI(n,k)niIk=0而 Ai正是k个棋子布入禁区，其他n-k个棋子任意布的方案数。由假设可知等于rk(nk)！(注意：布入禁区的棋子也要遵守无对攻规则）.所以A1A2An=n!+(1)k rk(nk)!I(n,k)iIk=0 n现在学习的是第79页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列上例方案数为 4!6(41)!11(42)!7(43)!1(4)!4例例，四位工人，A，B，C，D四项任务。条件如下：不干B；不干B、C；不干C、D；不干D。问有多少种可行方案？现在学习的是第80页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列解由题意，可得如下棋盘：其中有影线的格子表示禁区。A B C D1 2 3 4 R()=1+6x+10 x2+4x3 方案数=4!6(41)!+10(42)!4(43)!+0(44)!=4现在学习的是第81页，共150页3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列例例三论错排问题错排问题对应的是nn的棋盘的主对角线上的格子是禁区的布子问题。C=R(C)=(1+x)n=()xk 令rk=()nk=0 n k n k故R(C)中的xn:n!+(1)k()(nk)!=n!(1)k =Pnk=1 n nk=0 k!1 k n现在学习的是第82页，共150页3.6一般公式一般公式 3.6一般公式若将.2中的例子改为“单修一门数学的学生有多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”则相应的答案表示如下：MPC；MPC+MPC+MPCMPC+MPC+MPC现在学习的是第83页，共150页3.6一般公式一般公式设有与性质,2,n相关的元素N个，Ai为有第 i 种性质的元素的集合.i=1,2,nPk为至少有k种性质的元素的元次；qk为恰有k种性质的元素的个数。P0=N，P1=|A1|+|A2|+|An|，P2=|A1A2|+|A1A3|+|An-1An|Pk=|Aij|qk=|(Ai)(Aj)|I(n,k)i I I(n,k)i Ij I现在学习的是第84页，共150页3.6一般公式一般公式定理qk=(1)i()Pk+i k+i ii=0n-k证证设某一元素恰有k种性质，则其对Pk的某一项的贡献为，而对Pk+1，Pk+2,Pn的贡献都是。若某一元的性质少于k种则其对Pk，Pk+1，Pn的贡献都是。若恰有k+j种性质，则其对Pk的贡献是(),对Pk+i的贡献是（）k+j k k+jk+i现在学习的是第85页，共150页3.6一般公式一般公式而(1)i()()=(1)i()()=(1)i()()=()(1)i()=()0=0即某恰有k+j种性质的元素对上式右边的总的贡献为。k+jk+ik+i ii=0 ji=0 jk+jk+ik+i ki=0 jk+j i j kk+j k j ik+j k现在学习的是第86页，共150页3.6一般公式一般公式前例中只修一门课的学生为：|MPC|+|MPC|+|MPC|=q1=(1)j-1()Pj=P1 2P2+3P3j1j=1 3 在一般公式中，若令 P0=N，q0=|A1A2An|，就得到原来的容斥原理。现在学习的是第87页，共150页3.6一般公式一般公式证证根据定义 qk=|(Ai)(Aj)|qk由Pk+j的代数和组成，符号(1)j，计算Pk+j的重复度：k+j个集的交的绝对值的项的总个数为()(),共()种。每一项的重复度为 ()()()=()从而Pk+j的重复度也是()I(n,k)i Ij Inkk+jk+jk+jk+jjnknknnnkjkk现在学习的是第88页，共150页3.6一般公式一般公式qk=(1)j()Pk+j =(1)j k()Pjk+jkkjj=0n kkn证证对N做归纳。N=1时，设此元有m种性质，m n,不妨设A1=A2=Am=a1。显然Pj=()，若 jm，则 Pj=0；由定义，得 qk=jm1 k=m0 k m 现在学习的是第89页，共150页3.6一般公式一般公式右端(1)i()Pk+i (1)i()()(1)i()()=k+i ii=0nkk+i k m k+ii=0nk m k m-k i i=0nk1 k=m0 km假设对于 N1，等式成立。对于N，设新增元有m种性质，对于N个元的PjPj()，qkjm1 k=m0 km现在学习的是第90页，共150页3.6一般公式一般公式右端(1)i()Pk+i(1)i()Pk+i+()(1)i()Pk+i+(1)i()()qk+等式成立k+i ki=0nkk+i kk+i mk+i ki=0nkk+i ki=0nkk+i mnk i=01 k=m0 km现在学习的是第91页，共150页3.6一般公式一般公式例例某校有个教师，已知教数学的有位，教物理的有位，教化学的位；数、理位，数、化位，理、化位；数理化位。问教其他课的有几位？只教一门的有几位？只好教两门的有几位？解解令教数学的教师属于A1，教物理的属于A2，教化学的属于A3。则P0，P1|A1|+|A2|+|A3|8+6+5;P2|A1A2|+|A1A3|+|A2A3|12；P3|A1A2A3|3；现在学习的是第92页，共150页3.6一般公式一般公式故教其他课的老师数为：q0P0 P1+P2P3恰好一门的教师数：q1P12P2+3P34恰好教两门的老师数为：q2P23P33现在学习的是第93页，共150页3.6一般公式一般公式例例n 对夫妻围坐问题设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？解解不妨设 n 个女人先围成一圈，方案数为(n1)!。对任一这样的给定方案，顺时针给每个女人以编号1,2,n。设第i号与第 i+1号女人之间的位置为第 i 号位置，1 i n1。第 n 号女人与第1 号之现在学习的是第94页，共150页3.6一般公式一般公式间的位置为第 n 号位置。设第 i 号女人的丈夫的编号也为第 i 号，1 i n。让 n 个男人坐到上述编号的 n 个位置上。设 ai是坐在第 i 号位置上的男人，则 ai i，i+1，i n1；ann，1。这样的限制也即要求在下面3行n列的排列中 nn n1 a1 a2 a3 an1 an现在学习的是第95页，共150页3.6一般公式一般公式每列中都无相同元素。满足这样的限制的排列 a1a2 an称为二重错排。设二重错排的个数为Un，原问题所求的方案数就是Un(n1)！。设Ai为 ai=I 或 I+1(1 I n1)，an=n 或1的排列 a1 a2 an的集合。则Ai=2(n1)!，关键是计算|Ai|I(n,k)iI现在学习的是第96页，共150页3.6一般公式一般公式也就是从(1,2)(2,3)(n,n)(n,1)这n对数的k 对中各取一数，且互不相同的取法的计数。这相当于从1,2,2,3,3,4,n1,n1,n,n,1中取 k 个互不相邻数的组合的计数，但首尾的不能同时取。回想无重复不相邻组合的计数：C(n,r)=C(nr+1,r),这里所求的是()()=()2nk+1 k2n4(k2)+1 k22nk k 2n2nk现在学习的是第97页，共150页3.6一般公式一般公式 Un=(1)k ()(nk)!=Ai 2n2nk2nk ki 1,n 现在学习的是第98页，共150页.11反演反演基本想法：an 易算，bn难算，an可用bn表示，利用反演，将bn用an表示二项式反演二项式反演引理引理现在学习的是第99页，共150页.11反演反演证证现在学习的是第100页，共150页.11反演反演定理定理证证现在学习的是第101页，共150页.11反演反演推论证在定理中bk处用(1)k bk代入，即可例n!=()Dnk，Dn=bn，令nk=l，则 n!=()DlDn=(1)n-k()k!=n!(1)n-k =n nknknk 1(nk)!k=0k=0k=0nnn(1)k k!现在学习的是第102页，共150页.11反演反演Mbus反演定义设 n Z+1，若 n=1;(n)=0，若n=p11 p22 pkk 存在i1 (1)k，若n=p1p2pk 如(30)=(235)=(1)3 (12)=0；现在学习的是第103页，共150页.11反演反演定理定理设n Z+则 (d)=1，若n=1；0，若n 1；d|n证证若n=1，(d)=(1)=1,成立若 n1，设n=p11 p22 pkk，n=p1p2pk(d)=(d)=(pi)+(1)=1+()(1)j=(11)k=0d|nd|nd|nj=1kiII(k,j)kjj=1k现在学习的是第104页，共150页.11反演反演推论推论(n)=n (d)dd|n证证n =n =n 1+(1)j (pi)1 =n (1 )=(n)(d)dd|n(d)dd|n1pij=1i=1kkI(k,j)i I现在学习的是第105页，共150页.11反演反演定理定理(Mbus反演定理)设 f(n)和g(n)是定义在正整数集合上的两个函数 f(n)=g(d)=g()(M1)g(n)=(d)f()=()f(d)(M2)ndndd|nd|nd|nd|n则(M1)(M2)nd现在学习的是第106页，共150页.11反演反演证证“”设(M1)成立。(d)f()=(d)g(d1)=(d)g(d1)=(d)g(d1)=(d)g(d1)=g(d1)(d)=(d)=g(n)d|nd|nd|ndd1|nd1|nnd1d|nd1d|d1|nndd1|ndd1|ndnd1d|1，d1=n0，d1 n现在学习的是第107页，共150页.11反演反演“”：设（M2）成立。g(d)=g(d)=(d )f(d1)=(d )f(d1)=f(d1 )(d )=(d )=(d )=f(n)d|nd|nd|nndd1|nd1d|nd1d|nd1d|d1|ndd1|n1，d1=n0，d1 h，使得 ah+ah+1+ak=39 证证令Sj=ai，j=1,2,100显然S1S2hSkSh=39 即 ah+ah+1+ak=39 现在学习的是第118页，共150页.8鸽巢原理之二鸽巢原理之二鸽巢原理二鸽巢原理二m1,m2,mn都是正整数，并有m1+m2+mnn+1个鸽子住进n个鸽巢，则至少对某个 i 有第 i 个巢中至少有mi个鸽子，i=1,2,n上一小节的鸽巢原理一是这一原理的特殊情况，即m1=m2=mn=2，m1+m2+mnn+1=n+1如若不然，则对任一 i，都有第 i 个巢中的鸽子数mi1则现在学习的是第119页，共150页.8鸽巢原理之二鸽巢原理之二鸽子总数 m1+m2+mnn，与假设相矛盾推论推论m只鸽子进n个巢，至少有一个巢里有|只鸽子nm推论推论n(m1)+1只鸽子进n个巢，至少有一个巢内至少有m只鸽子推论推论若m1,m2,mn是正整数，且 r1,则 m1,mn至少有一个不小于rm1+mn n现在学习的是第120页，共150页.8鸽巢原理之二鸽巢原理之二例例设A=a1a2a20是10个0和10个1 组成的进制数B=b1b2b20是任意的进制数C=b1b2b20 b1b2b20=C1C2C40，则存在某个i，1 i 20，使得CiCi+1Ci+19与a1a2a20至少有10位对应相等.ABC第 i 格第 i+19格1 2 19 20 1 2 19 20 1 2 19 20 1 19 20现在学习的是第121页，共150页.8鸽巢原理之二鸽巢原理之二证证在C=C1C2C40中，当 i 遍历1,2,20时，每一个bj历遍 a1,a2,a20因A中有10个0和10个1，每一个bj都有10位次对应相等从而当 i历遍1,20时，共有10 20=200位次对应相等故对每个 i平均有200 20=10位相等，因而对某个 i 至少有10位对应相等现在学习的是第122页，共150页.8鸽巢原理之二鸽巢原理之二定理定理若序列S=a1,a2,amn+1中的各数是不等的m,n 是正整数，则 S有一长度为m+1的严格增子序列或长度为n+1的减子序列，而且 S有一长度为m+1的减子序列或长度为n+1的增子序列证证由S中的每个 ai 向后选取最长增子序列，设其长度为li，从而得序列L=l1,l2,lmn+1 若存在 lkm+1则结论成立现在学习的是第123页，共150页.8鸽巢原理之二鸽巢原理之二否则所有的 li 1,m，其中必有|=n+1个相等设li1=li2=lin=lin+1 不妨设 i1i2 ai2 ain+1，即有一长度为n+1的减子列否则不妨设ai1 li2，矛盾mn+1 m现在学习的是第124页，共150页.8鸽巢原理之二鸽巢原理之二证证从ai 向后取最长增子列及减子列，设其长度分别为 li，li.若任意 i，都有li 1，m,li，n,不超过mn种对则存在 j k，(lj,lj)=(lk,lk)若aj lk，若aj ak，则 lj lk，矛盾现在学习的是第125页，共150页.8鸽巢原理之二鸽巢原理之二例例将 1,65 划分为个子集，必有一个子集中有一数是同子集中的两数之差证用反证法设次命题不真即存在划分P1 P2 P3P4 1，65，Pi中不存在一个数是Pi中两数之差，i=1,2,3,4因 =17，故有一子集，其中至少有17个数，设这17个数从小到大为a1,a17 不妨设 A=a1,a17 P1。令bi1=aia1，i=2，17。65 4现在学习的是第126页，共150页.8鸽巢原理之二鸽巢原理之二设Bb1,b16，B 1,65。由反证法假设BP1=。因而 B (P2 P3 P4)。因为 6，不妨设b1,b6 P2，令Ci1=bib1，I=2，6设C C1,C5，C 1,65 由反证法假设C(P1P2)=，故有 C (P3P4)因为 3，不妨设C1,C2,C3 P316 352现在学习的是第127页，共150页.8鸽巢原理之二鸽巢原理之二令di1=CiC1，I=2,3设D d1,d2 ,D 1,65。由反证法假设 D(P1P2P3)=，因而 D P4。由反证法假设 d2d1 P1P2P3 且d2d1 P4，故 d2d1 1,65，但显然 d2d1 1,65，矛盾。现在学习的是第128页，共150页.9Ramsey 问题问题RamseyRamsey问题问题 Ramsey问题可以看成是鸽巢原理的推广下面举例说明Ramsey问题例例6 个人中至少存在人相互认识或者相互不认识证证这个问题与K6的边着色存在同色三角形等价假定用红蓝着色现在学习的是第129页，共150页.9Ramsey 问题问题设K6的顶点集为v1,v2,v6，dr(v)表示与顶点 v 关联的红色边的条数，db(v)表示与 v 关联的蓝色边的条数在K6 中，有dr(v)db(v)，由鸽巢原理可知，至少有条边同色现将证明过程用判断树表示如下：现在学习的是第130页，共150页.9Ramsey 问题问题dr(v1)3?db(v1)3设(v1v2)(v1v3)(v1v4)为红边设(v1v2)(v1v3)(v1v4)为蓝边v2v3v4是红?v2v3v4是蓝?设(v2v3)是蓝边设(v2v3)是红边v1v2v3是蓝v1v2v3是红YNNNYY现在学习的是第131页，共150页.9Ramsey 问题问题若干推论若干推论(a)a)K6的边用红蓝任意着色，则至少有两个同色的三角形证证由前定理知，有同色三角形，不妨设v1v2v3是红色三角形可由如下判断树证明现在学习的是第132页，共150页.9Ramsey 问题问题v1v4v5是蓝设(v4v5)为蓝边v4v5v6是红?设(v1v4)(v1v5)(v1v6)为蓝边db(v1)3dr(v1)3?设(v1v4)为红边(v4v2)(v4v3)为蓝边?设(v4v2)为红边db(v4)3?v1v2v4是红dr(v4)3设(v4v5)为蓝边(v4v5)(v4v6)为红边v2v3v5是红?设(v2v5)为蓝边v2v4v5是蓝v4v5v6是红v1v5v6是蓝?设(v5v6)为红边yyyyyynnnnn现在学习的是第133页，共150页.9Ramsey 问题问题(b)b)K9 的边红蓝两色任意着色，则必有红K4或蓝色三角形(蓝K4或红色三角形)证证设个顶点为 v1,v2,v9对个顶点的完全图的边的红、蓝着色图中，必然存在 vi，使得 dr(vi)3 否则，红边数 dr(vi)，这是不可能的不妨设 dr(v1)3，可得如下判断树证明结论1227 2现在学习的是第134页，共150页.9Ramsey 问题问题dr(v1)4?db(v1)6设(v1v2)(v1v3)(v1v4)(v1v5)是4红边设(v1v2)(v1v7)是6条蓝边K4(v2v3v4v5)是蓝K4?K6(v2v7)中有红?设(v2v3)是红边v1v2v3是红设v2v3v4是红K4(v2v3v4v5)是蓝K4YYYNNN现在学习的是第135页，共150页.9Ramsey 问题问题K9的边红、蓝着色，必有红色三角形或蓝色K4同理可证 K9的红、蓝着色，必有蓝色三角形或红色K4 (红 蓝K4)(蓝 红K4)存在同色K4或红及蓝 同色K4(红 蓝)现在学习的是第136页，共150页.9Ramsey 问题问题(c)c)K18的边红，蓝着色，存在红K4或蓝K4 证证设18个顶点为v1,v2,v18 从v1引出的17条边至少有条是同色的，不妨先假定为红色从而可得下面的判断树证明命题现在学习的是第137页，共150页.9Ramsey 问题问题dr(v1)9db(v1)9设(v1v2)(v1v10)是红边K9(v2 v10)中有同色K4或红加蓝K10(v1v2 v10)中有同色K4设(v1v2)(v1v10)是蓝边K9(v2 v10)中有同色K4或红加蓝K10(v1v2 v10)中有同色K4YN现在学习的是第138页，共150页.10Ramsey数数将上一节的问题一般化：给定一对正整数a、b，存在一个最小的正整数 r,对 r 个顶点的完全图的边任意红、蓝着色，存在 a 个顶点的红边完全图或 b 个顶点的蓝边完全图。记为 r(a,b)。比如：r(3,3)6，r(3,4)9，r(4,4)18RamseyRamsey数的简单性质数的简单性质现在学习的是第139页，共150页.10Ramsey数数定理定理r(a,b)r(b,a)；r(a,2)a证证K r(a,b)的边红蓝着色，有红Ka或蓝Kb将红蓝色对换，就有红Kb或蓝Ka设r(a,b)r，Kr的边任意红蓝着色红蓝互换后仍是Kr的边的着色，由r(a,b)的定义，有红Ka或蓝Kb再红蓝对换恢复原图有红Kb或蓝Ka 现在学习的是第140页，共150页.10Ramsey数数例例K9的边任意红蓝着色，有红三角形或蓝K4红蓝对换后，仍有红三角形或蓝K4，再对换一次，回到原来的着色方案，有蓝三角形或红K4第二个等式容易看出Ka红蓝着色若不全红(红Ka)，则必有一条蓝边现在学习的是第141页，共150页.10Ramsey数数定理定理当a,b 时，r(a,b)r(a 1,b)r(a,b1)证证对r(a 1,b)r(a,b1)个顶点的完全图红蓝着色任取其中一点 v，有 dr(v)+db(v)=r(a 1,b)+r(a,b1)1从而可得判断树如下现在学习的是第142页，共150页现在学习的是第143页，共150页.10Ramsey数数推论推论r(a,b)()a+b2 a1证证 r(a,b)r(a 1,b)r(a,b1)()()()a+b2 a1a+b3 a2a+b3 a1现在学习的是第144页，共150页.10Ramsey数数定理定理若 a，则 r(a,a)2a2证证Kn有()条边，对边红蓝着色有2 种方案其中同色Ka的方案数不超过n2n2()a2()()2 2n2()n2Ka的个数可红可蓝可任意着色边数同色边数现在学习的是第145页，共150页.10Ramsey数数这是一个上界Kn中含Ka的方案被重复计数若取n足够小，便得a2()()2na()+1 n an即()2 n=2 时()2a2 现在学习的是第147页，共150页.10Ramsey数数RamseyRamsey数的推广数的推广若将着色改为k 着色，同色Ka或同色Kb改为同色Ka i i=1,2,k即得Ramsey数 r(a1,a2,ak)对于给定的正整数 ai(ai 2)，i=1,2,k存在最小正整数r对Kr的边用k中颜色Ci(i=1,2,k)任意着色则存在 i，出现全Ci色的Ka i(即边都是Ci色的ai个顶点的完全图）；这个最小正整数 r 用 r(a1,ak)表示现在学习的是第148页，共150页.10Ramsey数数有 r(a1,a2,ak)r(a1,r(a2,ak)证证设r(a1,r(a2,ak)=p，r(a2,ak)=q；对Kp的边着色，出现第一色Ka1或第二色Kq，用n1中色对Kq的边着色，至少出现i色的ai点完全图，i=2,n对Kp的边n 着色，将后