课件：组合数学-容斥原理

第三章 容斥原理和鸽巢原理

§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)的证明和（a)类似，从略.§3.2容斥原理DeMogan定理的推广：设

证明：只证(a).N=2时定理已证。设定理对n是正确的，即假定：§3.2容斥原理正确即定理对n+1也是正确的。§3.2容斥原理§2容斥原理最简单的计数问题是求有限集合A和B的并的元素数目。显然有即具有性质A或B的元素的个数等于具(1)定理：§3.2容斥原理有性质A和B的元素个数。UBA§3.2容斥原理§3.2容斥原理证若A∩B=φ，则|A∪B|=|A|+|B||A|＝|A∩(B∪B)|＝|(A∩B)∪(A∩B)|＝|A∩B|+|A∩B|(1)同理|B|＝|B∩A|+|B∩A|(2)|A∪B|＝|(A∩(B∪B))∪(B∩(A∪A))|＝|(A∩B)∪(A∩B)∪(B∩A)∪(B∩A)|＝|A∩B|+|A∩B|+|B∩A|(3)§3.2容斥原理(3)－(1)－(2)得|A∪B|－|A|－|B|＝|A∩B|+|A∩B|+|B∩A|－(|A∩B|+|A∩B|)－(|B∩A|+|B∩A|)＝－|A∩B|∴|A∪B|＝|A|+|B|－|A∩B|定理：(2)§3.2容斥原理§3.2容斥原理ABC§3.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-子集的集合,则|∪Ai|=∑(－1)k-1∑|∩Ai|证

对n用归纳法。n=2时，等式成立。

假设对n-1，等式成立。对于n有

§3.2容斥原理ni=1k=1n

I∈￠(n,k)i∈I§3.2容斥原理

I∈￠(n-1,k)

I∈￠(n-1,k)i∈I§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容斥原理§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求从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的倍数，而且不超过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个英文字母作不允许重复的全排列，要求排除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个集合的交集都为空集。§3.3例故满足要求的排列数为：

§3.3例

例6。求完全由n个布尔变量确定的布而函数的个数。

解：设布尔函数类为：

由于n个布尔变量的不同的真值表数目与位2进制数数目相同，故为个。根据容斥原理，满足条件的函数数目为：§3.3例§3.3例§3.3例这10个布尔函数为：x1∧x2，x1∧x2，x1∧x2，x1∧x2，x1∨x2，x1∨x2，x1∨x2，x1∨x2，(x1∨x2)∧(x1∨x2)，(x1∨x2)∧(x1∨x2)例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，…，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错排问题§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错排问题§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!§3.5棋盘多项式和有限制排列设出现zz的排列的集合记为A3，|A3|==280；|A1∩A2|==12；|A1∩A3|==20；|A2∩A3|==30；|A1∩A2∩A3|=3!=6；

全排列的个数为：=1260；所以：

|A1∩A2∩A3|=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个不同元素的一个全排列可看做n个相同的棋子在n×n的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子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(C)xk为C的棋盘多项式。规定r0(C)=1，包括C=Ф时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有

rk(C)=rk－1(Ci)＋rk(Ce)，k=0∞§3.5棋盘多项式和有限制排列即对任一指定的格子，要么布子，所得的方案数为rk－1(Ci)；

要么不布子，方案数为rk(Ce)。设C有n个格子，则r1(C)＝n．r1(C)＝r0(Ci)+r1(Ce)，∵r1(Ce)＝n－1∴r0(Ci)＝1．故规定r0(C)＝1是合理的．§3.5棋盘多项式和有限制排列即对任一指定的格子，要么布子，所得的方案数为rk－1(Ci)；

要么不布子，方案数为rk(Ce)。从而

R(C)=∑rk(C)xk

＝１＋∑[rk－1(Ci)+

rk(Ce)]xk=x∑rk(Ci)xk+∑rk(Ce)xk

＝xR(Ci)+R(C

e)(3)∞k=0∞∞∞k=0k=0k=0§3.5棋盘多项式和有限制排列例如：R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=xR()+R()=x(1+x)+1+x=1+2x+x2§3.5棋盘多项式和有限制排列如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：

