第三章容斥原理与鸽巢原理.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,3.1 De Morgan定理,3.1 De Morgan定理,DeMorgan定理 论域U，补集,有,(a),(b),DeMogan定理的推广： 设A1,A2, ,An是U的子集，则,证明：只证(1). N=2时定理已证。 设定理对n是正确的，即假定：,3.1 De Morgan定理,即定理对n+1也是

2、正确的。,3.1 De Morgan定理,则,即具有性质A或B的元素的个数等于具有性质A和B的元素个数。,定理：,3.2 容斥原理,U,B,A,定理：,3.2 容斥原理,A,B,C,3.2 容斥原理,例： 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？,3.2 容斥原理,令：M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合；,3.2 容斥原理,即学校学生数为336人。,3.2 容斥原理,同理可推出：,

3、利用数学归纳法可得一般的定理：,3.2 容斥原理,定理：设A1,A2, ,An是有限集合，则,3.2 容斥原理,证：用数学归纳法证明。 已知 n=2时有,设 n-1时成立，即有：,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,3.2 容斥原理,其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。 一般有：,3.2 容斥原理,又,3.2 容斥原理,例1 求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。 解：设A为ace作为一个元素出现的排列集，B为 df作为一个元素出现的排

4、列集， 为同时出现ace、df的排列数。,3.3 容斥原理举例,根据容斥原理，不出现ace和df的排列数 为：,=6!- (5!+4!)+3!=582,3.3 容斥原理举例,例2 求从1到500的整数中能被3或5除尽的数的个数。 解： 令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合,3.3 容斥原理举例,被3或5除尽的数的个数为,例3 求由a,b,c,d四个字母构成的位符号串中，a,b,c至少出现一次的符号串数目。,3.3 容斥原理举例,解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。 由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现

5、a的n位符号串的个数应是3n，即,3.3 容斥原理举例,a，b，c至少出现一次的n位符号串集合即为,3.3 容斥原理举例,例4 求不超过120的素数个数。,因 112=121，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。 设Ai为不超过120的数i 的倍数集, i =2,3,5,7。,3.3 容斥原理举例,3.3 容斥原理举例,3.3 容斥原理举例,3.3 容斥原理举例,3.3 容斥原理举例,3.3 容斥原理举例,注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求

6、的不超过120的素数个数为： 27+4-1=30,3.3 容斥原理举例,例5 用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。 解：所有排列中，令：,3.3 容斥原理举例,3.3 容斥原理举例,A1为出现dog的排列的全体; A2为出现god的排列的全体; A3为出现gum的排列的全体; A4为出现depth的排列的全体. A5为出现thing的排列的全体.,出现dog字样的排列，相当于把dog作为一个单元参加排列，故,类似有：,由于god,dog不可能在一个排列中同 时出现，故：,类似：,3.3 容斥原理举例,由

7、于gum,dog可以在dogum字样中同时出现，故有：,类似有god和depth可以在godepth字样中同时出现，故,god和thing可以在thingod字样中同时出现，从而,3.3 容斥原理举例,3.3 容斥原理举例,由于god、depth、thing不可以同时出现，故有：,其余多于3个集合的交集都为空集。,3.3 容斥原理举例,故满足要求的排列数为：,3.3 容斥原理举例,例6 求完全由n个布尔变量确定的布尔函数 的个数。 解：设f(x1,x2, ,xn)中不出现xi的布尔函数为Ai (i=1,2, ,n),由于n个布尔变量 的不同的真值表数目与 位2进制数数目相同，故为 个。根据容斥

8、原理，满足条件的函数数目为：,3.3 容斥原理举例,3.3 容斥原理举例,若n=2，则,x1、x2均出现的10个布尔函数为： x1x2，x1x2，x1x2， x1x2， x1x2，x1x2，x1x2， x1x2， (x1x2)(x1x2)， (x1x2)(x1x2),3.3 容斥原理举例,例7：错排问题,n个元素依次给以标号1，2，n。N个元素的全排列中，求每个元素都不在自己原来位置上的排列数。 设Ai为数i在第i位上的全体排列， i=1，2，n。因数字i不能动，因而有：,3.3 容斥原理举例,3.3 容斥原理举例,每个元素都不在原来位置的排列数为,3.3 容斥原理举例,例8. 数1,2,9的

