《组合数学课件第三章容斥原理与鸽巢原理》由会员分享，可在线阅读，更多相关《组合数学课件第三章容斥原理与鸽巢原理（154页珍藏版）》请在金锄头文库上搜索。
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=133.2 容斥原理容斥原理 容斥原理容斥原理研究有限集合的研究有限集合的交或并交或并 的计数的计数。 DeMorgan定理定理 论域论域U，补集补集,有有3.2 容斥原理容斥原理(a)(b)证证：(a)的证明。设 ,
2、则 相当于 和同时成立，亦即 (1)3.2 容斥原理容斥原理反之，若故(2)由（1）和（2）得(b)的证明和（的证明和（a)类似，从略类似，从略.3.2 容斥原理容斥原理DeMogan定理的推广：设 证明证明：只证(a). N=2时定理已证。设定理对n是正确的，即假定：3.2 容斥原理容斥原理正确即定理对n+1也是正确的。3.2 容斥原理容斥原理2 容斥原理容斥原理 最简单的计数问题是求有限集合A和B的并的元素数目。显然有即具有性质A或B的元素的个数等于具(1)定理定理：3.2 容斥原理容斥原理有性质A和B的元素个数。UBA3.2 容斥原理容斥原理3.2 容斥原理容斥原理证证若AB=，则 |
3、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.2 容斥原理容斥原理( 3 ) ( 1 ) ( 2 ) 得| AB | A | B | AB| + |AB | + | BA| ( | AB | + | AB | ) ( | BA | + | BA | ) | AB | | AB | A | + | B | AB |定理：定理：(2)
4、3.2 容斥原理容斥原理3.2 容斥原理容斥原理ABC3.2 容斥原理容斥原理 例例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？3.2 容斥原理容斥原理令：令：M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合；3.2 容斥原理容斥原理即学校学生数为336人。3.2 容斥原理容斥原理同理可推出：利用数学归纳法可得一般的定理：3.2 容斥原理容斥原理 定理定理设(n,k)是1,n的所有k-子集的集合,
5、 则 |Ai | = (1)k-1 | Ai |证证对n用归纳法。n=2时，等式成立。 假设对n - 1，等式成立。对于n有 3.2 3.2 容斥原理容斥原理ni=1k=1n I(n,k)iI3.2 3.2 容斥原理容斥原理 I(n-1,k) I(n-1,k)iI3.2 3.2 容斥原理容斥原理 I(n,k) I(n-1,k-1) I(n-1,k)此定理也可表示为：定理：定理：设是有限集合，则(4)3.2 容斥原理容斥原理 证：证：用数学归纳法证明。已知 n=2时有设 n-1时成立，即有：3.2 容斥原理容斥原理3.2 容斥原理容斥原理3.2 容斥原理容斥原理3.2 容斥原理容斥原理3.2 容
6、斥原理容斥原理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作为一个元素出现的排列集， 为同时出现ace、df的排列数。3.3 例例根据容斥原理，不出现ace和df的排列数为：=6!- (5!+4!)+3!=582 3.3 例例 例例2 求
7、从1到500的整数中能被3或5除尽的数的个数。 解：解： 令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合3.3 例例被3或5除尽的数的个数为 例例3 求由a,b,c,d四个字母构成的位符号串中，a,b,c,d至少出现一次的符号串数目。3.3 例例 解：解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。 由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是3.3 例例 a，b，c至少出现一次的n位符号串集合即为3.3 例例 例例4。求不超过120的素数个数。 因 ，故不超过120的合数必然是2、3、5、7的倍数，而且不
8、超过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=303.3 例例 例例5。用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。 解：解：所有排列中，令：3.3 例例3.3 例例 出现dog字样的排列，相当于把dog作为一个单元参加
9、排列，故类似有： 由于god,dog不可能在一个排列中同 时出现，故： 类似：类似：3.3 例例 由于gum,dog可以在dogum字样中同时出现，故有： 类似有god和depth可以在godepth字样中同时出现，故 god和thing可以在thingod字样中同时出现，从而 3.3 例例3.3 例例 由于god、depth、thing不可以同时出现，故有： 其余多于3个集合的交集都为空集。3.3 例例 故满足要求的排列数为： 3.3 例例 例例6。求完全由n个布尔变量确定的布而函数的个数。 解：解：设 布尔函数类为： 由于n个布尔变量 的不同的真值表数目与 位2进制数数目相同，故为 个。根
10、据容斥原理，满足条件的函数数目为：3.3 例例3.3 例例3.3 例例这10个布尔函数为：x1x2，x1x2，x1x2， x1x2，x1x2，x1x2，x1x2， x1x2，(x1x2)(x1x2)， (x1x2)(x1x2) 例例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，此外尚有一个1。3.3 例例 4 错排问题错排问题 n个元素依次给以标号1，2，
11、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个字母的全排列中，令分别表A,C,E,G在原来位置上的排列，则错排数为：3.4 错排
12、问题错排问题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=6303.4 错排问题错排问题5 棋盘多项式和有限制排列棋盘多项式和有限制排列1. 有限制排列有限制排列3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列 例例4个x ，3个y，2个z的全排列中，求不出现xxxx，yyy，zz图象的排列。 解解设出现xxxx的排列的集合记为A1，
13、 |A1|= =60; 设出现yyy的排列的集合记为A2， | A2|= =105；6!1!3!2! 4!2! 7!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!3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列2棋子多项式 n个不同元素的一个
14、全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子xxxxx 如图所示的布局对应于排列41352。3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列 可以把棋盘的形状推广到任意形状： 布子规定称为无对攻规则，棋子相当于 象棋中的车。 令r k（C）表示k个棋子布到棋盘C上的方案数。如：3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列r1( )=1，r1( )=2，r1( )=2，r2( )=0，r2( )=1。为了形象化起见，（ ）中的图象便是棋盘的形状。3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列定义定义设C为一棋盘，称R(C)= rk(
15、C) xk为C的棋盘多项式。规定 r0(C)=1，包括C=时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有rk(C)=rk1(Ci)rk(Ce)，k=03.5 棋盘多项式和有限制排列棋盘多项式和有限制排列即对任一指定的格子，要么布子，所得的方案数为 rk1(Ci)；要么不布子，方案数为 rk(Ce)。设C有n个格子，则 r1(C)nr1(C)r0(Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故规定 r0(C)1是合理的3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列即对任一指定的格子，要么布子，所得的方案数为 r
16、k1(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=03.5 棋盘多项式和有限制排列棋盘多项式和有限制排列例如：R( )=1+ x；R( )= xR( )+ R( )= x+ (1+ x)=1+2x；R( )= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x23.5 棋盘多项式和有限制排列棋盘多项式和有限制排列 如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2
17、的格子。则有： 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)3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列利用（）和（），可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。例例R ( ) = xR( )+R( ) = x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3*R( ) = xR( ) + R( ) = 1+6x +10 x2 +4x3
18、3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列有禁区的排列例设对于排列P=P1 P2 P3 P4，规定P1，P、， P2、， P42。 1 2 3 4P1P2P3P412 4 314 3223431 214这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。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
19、, 2 , 3, ,n。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 n3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列上例方案数为 4!6(41)!11(42)!7(43)! 1(4)!4例例，四位工人，A，B，C，D四项任务。条件如下：不干B；不干B、C；不干C、D；不干D。
20、问有多少种可行方案？3.5 棋盘多项式和有限制排列棋盘多项式和有限制排列解由题意，可得如下棋盘： 其中有影线的格子表示禁区。A B C D1 2 3 4 R( )=1+6x+10x2+4x3 方案数=4!6(41)!+10(42)!4(43)! +0(44)!=43.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
21、 n nk=0 k! 1 k n3.6一般公式一般公式 3.6一般公式若将.2中的例子改为“单修一门数学的学生有多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”则相应的答案表示如下：MPC；MPC+MPC+MPCMPC+MPC+MPC3.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 = |
22、Aij |qk =| ( Ai) ( Aj)| I(n ,k)i I I(n ,k)i Ij I3.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 + i3.6一般公式一般公式而 (1)i ( ) ( ) = (1)i ( ) ( ) = (1)i ( ) ( ) = ( ) (1)i ( ) = ( )
23、 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 k3.6一般公式一般公式前例中只修一门课的学生为： | MPC | + | MPC | + | MPC |= q1= (1)j - 1 ( ) Pj= P1 2P2 + 3P3j1j =1 3 在一般公式中，若令 P0 = N， q0 = | A1A2An |，就得到原来的容斥原理。3.6一般公式一般公式证证根据定义 qk =| ( Ai) ( Aj)|qk由Pk+
24、j的代数和组成，符号 (1)j ，计算Pk+j的重复度：k + j个集的交的绝对值的项的总个数为( ) ( ) , 共 ( )种。每一项的重复度为 ( ) ( ) ( ) = ( ) 从而Pk+j的重复度也是 ( ) I(n ,k)i Ij Inkk + jk + jk + jk + jjnknknnnkjkk3.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=
25、jm1 k = m0 k m 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 km3.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
26、+ i ki=0nkk + i mnk i = 01 k =m0 km3.6一般公式一般公式例例某校有个教师，已知教数学的有位，教物理的有位，教化学的位；数、理位，数、化位，理、化位；数理化位。问教其他课的有几位？只教一门的有几位？只好教两门的有几位？解解令教数学的教师属于A1，教物理的属于A2，教化学的属于A3。则P0，P1| A1 |+| A2|+| A3 |8+6+5;P2| A1A2|+ | A1A3|+| A2A3|12；P3| A1A2A3|3； 3.6一般公式一般公式故教其他课的老师数为：q0P0 P1 +P2P3恰好一门的教师数：q1P12P2 + 3P34恰好教两门的老师数为
27、：q2P23P333.6一般公式一般公式例例n 对夫妻围坐问题设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？解解不妨设 n 个女人先围成一圈，方案数为( n1 )! 。对任一这样的给定方案，顺时针给每个女人以编号1 , 2 , , n。设第i号与第 i + 1号女人之间的位置为第 i 号位置，1 i n1。第 n 号女人与第1 号之3.6一般公式一般公式间的位置为第 n 号位置。设第 i 号女人的丈夫的编号也为第 i 号，1 i n。让 n 个男人坐到上述编号的 n 个位置上。设 ai是坐在第 i 号位置上的男人，则 ai i ，i + 1， i n1；an
28、n，1。这样的限制也即要求在下面3行n列的排列中 nn n1 a1 a2 a3 an1 an3.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)iI3.6一般公式一般公式也就是从( 1 , 2 ) ( 2 , 3 ) ( n, n ) ( n , 1)这n对数的k 对中各取一数，且互不相同的取法的计数。这相当于从1
29、 , 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 2n2nk3.6一般公式一般公式 Un =(1)k ( )(nk)! = Ai 2n2nk2nk ki 1 , n .11反演反演基本想法：an 易算，bn难算，an可用bn表示，利用反演，将bn用an表示二项式反演二项式反演引理引理.11反演反演证证.11反演反演定理定理证证.11反演
30、反演推论证在定理中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!.11反演反演Mbus反演定义设 n Z+ 1，若 n = 1;( n ) = 0，若n = p11 p22 pkk 存在i1 (1)k ，若n = p1p2pk 如 ( 30) = ( 235 ) = (1)3 ( 12) = 0；.11反演反演定理定理设n Z+ 则 ( d ) = 1，若n = 1；0，若n 1；d | n证证
31、若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.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.11反演反演定理定理( Mbus反演定理 )设 f (
32、n )和g ( n )是定义在正整数集合上的两个函数 f ( n ) = g (d ) = g ( ) (M1 ) g( n ) = (d) f ( ) = ( )f (d) (M2) ndndd | nd | nd | nd | n则( M1 ) ( M2 ) nd.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 | n
33、ndd1 | ndd1 | ndnd1d | 1，d1 = n0，d1 n.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 + + a
34、k = 39 .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则.8鸽巢原理之二鸽巢原理之二鸽子总数 m1 + m2 + +mnn ，与假设相矛盾推论推论m只鸽子进n个巢，至少有一个巢里有 |只鸽子nm推论推论n(m1) +
35、1只鸽子进n个巢，至少有一个巢内至少有m只鸽子推论推论若m1 , m2 , , mn是正整数，且 r1,则 m1, , mn至少有一个不小于rm1 + +mn n.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.8鸽巢原理之二鸽巢原理之二证证在C =
36、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位对应相等.8鸽巢原理之二鸽巢原理之二定理定理若序列S = a1 , a2 , , amn+1中的各数是不等的m , n 是正整数，则 S有一长度为m+1的严格增子序列或长度为n+1的减子序列，而且 S有一长度为m+1的减子序列或长度为n+1的增子序列证证由S中的每个 ai 向后选取最长增子序列，
37、设其长度为li ，从而得序列L = l1 , l2 , , lmn+1 若存在 lkm+1则结论成立.8鸽巢原理之二鸽巢原理之二否则所有的 li 1 , m，其中必有 | = n+1个相等设li1 = li2 = = lin= lin+1 不妨设 i1i2 ai2 ain+1 ，即有一长度为n+1的减子列否则不妨设ai1 li2 ，矛盾mn+1 m.8鸽巢原理之二鸽巢原理之二证证从ai 向后取最长增子列及减子列，设其长度分别为 li ，li .若任意 i ，都有li 1，m, li，n,不超过mn种对则存在 j k，( lj , lj ) = ( lk , lk )若aj lk，若aj ak，
38、则 lj lk ，矛盾.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.8鸽巢原理之二鸽巢原理之二设Bb1 , , b16，B 1 , 65 。由反证法假设BP1 = 。因而 B ( P2 P3 P4 )。 因为 6，不妨设b1 , , b6 P
39、2 ， 令Ci1=bib1，I = 2， ，6设C C1 , , C5 ，C 1 , 65 由反证法假设C( P1P2 ) =，故有 C (P3P4 )因为 3，不妨设C1 , C2 , C3 P316 352.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 ，矛盾。.9Ramsey 问题问题RamseyRamsey问题问题 Ramsey问题可以看成是鸽巢原理
40、的推广下面举例说明Ramsey问题例例6 个人中至少存在人相互认识或者相互不认识证证这个问题与K6的边着色存在同色三角形等价假定用红蓝着色.9Ramsey 问题问题设K6的顶点集为v1 , v2 , , v6 ，dr(v)表示与顶点 v 关联的红色边的条数，db(v)表示与 v 关联的蓝色边的条数在K6 中，有dr(v) db(v)，由鸽巢原理可知，至少有条边同色现将证明过程用判断树表示如下：.9Ramsey 问题问题dr(v1)3?db(v1)3设(v1v2) (v1v3) (v1v4)为红边设(v1v2) (v1v3) (v1v4)为蓝边v2v3v4是红 ?v2v3v4是蓝 ?设( v2v
41、3 )是蓝边设( v2v3 )是红边v1v2v3是蓝v1v2v3是红YNNNYY.9Ramsey 问题问题若干推论若干推论( ( a )a )K6的边用红蓝任意着色，则至少有两个同色的三角形证证由前定理知，有同色三角形，不妨设v1v2v3是红色三角形可由如下判断树证明.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
42、) 为红边v2v3v5是红?设 (v2v5)为蓝边v2v4v5是蓝v4v5v6是红v1v5v6是蓝?设 (v5v6)为红边yyyyyynnnnn.9Ramsey 问题问题( ( b )b )K9 的边红蓝两色任意着色，则必有红K4或蓝色三角形(蓝K4或红色三角形)证证设个顶点为 v1 , v2 , , v9对个顶点的完全图的边的红、蓝着色图中，必然存在 vi ，使得 dr(vi)3 否则，红边数 dr(vi) ，这是不可能的不妨设 dr(v1)3，可得如下判断树证明结论1227 2.9Ramsey 问题问题dr(v1)4?db(v1)6设(v1v2) (v1v3) (v1v4)(v1v5)是4
43、红边设(v1v2) (v1v7)是6条蓝边K4(v2v3v4v5)是蓝K4 ?K6(v2v7)中有红 ?设(v2v3)是红边v1v2v3是红设v2v3v4是红K4(v2v3v4v5)是蓝K4YYYNNN.9Ramsey 问题问题K9的边红、蓝着色，必有红色三角形或蓝色K4同理可证 K9的红、蓝着色，必有蓝色三角形或红色K4 (红 蓝K4) (蓝 红K4)存在同色K4或红及蓝 同色K4 (红 蓝 ).9Ramsey 问题问题( ( c )c )K18的边红，蓝着色，存在红K4或蓝K4 证证设18个顶点为v1 , v2 , , v18 从v1引出的17条边至少有条是同色的，不妨先假定为红色从而可得
44、下面的判断树证明命题.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.10Ramsey数数将上一节的问题一般化：给定一对正整数a、b，存在一个最小的正整数 r ,对 r 个顶点的完全图的边任意红、蓝着色，存在 a 个顶点的红边完全图或 b 个顶点的蓝边完全图。记为 r ( a , b )。比如：r ( 3 , 3 )6，r ( 3 , 4 )9，r ( 4
45、 , 4 )18RamseyRamsey数的简单性质数的简单性质.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 .10Ramsey数数例例K9的边任意红蓝着色，有红三角形或蓝K4红蓝对换后，仍有红三角形或蓝K4，再对换一次，回到原来的着色方案，有蓝三角形或红K4第二个等式容易看出Ka红蓝着色若不全红(
46、红Ka)，则必有一条蓝边.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从而可得判断树如下.10Ramsey数数dr(v)r (a1 , b) ? db(v)r (a, b 1 )与 v 以红边相连的r(a1 , b)个顶点的完全图中有一个红Ka1 ?有蓝Kb红Ka或蓝KbV与这a1个点构成红KaNYYN.10Ramsey数数推论
47、推论r (a , b ) ( )a + b2 a1证证 r ( a , b ) r ( a 1 , b ) r ( a , b1 ) ( )( ) ( ) a + b2 a1a + b3 a2a + b3 a1.10Ramsey数数定理定理若 a ，则 r ( a , a) 2a2证证Kn有 ( )条边，对边红蓝着色有2 种方案其中同色Ka的方案数不超过n2n2( )a2( )( ) 2 2n2( ) n2Ka的个数可红可蓝可任意着色边数同色边数.10Ramsey数数这是一个上界Kn中含Ka的方案被重复计数若取n足够小，便得a2( ) ( ) 2na( ) + 1 n an即( ) 2 n=
48、2 时( ) 2a2 .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)表示.10Ramsey数数有 r (a1 , a2 , , ak) r ( a1 ,
49、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 着色，将后n1中色看作同一种色，出现第一色Ka 1或另一色(n1种色看作另一色）的Kq即出现第 I 色Ka i ，I = 2 , , n. 故 r (a1 , a2 , , ak) p.10Ramsey数数例例r ( 3 , 3 , 3) = 17证证设三色为 r ,b ,g则对K17的任一顶点v 有dr(v) + db(v) + dg(v) = 16；因 =6 ,故任一顶点与其他顶点的连线中，至少有条同色不妨设dr(v1)6, (v1v2)(v1v7)都是红边从而可得如下判断树16 3.10Ramsey数数K6(v2v7)中无红边 ?K6(v2v7)中有红边K6(v2v7)中蓝绿着色有蓝K3或绿K3设(v2v3)为红边v1v2v3是红色的原题得证YN本文观看结束！谢 谢欣 赏！