rk(C)=∑ri(C1)rk－i(C2)i=0k故R(C)=∑(∑ri(C1)rk－i(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+10x2+4x3§3.5棋盘多项式和有限制排列３．有禁区的排列例设对于排列P=P1P2P3P4，规定P1≠３，P２≠１、４，P３≠2、４，P4≠2。1234P1P2P3P41243143223431214这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。§3.5棋盘多项式和有限制排列定理设ri为I个棋子布入禁区的方案数，i=1,2,3,···,n。有禁区的布子方案数（即禁区内不布子的方案数）为

r0n!－r1(n－1)!＋r2(n－2)!－···＋(－1)nrn＝∑(－1)krk

(n－k)!

k=0n证设Ai

为第i个棋子布入禁区，其他棋子任意布的方案集，i=1,2,3,…,n。§3.5棋盘多项式和有限制排列则所有棋子都不布入禁区的方案数为｜A1∩A2∩···∩An｜＝n！＋∑(－1)k∑｜∩Ai｜I∈￠(n,k)ni∈Ik=0而∑｜∩Ai｜正是k个棋子布入禁区，其他n-k个棋子任意布的方案数。由假设可知等于rk(n－k)！(注意：布入禁区的棋子也要遵守无对攻规则）.所以｜A1∩A2∩···∩An｜=n!+∑(－1)krk

(n－k)!I∈￠(n,k)i∈Ik=0

n§3.5棋盘多项式和有限制排列上例方案数为4!－6(4－1)!＋11(4－2)!－7(4－3)!＋1(4－４)!＝4例１，２，３，４四位工人，A，B，C，D四项任务。条件如下：１不干B；２不干B、C；３不干C、D；４不干D。问有多少种可行方案？§3.5棋盘多项式和有限制排列解由题意，可得如下棋盘：其中有影线的格子表示禁区。ABCD1234

R()=1+6x+10x2+4x3

方案数=4!－6(4－1)!+10(4－2)!－4(4－3)!+0(4－4)!=4§3.5棋盘多项式和有限制排列例三论错排问题错排问题对应的是n×n的棋盘的主对角线上的格子是禁区的布子问题。C=···R(C)=(1+x)n=∑()xk令rk=()

nk=0

n

k

n

k故R(C)中的xn:n!+∑(－1)k()(n－k)!=n!∑(－1)k－=Pnk=1

n

nk=0

k!1

k

n§3.6一般公式

§3.6一般公式若将§３.2中的例子改为“单修一门数学的学生有多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”则相应的答案表示如下：｜M∩P∩C｜；｜M∩P∩C｜+｜M∩P∩C｜+｜M∩P∩C｜｜M∩P∩C｜+｜M∩P∩C｜+｜M∩P∩C｜§3.6一般公式设有与性质１,2,···,n相关的元素N个，Ai为有第i种性质的元素的集合.i=1,2,…,nPk为至少有k种性质的元素的元次；qk为恰有k种性质的元素的个数。P0=N，P1=|A1|+|A2|+···+|An|，P2=|A1∩A2|+|A1∩A3|+···+|An-1∩An|Pk=∑|∩Aij|qk=∑|(∩Ai)∩(∩Aj)|

I∈￠(n,k)i∈I

I∈￠(n,k)i∈Ij∈I§3.6一般公式定理qk=∑(－1)i()Pk+i

k+iii=0n-k证１设某一元素恰有k种性质，则其对Pk的某一项的贡献为１，而对Pk+1，Pk+2,···,Pn的贡献都是０。若某一元的性质少于k种则其对Pk，Pk+1，···，Pn的贡献都是０。若恰有k+j种性质，则其对Pk的贡献是(),对Pk+i的贡献是（）k+j

kk+jk+i§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§3.6一般公式前例中只修一门课的学生为：|M∩P∩C|+|M∩P∩C|+|M∩P∩C|=q1=∑(－1)j-1()Pj=P1－2P2+3P3j1j=13在一般公式中，若令

P0=N，q0=|A1∩A2∩···∩An|，就得到原来的容斥原理。§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+jjn－kn－knnnkjkk§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=()，若j＞m，则Pj=0；由定义，得qk=｛jm1k=m0k≠m§3.6一般公式右端＝∑(－1)i()Pk+i

＝∑(－1)i()()＝∑(－1)i()()={k+iii=0n－kk+ik

mk+ii=0n－k

mk

m-kii=0n－k1k=m0k≠m假设对于N－1，等式成立。对于N，设新增元有m种性质，对于N个元的P’j＝Pj＋()，q’k＝｛jm1k=m0k≠m§3.6一般公式右端＝∑(－1)i()P’k+i＝∑(－1)i()[Pk+i+()]＝∑(－1)i()Pk+i+∑(－1)i()()＝qk+｛等式成立．k+i

ki=0n－kk+i

kk+i

mk+i

ki=0n－kk+i

ki=0n－kk+i

mn－k

i=01k=m0k≠m§3.6一般公式例某校有１２个教师，已知教数学的有８位，教物理的有６位，教化学的５位；数、理５位，数、化４位，理、化３位；数理化３位。问教其他课的有几位？只教一门的有几位？只好教两门的有几位？解令教数学的教师属于A1，教物理的属于A2，教化学的属于A3。则P0＝１２，P1＝|A1|+|A2|+|A3|＝8+6+5＝１９;P2＝|A1∩A2|+

|A1∩A3|+|A2∩A3|＝12；P3＝|A1∩A2∩A3|＝3；§3.6一般公式故教其他课的老师数为：

q0＝P0－P1+P2－P3＝２恰好一门的教师数：

q1＝P1－2P2+3P3＝4恰好教两门的老师数为：

q2＝P2－3P3＝3§3.6一般公式例

n对夫妻围坐问题设n对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？解不妨设n个女人先围成一圈，方案数为(n－1)!。对任一这样的给定方案，顺时针给每个女人以编号1,2,···,n。设第i号与第

i+1号女人之间的位置为第

i号位置，1≤i≤n－1。第n号女人与第1号之§3.6一般公式间的位置为第n号位置。设第

i号女人的丈夫的编号也为第

i号，1≤i≤n。让n个男人坐到上述编号的

n个位置上。设

ai是坐在第

i号位置上的男人，则

ai≠i，i+1，１≤i≤n－1；an≠n，1。这样的限制也即要求在下面3行n列的排列中１２３······n－１n２３４······n1a1a2a3

······an－1an§3.6一般公式每列中都无相同元素。满足这样的限制的排列a1a2···an称为二重错排。设二重错排的个数为Un，原问题所求的方案数就是Un(n－1)！。设Ai为ai=I或

I+1(1≤I≤n－1)，an=n

或1的排列a1a2···an的集合。则｜Ai｜=2(n－1)!，关键是计算∑|∩Ai|

I∈￠(n,k)i∈I§3.6一般公式也就是从(1,2)(2,3)···(n－１,n)(n,1)这n对数的k对中各取一数，且互不相同的取法的计数。这相当于从1,2,2,3,3,4,···,n－1,n－1,n,n,1中取

k个互不相邻数的组合的计数，但首尾的１不能同时取。回想无重复不相邻组合的计数：

C’(n,r)=C(n－r+1,r),这里所求的是()－()=()

2n－k+1k2n－4－(k－2)+1k－22n－kk2n2n－k§3.6一般公式∴Un=∑(－1)k()(n－k)!=｜∩Ai｜2n2n－k2n－kki∈[1,n]§３.11反演基本想法：{an}易算，{bn}难算，{an}可用｛bn｝表示，利用反演，将{bn}用{an}表示．１．二项式反演引理§３.11反演证

§３.11反演定理证§３.11反演推论证在定理中bk处用(－1)kbk代入，即可．例n!=∑()Dn－k，Dn=bn，令n－k=l，则n!=∑()DlDn=∑(－1)n-k()k!=n!∑(－1)n-k

=n∑nknknk1(n－k)!k=0k=0k=0nnn(－1)kk!§３.11反演２．Mǒbíus反演定义设n∈Z+

1，若n=1;μ(n)=0，若n=p1α1p2α2···pkαk存在αi>1(－1)k，若n=p1p2···pk

如μ(30)=μ(2·3·5)=(－1)3

μ(12)=0；§３.11反演定理设n∈Z+

则∑μ(d)=1，若n=1；0，若n>1；d|n证若n=1，∑μ(d)=μ(1)=1,成立．若

n>1，设n=p1α1p2α2···pkαk，n’=p1p2···pk

∑μ(d)=∑μ(d)=∑∑μ(∏pi)+μ(1)=1+∑()(－1)j=(1－1)k=0d|nd|nd|n’j=1ki∈II∈￠(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|n’1pij=1i=1kkI∈￠(k,j)i∈I§３.11反演定理(Mǒbíus反演定理)设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§３.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§３.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<n§３.11反演例圆排列问题设a1a2···an

是一个圆排列，即a2a3···ana1,···,ana1···an－1，看作是相同的。为了加以区别，必要时把原先的排列称为线排列。一个圆排列在n个位置短开形成的

n个线排列在元素可重复的情况下，未必都不相同。例如，d｜n时，由不重复的a1a2···ad重复n／d次构成的圆排列

§３.11反演(a1a2···ad)···(a1a2···ad)

nd组只能形成d个不同的线排列。若一个圆排列可由一个长度为k的线排列重复若干次形成，则这样的k中最小者成为该圆排列的周期。一个圆排列中元素的个数（重复出现的按其重复次数计）称为它的长度§３.11反演设集合｛1,2,···,m｝中元素形成的长度与周期都是d的圆排列的个数为M(d)。设n是一给定的正整数。若

d｜n，每个长度与周期都是d的圆排列可在d个位置上断开，重复

n/d次形成d个长度为

n的可重排列。因此有∑dM(d)=mn

由Mǒbíus反演定理nM(n)=∑μ(d)m故M(n)=∑μ(d)md｜nd｜nd｜nndnd§３.11反演设长度为n的圆排列的个数为T(n)，则

T(n)＝∑M(d)d｜n例

m={1,2}，n=7则

M(7)=(27－2)=18T(7)=∑M(d)=M(1)+M(7)=20d｜717§３.7鸽巢原理之一鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”例１367人中至少有２人的生日相同。例２10双手套中任取11只，其中至少有两只是完整配对的。例３参加一会议的人中至少有２人认识的别的参加者的人数相等。§３.7鸽巢原理之一例４从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=2αir,aj=2αjr若αi＞αj，则ai是aj的倍数。§３.7鸽巢原理之一例５设a1,a2,···,am是正整数序列，则至少存在k和l,1≤k≤l≤m，使得和

ak+ak+1+···+al

是m的倍数。证设Sk=∑ai,Sh≡rhmodm0≤rh≤m-1h=1,2,···,m.若存在l,Sl≡0modm则命题成立．否则，1≤rh≤m-1．但h=1,2,···,m．由鸽巢原理，故存在rk=rh,即Sk≡Sh，不妨设h＞k．则

Sh－Sk=ak+1+ak+2+…+ah≡0modmi=1h§３.7鸽巢原理之一例６设a1,a2,a3为任意３个整数，b1b2b3为a1,a2,a3的任一排列，则a1－b1,a2－b2,

a3－b3中至少有一个是偶数．证由鸽巢原理，a1,a2,a3必有两个同奇偶．设这３个数被２除的余数为xxy，于是b1,b2,b3中被２除的余数有２个x，一个y．这样a1－b1,a2－b2,a3－b3被２除的余数必有一个为０．§３.7鸽巢原理之一例７设a1,a2,···,a100是由1和２组成的序列,已知从其任一数开始的顺序10个数的和不超过16．即

ai+ai+1+…+ai+9

≤16，1≤i≤91则至少存在

h和

k，k>h，使得

ah+ah+1+…+ak=39证令Sj=∑ai，j=1,2,…,100显然S1<S2<…<S100，且S100=(a1+…+a10)+(a11+…+a20)+…+(a91+…+a100)i=1j§３.7鸽巢原理之一根据假定有S100≤10×16=160作序列S1,S2,…,S100,S1+39,…,S100+39.共200项．其中最大项S100+39≤160+39由鸽巢原理，必有两项相等．而且必是前段中某项与后段中某项相等．设

Sk=Sh+39，k>hSk－Sh=39即

ah+ah+1+…+ak=39§３.8鸽巢原理之二鸽巢原理二m1,m2,…,mn都是正整数，并有m1+m2+…+mn－n+1个鸽子住进n个鸽巢，则至少对某个i有第i个巢中至少有mi个鸽子，i=1,2,…,n．上一小节的鸽巢原理一是这一原理的特殊情况，即m1=m2=…=mn=2，

m1+m2+…+mn－n+1=n+1如若不然，则对任一i，都有第

i个巢中的鸽子数≤mi－1则§３.8鸽巢原理之二鸽子总数≤m1+m2+…+mn－n

，与假设相矛盾．推论１

m只鸽子进n个巢，至少有一个巢里有「－|只鸽子．nm推论２

n(m－1)+1只鸽子进n个巢，至少有一个巢内至少有m只鸽子．推论３若m1,m2,…,mn是正整数，且>

r－1,则m1,…,mn至少有一个不小于rm1+…+mnn§３.8鸽巢原理之二例设A=a1a2···a20是10个0和10个1组成的２进制数．B=b1b2···b20是任意的２进制数．C=b1b2···b20b1b2···b20=C1C2···C40，则存在某个i，1≤i≤20，使得CiCi+1···Ci+19与a1a2···a20至少有10位对应相等．…...…...............ABC第i格第i+19格12·········192012·······192012········19201······1920§３.8鸽巢原理之二证在C=C1C2···C40中，当i遍历1,2,…,20时，每一个bj历遍a1,a2,…,a20．因A中有10个0和10个1，每一个bj都有10位次对应相等．从而当i历遍1,…,20时，共有10·20=200位次对应相等．故对每个i平均有20020=10位相等，因而对某个i至少有10位对应相等．§３.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}．若存在lk≥m+1则结论成立．§３.8鸽巢原理之二否则所有的li∈[1,m]，其中必有「|=n+1个相等．设li1

=li2=···=lin=lin+1不妨设i1<i2<···<in+1应有ai1>ai2>···>ain+1，即有一长度为n+1的减子列．否则不妨设ai1<ai2，则有li1>li2，矛盾．mn+1m§３.8鸽巢原理之二证２从ai

向后取最长增子列及减子列，设其长度分别为li，l’i.若任意i，都有li

∈[1，m],l’i∈［１，n］,不超过mn种对．则存在j<k，(lj,l’j)=(lk,l’k)若aj<ak，则lj>lk，若aj>ak，则l’j>l’k，矛盾．§３.8鸽巢原理之二例将[1,65]划分为４个子集，必有一个子集中有一数是同子集中的两数之差．证用反证法．设次命题不真．即存在划分P1∪P2∪P3∪P4＝[1，65]，Pi中不存在一个数是Pi中两数之差，i=1,2,3,4因

=17，故有一子集，其中至少有17个数，设这17个数从小到大为a1,…,a17

．不妨设A={a1,…,a17}P1。令bi－1=ai－a1，i=2，···，17。654§３.8鸽巢原理之二设B＝｛b1,···,b16}，B[1,65]。由反证法假设B∩P1=ф。因而

B(P2∪P3∪P4)。

因为＝6，不妨设{b1,···,b6}P2，令Ci－1=bi－b1，I=2，···，6设C＝{C1,···,C5}，C[1,65]由反证法假设C∩(P1∪P2)=ф，故有

C(P3∪P4)因为＝3，不妨设{C1,C2,C3}P316352§３.8鸽巢原理之二令di－1=Ci－C1，I=2,3设D＝{d1,d2},D[1,65]。由反证法假设D∩(P1∪P2∪P3)=ф，因而

DP4。由反证法假设

d2－d1∈P1∪P2∪P3

且d2－d1∈P4，故d2－d1∈[1,65]，但显然

d2－d1∈[1,65]，矛盾。§３.9Ramsey问题１．Ramsey问题

Ramsey问题可以看成是鸽巢原理的推广．下面举例说明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是蓝△?设(v2v3)是蓝边设(v2v3)是红边△v1v2v3是蓝△△v1v2v3是红△√√YNNNYY§３.9Ramsey问题２．若干推论(

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)为红边△v2v3v5是红△?设(v2v5)为蓝边△v2v4v5是蓝△△v4v5v6是红△△v1v5v6是蓝△?设(v5v6)为红边√√√yyyyyynnnnn§３.9Ramsey问题(b)K9

的边红蓝两色任意着色，则必有红K4或蓝色三角形(蓝K4或红色三角形)．证设９个顶点为v1,v2,···,v9．对９个顶点的完全图的边的红、蓝２着色图中，必然存在vi，使得dr(vi)≠3．否则，红边数＝∑dr(vi)＝，这是不可能的．不妨设

dr(v1)≠3，可得如下判断树证明结论．12272§３.9Ramsey问题dr(v1)≥4?db(v1)≥6设(v1v2)(v1v3)(v1v4)(v1v5)是4红边设(v1v2)···(v1v7)是6条蓝边K4(v2v3v4v5)是蓝K4?K6(v2···v7)中有红△?设(v2v3)是红边△v1v2v3是红△设△v2v3v4是红△K4(v2v3v4v5)是蓝K4√√YYYNNN§３.9Ramsey问题∴K9的边红、蓝２着色，必有红色三角形或蓝色K4．同理可证K9的红、蓝２着色，必有蓝色三角形或红色K4．

(红△∨蓝K4)∧(蓝△∨红K4)＝存在同色K4或红△及蓝△＝同色K4∨(红△∧蓝△)§３.9Ramsey问题(c)K18的边红，蓝２着色，存在红K4或蓝K4

．证设18个顶点为v1,v2,···,v