9、全排列中,求偶数在原来位置上,其余都不在原来位置的错排数目。 解：实际上是1,3,5,7,9五个数的错排问题，总数为：,3.3 容斥原理举例,例9. 在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。,解: 8个字母的全排列中，令 分别表A,C,E,G在原来位置上的排列，则错排数：,3.3 容斥原理举例,3.3 容斥原理举例,例10. 求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列数。,解：8个字母中只有4个不在原来位置上,其余4个字母保持不动,相当于4个元素的错排,其数目为：,3.3 容斥原理举例,故8个字母的全

10、排列中有4个不在原来位置上的排列数应为：C(8,4)9=630,3.3 容斥原理举例,1. 有限制排列,3.4 棋盘多项式和有限制排列,例 4个x ，3个y，2个z的全排列中，求不出现xxxx，yyy，zz图象的排列。 解 设出现xxxx的排列的集合记为A1， |A1|= =60; 设出现yyy的排列的集合记为A2， | A2|= =105；,6!,4!2!,7!,1!3!2!,3.4 棋盘多项式和有限制排列,设出现zz的排列的集合记为A3， |A3|= =280； |A1A2|= =12； |A1A3|= =20； |A2A3|= =30； |A1A2A3|=3!=6； 全排列的个数为： =

11、1260； 所以： |A1A2A3|=1260(60+105+280) +(12+20+30)6 = 871,4!3!,8!,4!,2!,5!,3!,6!,4!,9!,2!3!4!,2. 棋子多项式,n个不同元素的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子。,x,x,x,x,x,如图所示的布局对应 于排列41352。,3.4 棋盘多项式和有限制排列,可以把棋盘的形状推广到任意形状：,布子规定称为无对攻规则，棋子相当于象棋中的车。 令r k(C)表示k个棋子布到棋盘C上的方案数。如：,3.4 棋盘多项式和有限制排列,r1( )=1，,r1( )

12、=2，,r1( )=2，,r2( )=0，,r2( )=1。,为了形象化起见, ( )中的图像便是棋盘的形状。,3.4 棋盘多项式和有限制排列,定义 设C为一棋盘，称R(C)= rk(C) xk为C的棋盘多项式。 规定 r0(C)=1，包括C=时。 设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。 在上面定义下，显然有 rk(C)=rk1(Ci)rk(Ce)，,k=0,3.4 棋盘多项式和有限制排列,即对任一指定的格子，要么布子，所得的 方案数为 rk1(Ci)； 要么不布子，方案数为 rk(Ce)。,设C有n个格子，则 r1(C)n r1(C)r0(C

13、i) + r1(Ce)， r1(Ce)n1 r0(Ci)1 故规定 r0(C)1是合理的,3.4 棋盘多项式和有限制排列,即对任一指定的格子，要么布子，所得的 方案数为 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),k=0,k=0,k=0,k=0,3.4 棋盘多项式和有限制排列,例如：,R( )=1+ x；,R( )= xR( )+ R( )= x+ (1+ x)=1+2x；,R( )= x R( ) + R( ) = x(1 + x

14、 )+1 + x =1+ 2x +x2,3.4 棋盘多项式和有限制排列,如果C由相互分离的C1，C2组成，即C的任一格子所在的行和列中都没有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),3.4 棋盘多项式和有限制排列,利用(3)和(4)，可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。,例 R ( ) = xR( )+R( ) =

15、 x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3,*,R( ) = xR( ) + R( ) = 1+6x +10 x2 +4x3,3.4 棋盘多项式和有限制排列,例 设对于排列P=P1 P2 P3 P4，规定P1，P、， P2、， P42。,1 2 3 4,P1,P2,P3,P4,1,2,4 3,1 4 3,2,2 3,4,3,1 2,1 4,这样的排列对应于有 禁区的布子。如右图有影线的格子表示禁区。,3.5 有禁区的排列,定理 设 ri 为 i个棋子布入禁区的方案数， i =1,2,3,n。有禁区的布子方案数(即禁 区内不布子的方案数)为,r0 n! r1(n1)!

16、 r2(n2)!(1)nrn (1)k rk ( nk)!,k=0,n,证 令P1P2Pn是n个棋子布入nn棋盘的排列,即Pi是第i个棋子在第i行的位置, Ai 是棋子Pi,3.5 有禁区的排列,落入禁区,其他棋子任意布的方案集，i =1, 2, 3, ,n。一个棋子落入禁区,其余n-1个棋子进行无条件的排列,故至少有一个棋子落入禁区的方案数为r1(n-1)!,两个棋子落入禁区,其余n-2个棋子进行无条件的排列,故至少有两个棋子落入禁区的方案数为r2(n-2)!,依次类推,n个棋子无一落入禁区的排列数为:,A1A2An=n!+ (1)k rk ( nk)!,k=0,n,3.5 有禁区的排列,上

17、例方案数为 4!6(41)!11(42)!7(43)! 1(4)!4,例 1, 2, 3, 4四位工人，A, B, C, D 四项任务。条件如下: 1不干B; 2不干B、C; 不干C、D; 4不干D。问有多少种可行方案？,3.5 有禁区的排列,解 由题意，可得如下棋盘：,其中有影线的格子表示 禁区。,A B C D,1 2 3 4,R( )=1+6x+10 x2+4x3,方案数=4!6(41)!+10(42)!4(43)! +0(44)!=4,3.5 有禁区的排列,例 三论错排问题 错排问题对应的是nn的棋盘的主对角线上的格子是禁区的布子问题。,C =,错排的方案数:,3.5 有禁区的排列,3

18、.6 广义的容斥原理,例： 若将.2中的例子改为“单修一门数学的学生有多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”则相应的答案表示如下： MPC； MPC+MPC+MPC MPC+MPC+MPC,3.6 广义的容斥原理,只修一门数学：,只修一门物理：,只修一门化学：,3.6 广义的容斥原理,所以，只修一门课程：,3.6 广义的容斥原理,修数学和物理两门课：,类似地：,3.6 广义的容斥原理,一般地：,所以，可得：,3.6 广义的容斥原理,3.6 广义的容斥原理,还可以推得：,3.6 广义的容斥原理,所以有：,3.6 广义的容斥原理,定理：在集合S中,设A1,A2, ,An是n

19、种性质的子集,(m)表示刚好只有其中m个性质的元素个数,(m)表示至少有m个性质的元素个数,则,3.6 广义的容斥原理,以m=2,n=4为例：,3.6 广义的容斥原理,以m=3,n=4为例：,例：某校有12个教师,已知教数学的有位,教物理的有位,教化学的位;数、理位,数、化位,理、化位;数理化位。问教其他课的有几位？只教一门的有几位？只好教两门的有几位？ 解 令教数学的教师属于A1，教物理的属于A2，教化学的属于A3。则(0)12， (1) | A1 |+| A2|+| A3 |8+6+519; (2) | A1A2|+ | A1A3|+| A2A3|12； (3) | A1A2A3|3；,3

20、.7 广义的容斥原理的应用,故教其他课的老师数为： (0)(0)(1) +(2)(3) 恰好一门的教师数： (1)(1)2(2) +3(3)=4 恰好教两门的老师数为： (2)(2)3(3) =3,3.7 广义的容斥原理的应用,3.8 第二类Stirling数的展开式,第二类Stirling数，S(n,m)是将n个有标志的球放进m个无区别的盒子而无一空盒的方案数，也是将n个数拆分成正好m个数的和的方案数。,考虑n个有标志的球放进m个有区别的盒子，无一空盒的方案数，令： Ai表示第i盒为空盒的子集，i=1,2, ,m. n个有标志的球，m个有区别的盒，无一空盒的事件全体为S.,3.8 第二类St

21、irling数的展开式,3.8 第二类Stirling数的展开式,n个有标志的球放进m个有区别的盒子，无一空盒的方案数：,3.8 第二类Stirling数的展开式,第二类Stirling数，S(n,m)是将n个有标志的球放进m个无区别的盒子而无一空盒的方案数，所以：,推论1：,推论2：由于S(m,m)=1,问题: 欧拉函数 (n)是求小于n且与n互素的数的个数。 解：若n分解为素数的乘积,设1到n的n个数中为Pi 倍数的数的集合为: Ai ( i=1,2, ,n),则有,3.9 欧拉函数(n),3.9 欧拉函数(n),3.9 欧拉函数(n),即比60小且与60无公因子的数有16个：7，11，1

22、3，17，19，23，29，31，37，41，43，47，49，53，59，此外尚有一个1。,3.9 欧拉函数(n),3.10 n对夫妻问题,例 n 对夫妻围坐问题 设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？,解：（1）n个人围桌而坐的方案数应为( n1 )! n对夫妻围桌而坐的方案数：2n(n-1)! 令：Ai表示第i对夫妻相邻而坐的集合，i=1,2, ,n, 夫妻不相邻的方案数为：,3.10 n对夫妻问题,（2）2n个人围桌而坐的方案数应为( 2n1 )! |Ai|相当于将第i对夫妻作为一个对象围桌而坐后换位，故：,3.10 n对夫妻问题,故夫妻不相

23、邻而坐的方案数为：,.11 Mbius反演定理,基本想法：an 易算, bn难算, an可用 bn表示, 利用反演, 将bn用an表示,1. 二项式反演,引理:,.11 Mbius反演定理,基本想法：an 易算, bn难算, an可用 bn表示, 利用反演, 将bn用an表示,1. 二项式反演,引理:,.11 Mbius反演定理,基本想法：an 易算, bn难算, an可用 bn表示, 利用反演, 将bn用an表示,Mbius反演定理：设f(n)和g(n)是定义在正整数集合上的两个函数，若,则 反之亦然。,其中：,若d=1 若d=r个不同素数之积 其它（素数积中含有相同素数）,.11 Mbiu

24、s反演定理,辅助定理：对于任意正整数n恒有：,证明：n=1时，定理成立。,若,其中，pi是互不相同的素数。 d|n可表示为：,.11 Mbius反演定理,则d是从 个 中选 个 ，,从 个 中选 个 ， ,从 个 中选 个 ，而得到的结果。 而重复取某个 时， ，令：,.11 Mbius反演定理,证明(Mbius反演定理)： 由f(n)的公式得：,令,由于,.11 Mbius反演定理,所以，,反过来，,例 圆排列问题,设 a1a2an 是一个圆排列，即 a2a3ana1 , , ana1 an1，看作是相同的。为了加以区别，必要时把原先的排列称为线排列。一个圆排列在 n 个位置短开形成的 n

25、个线排列在元素可重复的情况下，未必都不相同。 例如，dn时，由不重复的a1a2 ad重复 n d次构成的圆排列。,.11 Mbius反演定理,( a1a2 ad ) ( a1a2 ad ),n d 组,只能形成 d 个不同的线排列。 若一个圆排列可由一个长度为 k 的线排列重复若干次形成，则这样的 k 中最小者成为该圆排列的周期。一个圆排列中元素的个数（重复出现的按其重复次数计）称为它的长度。,.11 Mbius反演定理,设集合1 , 2 , , m中元素形成的长度与周期都是 d 的圆排列的个数为M(d)。 设 n 是一给定的正整数。 若 d n ，每个长度与周期都是 d的圆排列可在 d 个位

26、置上断开，重复 n / d 次形成d个 长度为 n 的可重排列。因此有, d M( d ) = mn 由Mbus反演定理 n M(n) = ( d ) m 故 M( n ) = ( d ) m,dn,dn,dn,.11 Mbius反演定理,设长度为 n 的圆排列的个数为T( n )，则 T( n ) M( d ),dn,例 m = 1 , 2 ，n = 7 则 M ( 7 ) = ( 272 ) = 18 T ( 7 ) = M( d ) = M (1 ) + M ( 7) = 20,d7,1 7,.11 Mbius反演定理,.12 鸽巢原理,鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽

27、屉原理。即,“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”,例 367人中至少有人的生日相同。 例 10双手套中任取11只，其中至少有两只 是完整配对的。 例 参加一会议的人中至少有人认识的别的参加者的人数相等。,例 从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数，其中一个是另一个的倍数。,证 设n+1个数是 a1 , a2 , , an+1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列 r1 , r2, , , rn+1。这n+1个数仍在1 , 2n中，且都是奇数。而1 , 2n中只有n个奇数 。 故必有 ri = rj = r , 则 ai

28、 = 2i r, aj = 2j r 若ij ，则 ai 是 aj 的倍数。,.12 鸽巢原理,例 设 a1 , a2 , , am是正整数序列，则至 少存在k和 t , 1kt m，使得和 ak + ak+1 + + at 是m的倍数。,证 设Sk = ai , Sh rh mod m 0rhm-1 h = 1 , 2 , , m . 若存在t, St0 mod m 则 命题成立否则，1rhm-1但h = 1 , 2 , , m由鸽巢原理，故存在 rk = rh , 即 Sk Sh，不妨设 h k则 ShSk = ak+1 + ak+2 + + ah 0 mod m,i=1,k,.13 鸽巢

29、原理举例,例 设 a1 , a2 , a3为任意个整数，b1b2b3 为a1 , a2 , a3的任一排列，则 a1b1 , a2b2 , a3b3中至少有一个是偶数,证 由鸽巢原理， a1 , a2 , a3必有两个同奇 偶设这个数被除的余数为 xxy，于 是b1 , b2 , b3中被除的余数有个x，一个 y这样a1b1 , a2b2 , a3b3被除的余 数必有一个为,.13 鸽巢原理举例,例 设a1 , a2 , , a100是由 1和组成的序 列 , 已知从其任一数开始的顺序10个数的和 不超过16即 ai + ai+1 + + ai+9 16，1 i 91 则至少存在 h 和 k

30、，k h，使得 ah + ah+1 + + ak = 39,证 令 Sj = ai，j =1 , 2 , ,100 显然 S1S2 r1, 则 m1, , mn至少有一个数不小于r。,m1 + +mn n,.14 鸽巢原理的推广,定理 若序列S = a1 , a2 , , an2+1中的各数是不等的则 S中至少可选出一组由n+1个元素组成的或为单调增或为单调减的子序列。,证 由S中的每个 ai 向后选取最长单调增子序列，设其长度为li (i=1,2, ,n2+1) ，从而得序列L = l1 , l2 , , lk ,若存在 lkn+1, 则结论成立,.14 鸽巢原理的推广,否则所有的 li 1

31、 , n,其中必有 个相等 设 li1 = li2 = = lin= lin+1 不妨设 i1 ai2 ain+1 ，即有一长度为 n+1的递减子序列 否则 不妨设ai1 li2 ，矛盾,.14 鸽巢原理的推广,例 将 1 , 67 划分为个子集，必有一个子集中有一数是同子集中的另两数之差,证 用反证法设此命题不真即存在划分P1P2P3P4 1,67 ,Pi中不存在一个数是Pi中两数之差，i=1,2,3,4，因 ,故有一子集，其中至少有17个数，设这17个数从小到大为a1 , , a17 不妨设 A=a1 , , a17 。 令bi1= aia1，i = 2，17。,.14 鸽巢原理的推广,设

32、 Bb1 , , b16，bi 1 , 67 。由反证法假设BP1 = 。因而 B( P2 P3 P4 )。 因为 ，不妨设b1 , , b6 P2 ， 令Ci1=bib1，i = 2， ，6 设C C1 , , C5 ，C 1 , 67 由反证法假设C( P1P2 ) = ，故有 C(P3P4 ) 因为 ，不妨设C1 , C2 , C3 P3,.14 鸽巢原理的推广,.14 鸽巢原理的推广,令 di1= CiC1，i = 2 , 3 设 D d1 , d2 , D 1 , 67。 由反证法假设 D( P1P2P3 )= ，因而 D P4 由反证法假设 d2d1 P1P2P3 且d2d1 P4

33、 ， 故 d2d1 1 , 67 ，但显然 d2d1 1 , 67 ，矛盾。,.15 Ramsey问题,Ramsey问题,Ramsey问题可以看成是鸽巢原理的推广下面举例说明Ramsey问题,例 6 个人中至少存在人相互认识或者相互不认识 证 这个问题与K6的边着色存在同色三角形等价假定用红蓝着色,.15 Ramsey 问题,设K6的顶点集为v1 , v2 , , v6 ，dr(v)表 示与顶点 v 关联的红色边的条数，db(v)表示与 v 关联的蓝色边的条数在K6 中，有 dr(v) db(v)，由鸽巢原理可知，至少 有条边同色 现将证明过程用判断树表示如下：,.15 Ramsey 问题,d

34、r(v1)3?,db(v1)3,设(v1v2) (v1v3) (v1v4)为红边,设(v1v2) (v1v3) (v1v4)为蓝边,v2v3v4是红 ?,v2v3v4是蓝 ?,设( v2v3 )是蓝边,设( v2v3 )是红边,v1v2v3是蓝,v1v2v3是红,Y,N,N,N,Y,Y,.15 Ramsey 问题,若干推论,(a) K6的边用红蓝任意着色，则至少有两个同色的三角形。,证 由前定理知，有同色三角形，不妨设 v1v2v3是红色三角形可由如下判断树证明,.15 Ramsey 问题,v1v4v5是蓝,y,y,y,y,y,y,n,n,n,n,n,.15 Ramsey 问题,(b) K9

35、的边红蓝两色任意着色，则必有红K4或蓝色三角形(蓝K4或红色三角形) 证 设个顶点为 v1 , v2 , , v9对个顶点的完全图的边的红、蓝着色图中，必然存在vi ，使得 dr(vi)3 否则，红边数 dr(vi) ，这是不可能的。不妨设 dr(v1)3，可得如下判断树证明结论。,1 2,27 2,.15 Ramsey 问题,dr(v1)4?,db(v1)6,设(v1v2) (v1v3) (v1v4)(v1v5)是4红边,设(v1v2) (v1v7)是6条蓝边,K4(v2v3v4v5)是蓝K4 ?,K6(v2v7)中有红 ?,设(v2v3)是红边,v1v2v3是红,设v2v3v4是蓝,K4(

36、v2v3v4v5)是蓝K4,Y,Y,Y,N,N,N,.15 Ramsey 问题, K9的边红、蓝着色，必有红色三角形或蓝色K4 同理可证 K9的红、蓝着色，必有蓝色三 角形或红色K4 (红 蓝K4) (蓝 红K4) 存在同色K4或红及蓝 同色K4 (红 蓝 ),.15 Ramsey 问题,(c) K18的边红，蓝着色，存在红K4或蓝K4 。,证 设18个顶点为v1 , v2 , , v18 从v1引出的17条边至少有条是同色的，不妨先假定为红色从而可得下面的判断树证明命题,.15 Ramsey 问题,dr(v1)9,db(v1)9,设(v1v2) (v1v10)是红边,K9(v2 v10)中有

37、同色K4 或红加蓝,K10( v1v2 v10)中有同色K4,设(v1v2) (v1v10)是蓝边,K9(v2 v10)中有同色K4 或红加蓝,K10( v1v2 v10)中有同色K4,Y,N,.15 Ramsey数,将上一节的问题一般化：给定一对正整数a、b，存在一个最小的正整数 r ,对 r 个顶点的完全图的边任意红、蓝着色，存在 a 个顶点的红边完全图或 b 个顶点的蓝边完全图。记为 r ( a , b )。比如： r ( 3 , 3 )6，r ( 3 , 4 )9， r ( 4 , 4 )18,Ramsey数的简单性质,.15 Ramsey数,定理 r(a,b)r(b,a)；r(a,2

38、)a,证 K r(a , b )的边红蓝着色，有红Ka或蓝 Kb将红蓝色对换，就有红Kb或蓝Ka 设r(a,b)r，Kr的边任意红蓝着色 红蓝互换后仍是Kr的边的着色，由r(a,b) 的定义，有红Ka或蓝Kb再红蓝对换恢复 原图有红Kb或蓝Ka,.15 Ramsey数,例 K9的边任意红蓝着色，有红三角形或蓝K4红蓝对换后，仍有红三角形或蓝K4，再对换一次，回到原来的着色方案，有蓝三角形或红K4 第二个等式容易看出Ka红蓝着色若不全红(红Ka)，则必有一条蓝边,.15 Ramsey数,定理 当a,b时， r(a,b)r(a1,b)r(a,b1),证 对r(a1,b)r(a,b1) 个顶点的完全图红蓝着色任取其中一点 v，有 dr(v) + db(