组合数学第三章容斥原理与鸽巢原理

1、关于组合数学第三章容斥原理和鸽巢原理第一张，PPT共一百五十页，创作于2022年6月 3的倍数是：3，6，9，12，15， 18。 6个但答案不是10+6=16 个，因为6，12，18在两类中重复计数，应减去。故答案是：16-3=133.2 容斥原理第二张，PPT共一百五十页，创作于2022年6月 容斥原理研究有限集合的交或并的计数。DeMorgan定理 论域U，补集,有3.2 容斥原理(a)(b)第三张，PPT共一百五十页，创作于2022年6月证：(a)的证明。设 ,则 相当于 和同时成立，亦即 (1)3.2 容斥原理第四张，PPT共一百五十页，创作于2022年6月反之，若故(2)由（1）和

2、（2）得(b)的证明和（a)类似，从略.3.2 容斥原理第五张，PPT共一百五十页，创作于2022年6月DeMogan定理的推广：设 证明：只证(a). N=2时定理已证。设定理对n是正确的，即假定：3.2 容斥原理第六张，PPT共一百五十页，创作于2022年6月正确即定理对n+1也是正确的。3.2 容斥原理第七张，PPT共一百五十页，创作于2022年6月2 容斥原理 最简单的计数问题是求有限集合A和B的并的元素数目。显然有即具有性质A或B的元素的个数等于具(1)定理：3.2 容斥原理第八张，PPT共一百五十页，创作于2022年6月有性质A和B的元素个数。UBA3.2 容斥原理第九张，PPT共

3、一百五十页，创作于2022年6月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 )第十张，PPT共一百五十页，创作于2022年6月3.2 容斥原理( 3 ) ( 1 ) ( 2 ) 得| AB | A | B | AB| + |AB | + | BA| ( | AB | + | AB | ) ( | B

4、A | + | BA | ) | AB | | AB | A | + | B | AB |第十一张，PPT共一百五十页，创作于2022年6月定理：(2)3.2 容斥原理第十二张，PPT共一百五十页，创作于2022年6月3.2 容斥原理第十三张，PPT共一百五十页，创作于2022年6月ABC3.2 容斥原理第十四张，PPT共一百五十页，创作于2022年6月 例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？3.2 容斥原理第十

5、五张，PPT共一百五十页，创作于2022年6月令：M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合；3.2 容斥原理第十六张，PPT共一百五十页，创作于2022年6月即学校学生数为336人。3.2 容斥原理第十七张，PPT共一百五十页，创作于2022年6月同理可推出：利用数学归纳法可得一般的定理：3.2 容斥原理第十八张，PPT共一百五十页，创作于2022年6月 定理设(n,k)是1,n的所有k-子集的集合, 则 |Ai | = (1)k-1 | Ai |证对n用归纳法。n=2时，等式成立。 假设对n - 1，等式成立。对于n有 3.2 容斥原理ni=1k=1n I(n

6、,k)iI第十九张，PPT共一百五十页，创作于2022年6月3.2 容斥原理 I(n-1,k) I(n-1,k)iI第二十张，PPT共一百五十页，创作于2022年6月3.2 容斥原理 I(n,k) I(n-1,k-1) I(n-1,k)此定理也可表示为：第二十一张，PPT共一百五十页，创作于2022年6月定理：设是有限集合，则(4)3.2 容斥原理第二十二张，PPT共一百五十页，创作于2022年6月 证：用数学归纳法证明。已知 n=2时有设 n-1时成立，即有：3.2 容斥原理3.2 容斥原理第二十三张，PPT共一百五十页，创作于2022年6月3.2 容斥原理第二十四张，PPT共一百五十页，创

7、作于2022年6月3.2 容斥原理第二十五张，PPT共一百五十页，创作于2022年6月3.2 容斥原理第二十六张，PPT共一百五十页，创作于2022年6月3.2 容斥原理第二十七张，PPT共一百五十页，创作于2022年6月3.2 容斥原理第二十八张，PPT共一百五十页，创作于2022年6月3.2 容斥原理第二十九张，PPT共一百五十页，创作于2022年6月其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。一般有：3.2 容斥原理第三十张，PPT共一百五十页，创作于2022年6月(5)容斥原理指的就是（4）和（5）式。3.2 容斥原理第三十一张，PPT共一百五十

8、页，创作于2022年6月3 例 例1 求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。 解：设A为ace作为一个元素出现的排列集，B为 df作为一个元素出现的排列集， 为同时出现ace、df的排列数。3.3 例第三十二张，PPT共一百五十页，创作于2022年6月根据容斥原理，不出现ace和df的排列数为：=6!- (5!+4!)+3!=582 3.3 例第三十三张，PPT共一百五十页，创作于2022年6月 例2 求从1到500的整数中能被3或5除尽的数的个数。 解： 令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合3.3 例第三十四张，PPT共

9、一百五十页，创作于2022年6月被3或5除尽的数的个数为 例3 求由a,b,c,d四个字母构成的位符号串中，a,b,c,d至少出现一次的符号串数目。3.3 例第三十五张，PPT共一百五十页，创作于2022年6月 解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。 由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是3.3 例第三十六张，PPT共一百五十页，创作于2022年6月 a，b，c至少出现一次的n位符号串集合即为3.3 例第三十七张，PPT共一百五十页，创作于2022年6月 例4。求不超过120的素数个数。 因 ，故不超过120的合

10、数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。 设 为不超过120的数 的倍数集， =2，3，5，7。3.3 例第三十八张，PPT共一百五十页，创作于2022年6月3.3 例第三十九张，PPT共一百五十页，创作于2022年6月3.3 例第四十张，PPT共一百五十页，创作于2022年6月3.3 例第四十一张，PPT共一百五十页，创作于2022年6月3.3 例第四十二张，PPT共一百五十页，创作于2022年6月 注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7着四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求的不超过120的素数个数

11、为： 27+4-1=303.3 例第四十三张，PPT共一百五十页，创作于2022年6月 例5。用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。 解：所有排列中，令：3.3 例第四十四张，PPT共一百五十页，创作于2022年6月3.3 例第四十五张，PPT共一百五十页，创作于2022年6月 出现dog字样的排列，相当于把dog作为一个单元参加排列，故类似有： 由于god,dog不可能在一个排列中同 时出现，故： 类似：3.3 例第四十六张，PPT共一百五十页，创作于2022年6月 由于gum,dog可以在dogum字

12、样中同时出现，故有： 类似有god和depth可以在godepth字样中同时出现，故 god和thing可以在thingod字样中同时出现，从而 3.3 例第四十七张，PPT共一百五十页，创作于2022年6月3.3 例第四十八张，PPT共一百五十页，创作于2022年6月 由于god、depth、thing不可以同时出现，故有： 其余多于3个集合的交集都为空集。3.3 例第四十九张，PPT共一百五十页，创作于2022年6月 故满足要求的排列数为： 3.3 例第五十张，PPT共一百五十页，创作于2022年6月 例6。求完全由n个布尔变量确定的布而函数的个数。 解：设 布尔函数类为： 由于n个布尔变

13、量 的不同的真值表数目与 位2进制数数目相同，故为 个。根据容斥原理，满足条件的函数数目为：3.3 例第五十一张，PPT共一百五十页，创作于2022年6月3.3 例第五十二张，PPT共一百五十页，创作于2022年6月3.3 例这10个布尔函数为：x1x2，x1x2，x1x2， x1x2，x1x2，x1x2，x1x2， x1x2，(x1x2)(x1x2)， (x1x2)(x1x2)第五十三张，PPT共一百五十页，创作于2022年6月 例7。欧拉函数(n)是求小于n且与n互素的数的个数。 解：若n分解为素数的乘积 设1到n的n个数中为 倍数的集合为则有3.3 例第五十四张，PPT共一百五十页，创作

14、于2022年6月3.3 例第五十五张，PPT共一百五十页，创作于2022年6月3.3 例第五十六张，PPT共一百五十页，创作于2022年6月即比60小且与60无公因子的数有16个：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一个1。3.3 例第五十七张，PPT共一百五十页，创作于2022年6月 4 错排问题 n个元素依次给以标号1，2，n。N个元素的全排列中，求每个元素都不在自己原来位置上的排列数。 设 为数 在第 位上的全体排列， =1，2，n。因数字 不能动，因而有：3.3 例第五十八张，PPT共一百五十页，创作于2022年6月3.4 错

15、排问题第五十九张，PPT共一百五十页，创作于2022年6月每个元素都不在原来位置的排列数为3.4 错排问题第六十张，PPT共一百五十页，创作于2022年6月 例1。数1，2，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。 解：实际上是1，3，5，7，9五个数的错排问题，总数为：3.4 错排问题第六十一张，PPT共一百五十页，创作于2022年6月 例2. 在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。 8个字母的全排列中，令分别表A,C,E,G在原来位置上的排列，则错排数为：3.4 错排问题第六十二张，PPT共一百五十页，创

16、作于2022年6月3.4 错排问题第六十三张，PPT共一百五十页，创作于2022年6月 例3。求8个字母A,B,C,D,E,F,G,H的全排列中只有4个不在原来位置的排列数。 解：8个字母中只有4个不在原来位置上，其余4个字母保持不动，相当于4个元素的错排，其数目为3.4 错排问题第六十四张，PPT共一百五十页，创作于2022年6月 故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)9=6303.4 错排问题第六十五张，PPT共一百五十页，创作于2022年6月5 棋盘多项式和有限制排列1. 有限制排列3.5 棋盘多项式和有限制排列 例4个x ，3个y，2个z的全排列中，求不出现

17、xxxx，yyy，zz图象的排列。 解设出现xxxx的排列的集合记为A1， |A1|= =60; 设出现yyy的排列的集合记为A2， | A2|= =105；6!1!3!2! 4!2! 7!第六十六张，PPT共一百五十页，创作于2022年6月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!

18、4!9!2!3!4!第六十七张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列2棋子多项式 n个不同元素的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子xxxxx 如图所示的布局对应于排列41352。第六十八张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列 可以把棋盘的形状推广到任意形状： 布子规定称为无对攻规则，棋子相当于 象棋中的车。 令r k（C）表示k个棋子布到棋盘C上的方案数。如：第六十九张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列r1( )=1，r1( )

19、=2，r1( )=2，r2( )=0，r2( )=1。为了形象化起见，（ ）中的图象便是棋盘的形状。第七十张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列定义设C为一棋盘，称R(C)= rk(C) xk为C的棋盘多项式。规定 r0(C)=1，包括C=时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有rk(C)=rk1(Ci)rk(Ce)，k=0第七十一张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列即对任一指定的格子，要么布子，所得的方案数为 rk1(Ci)；要么不布子，方案数为

20、rk(Ce)。设C有n个格子，则 r1(C)nr1(C)r0(Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故规定 r0(C)1是合理的第七十二张，PPT共一百五十页，创作于2022年6月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第七十三张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列例如：R(

21、 )=1+ x；R( )= xR( )+ R( )= x+ (1+ x)=1+2x；R( )= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x2第七十四张，PPT共一百五十页，创作于2022年6月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

22、)第七十五张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列利用（）和（），可以把一个比较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。例R ( ) = xR( )+R( ) = x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3*R( ) = xR( ) + R( ) = 1+6x +10 x2 +4x3第七十六张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列有禁区的排列例设对于排列P=P1 P2 P3 P4，规定P1，P、， P2、， P42。 1 2 3 4P1P2P3P412 4 314 3223431

23、 214这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。第七十七张，PPT共一百五十页，创作于2022年6月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。第七十八张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列则所有棋子都不布入禁区的方案数为A1A2Ann！ (1)kAiI(n ,

24、k)niIk=0而 Ai正是k个棋子布入禁区，其他n - k个棋子任意布的方案数。由假设可知等于rk(nk)！(注意：布入禁区的棋子也要遵守无对攻规则）.所以A1A2An=n!+ (1)k rk ( nk)!I(n , k)iIk=0 n第七十九张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列上例方案数为 4!6(41)!11(42)!7(43)! 1(4)!4例，四位工人，A，B，C，D四项任务。条件如下：不干B；不干B、C；不干C、D；不干D。问有多少种可行方案？第八十张，PPT共一百五十页，创作于2022年6月3.5 棋盘多项式和有限制排列解由题意，可得如下棋盘

25、： 其中有影线的格子表示禁区。A B C D1 2 3 4 R( )=1+6x+10 x2+4x3 方案数=4!6(41)!+10(42)!4(43)! +0(44)!=4第八十一张，PPT共一百五十页，创作于2022年6月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第八十二张，PPT共一百五十页，

26、创作于2022年6月3.6一般公式 3.6一般公式若将.2中的例子改为“单修一门数学的学生有多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”则相应的答案表示如下：MPC；MPC+MPC+MPCMPC+MPC+MPC第八十三张，PPT共一百五十页，创作于2022年6月3.6一般公式设有与性质, 2 , , n相关的元素N个，Ai为有第 i 种性质的元素的集合.i=1,2,nPk为至少有k种性质的元素的元次；qk为恰有k种性质的元素的个数。P0 = N，P1 = | A1 | + | A2 | + + | An |，P2 = | A1A2 |+ | A1A3 |+ + | An -

27、1An |Pk = | Aij |qk =| ( Ai) ( Aj)| I(n ,k)i I I(n ,k)i Ij I第八十四张，PPT共一百五十页，创作于2022年6月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第八十五张，PPT共一百五十页，创作于2022年6月3.6一般公式而 (1)i ( )

28、 ( ) = (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第八十六张，PPT共一百五十页，创作于2022年6月3.6一般公式前例中只修一门课的学生为： | MPC | + | MPC | + | MPC |= q1= (1)j - 1 ( ) Pj= P1 2P2 + 3P3j1j =1 3 在一般公式中，若令

29、P0 = N， q0 = | A1A2An |，就得到原来的容斥原理。第八十七张，PPT共一百五十页，创作于2022年6月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第八十八张，PPT共一百五十页，创作于2022年6月3.6一般公式qk = (1)j ( )

30、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 第八十九张，PPT共一百五十页，创作于2022年6月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(

31、 )，qkjm1 k =m0 km第九十张，PPT共一百五十页，创作于2022年6月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第九十一张，PPT共一百五十页，创作于2022年6月3.6一般公式例某校有个教师，已知教数学的有位，教物理的有位，教化学的位；数、理位，数、化位，理、化位；数理化位。问教其他课的有几位？只教一门的有几位？只

32、好教两门的有几位？解令教数学的教师属于A1，教物理的属于A2，教化学的属于A3。则P0，P1| A1 |+| A2|+| A3 |8+6+5;P2| A1A2|+ | A1A3|+| A2A3|12；P3| A1A2A3|3； 第九十二张，PPT共一百五十页，创作于2022年6月3.6一般公式故教其他课的老师数为：q0P0 P1 +P2P3恰好一门的教师数：q1P12P2 + 3P34恰好教两门的老师数为：q2P23P33第九十三张，PPT共一百五十页，创作于2022年6月3.6一般公式例n 对夫妻围坐问题设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？解不妨

33、设 n 个女人先围成一圈，方案数为( n1 )! 。对任一这样的给定方案，顺时针给每个女人以编号1 , 2 , , n。设第i号与第 i + 1号女人之间的位置为第 i 号位置，1 i n1。第 n 号女人与第1 号之第九十四张，PPT共一百五十页，创作于2022年6月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第九十五张，PP

34、T共一百五十页，创作于2022年6月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第九十六张，PPT共一百五十页，创作于2022年6月3.6一般公式也就是从( 1 , 2 ) ( 2 , 3 ) ( n, n ) ( n , 1)这n对数的k 对中各取一数，且互不相同的取法的计数。这相当于从1 , 2 , 2 ,

35、 3 ,3 ,4, ,n1, n1, n , n , 1中取 k 个互不相邻数的组合的计数，但首尾的不能同时取。回想无重复不相邻组合的计数： C( n , r ) = C ( nr + 1 , r ) ,这里所求的是( )( )= ( ) 2nk+1 k2n4( k2)+1 k22nk k 2n2nk第九十七张，PPT共一百五十页，创作于2022年6月3.6一般公式 Un =(1)k ( )(nk)! = Ai 2n2nk2nk ki 1 , n 第九十八张，PPT共一百五十页，创作于2022年6月.11反演基本想法：an 易算，bn难算，an可用bn表示，利用反演，将bn用an表示二项式反演

36、引理第九十九张，PPT共一百五十页，创作于2022年6月.11反演证第一百张，PPT共一百五十页，创作于2022年6月.11反演定理证第一百零一张，PPT共一百五十页，创作于2022年6月.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!第一百零二张，PPT共一百五十页，创作于2022年6月.11反演Mbus反演定义设 n Z+ 1，若 n = 1;( n ) = 0，若n

37、= p11 p22 pkk 存在i1 (1)k ，若n = p1p2pk 如 ( 30) = ( 235 ) = (1)3 ( 12) = 0；第一百零三张，PPT共一百五十页，创作于2022年6月.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第一百零四张，P

38、PT共一百五十页，创作于2022年6月.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第一百零五张，PPT共一百五十页，创作于2022年6月.11反演定理( Mbus反演定理 )设 f ( n )和g ( n )是定义在正整数集合上的两个函数 f ( n ) = g (d ) = g ( ) (M1 ) g( n ) = (d) f ( ) = ( )f (d) (M2) ndndd | nd | nd |

39、nd | n则( M1 ) ( M2 ) nd第一百零六张，PPT共一百五十页，创作于2022年6月.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第一百零七张，PPT共一百五十页，创作于2022年6月.11反演“”：设（M2）成立。 g (d )

40、 = 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 第一百一十八张，PPT共一百五十页，创作于2022年6月.8鸽巢原理之二鸽巢原理二m1 , m2 , , mn都

41、是正整数，并有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则第一百一十九张，PPT共一百五十页，创作于2022年6月.8鸽巢原理之二鸽子总数 m1 + m2 + +mnn ，与假设相矛盾推论m只鸽子进n个巢，至少有一个巢里有 |只鸽子nm推论n(m1) + 1只鸽子进n个巢，至少有一个巢内至少有m只鸽子推论若m1

42、 , m2 , , mn是正整数，且 r1,则 m1, , mn至少有一个不小于rm1 + +mn n第一百二十张，PPT共一百五十页，创作于2022年6月.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第一百二十一张，PPT共一百五十页，创作于2022年6月.8鸽

43、巢原理之二证在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位对应相等第一百二十二张，PPT共一百五十页，创作于2022年6月.8鸽巢原理之二定理若序列S = a1 , a2 , , amn+1中的各数是不等的m , n 是正整数，则 S有一长度为m+1的严格增子序列或长度为n+1的减子序列，而且 S有一长度为m+1的减子序列或长度为

44、n+1的增子序列证由S中的每个 ai 向后选取最长增子序列，设其长度为li ，从而得序列L = l1 , l2 , , lmn+1 若存在 lkm+1则结论成立第一百二十三张，PPT共一百五十页，创作于2022年6月.8鸽巢原理之二否则所有的 li 1 , m，其中必有 | = n+1个相等设li1 = li2 = = lin= lin+1 不妨设 i1i2 ai2 ain+1 ，即有一长度为n+1的减子列否则不妨设ai1 li2 ，矛盾mn+1 m第一百二十四张，PPT共一百五十页，创作于2022年6月.8鸽巢原理之二证从ai 向后取最长增子列及减子列，设其长度分别为 li ，li .若任意

45、 i ，都有li 1，m, li，n,不超过mn种对则存在 j k，( lj , lj ) = ( lk , lk )若aj lk，若aj ak，则 lj lk ，矛盾第一百二十五张，PPT共一百五十页，创作于2022年6月.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，1

46、7。65 4第一百二十六张，PPT共一百五十页，创作于2022年6月.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第一百二十七张，PPT共一百五十页，创作于2022年6月.8鸽巢原理之二令di1= CiC1，I = 2 , 3设D d1 , d2 , D 1 , 65。由

47、反证法假设 D( P1P2P3 )=，因而 D P4。由反证法假设 d2d1 P1P2P3 且d2d1 P4 ，故 d2d1 1 , 65 ，但显然 d2d1 1 , 65 ，矛盾。第一百二十八张，PPT共一百五十页，创作于2022年6月.9Ramsey 问题Ramsey问题 Ramsey问题可以看成是鸽巢原理的推广下面举例说明Ramsey问题例6 个人中至少存在人相互认识或者相互不认识证这个问题与K6的边着色存在同色三角形等价假定用红蓝着色第一百二十九张，PPT共一百五十页，创作于2022年6月.9Ramsey 问题设K6的顶点集为v1 , v2 , , v6 ，dr(v)表示与顶点 v 关

48、联的红色边的条数，db(v)表示与 v 关联的蓝色边的条数在K6 中，有dr(v) db(v)，由鸽巢原理可知，至少有条边同色现将证明过程用判断树表示如下：第一百三十张，PPT共一百五十页，创作于2022年6月.9Ramsey 问题dr(v1)3?db(v1)3设(v1v2) (v1v3) (v1v4)为红边设(v1v2) (v1v3) (v1v4)为蓝边v2v3v4是红 ?v2v3v4是蓝 ?设( v2v3 )是蓝边设( v2v3 )是红边v1v2v3是蓝v1v2v3是红YNNNYY第一百三十一张，PPT共一百五十页，创作于2022年6月.9Ramsey 问题若干推论( a )K6的边用红蓝

49、任意着色，则至少有两个同色的三角形证由前定理知，有同色三角形，不妨设v1v2v3是红色三角形可由如下判断树证明第一百三十二张，PPT共一百五十页，创作于2022年6月.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是蓝?设 (

50、v5v6)为红边yyyyyynnnnn第一百三十三张，PPT共一百五十页，创作于2022年6月.9Ramsey 问题( b )K9 的边红蓝两色任意着色，则必有红K4或蓝色三角形(蓝K4或红色三角形)证设个顶点为 v1 , v2 , , v9对个顶点的完全图的边的红、蓝着色图中，必然存在 vi ，使得 dr(vi)3 否则，红边数 dr(vi) ，这是不可能的不妨设 dr(v1)3，可得如下判断树证明结论1227 2第一百三十四张，PPT共一百五十页，创作于2022年6月.9Ramsey 问题dr(v1)4?db(v1)6设(v1v2) (v1v3) (v1v4)(v1v5)是4红边设(v1v

51、2) (v1v7)是6条蓝边K4(v2v3v4v5)是蓝K4 ?K6(v2v7)中有红 ?设(v2v3)是红边v1v2v3是红设v2v3v4是红K4(v2v3v4v5)是蓝K4YYYNNN第一百三十五张，PPT共一百五十页，创作于2022年6月.9Ramsey 问题K9的边红、蓝着色，必有红色三角形或蓝色K4同理可证 K9的红、蓝着色，必有蓝色三角形或红色K4 (红 蓝K4) (蓝 红K4)存在同色K4或红及蓝 同色K4 (红 蓝 )第一百三十六张，PPT共一百五十页，创作于2022年6月.9Ramsey 问题( c )K18的边红，蓝着色，存在红K4或蓝K4 证设18个顶点为v1 , v2

52、, , v18 从v1引出的17条边至少有条是同色的，不妨先假定为红色从而可得下面的判断树证明命题第一百三十七张，PPT共一百五十页，创作于2022年6月.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第一百三十八张，PPT共一百五十页，创作于2022年6月.10Ramsey数将上一节的问题一般化：给定一对正整数a、b，存在一个最小的正整数 r ,对 r 个顶点的完全图的边任意红、蓝着色，存在 a 个顶点的红边完全图或 b 个顶点的蓝边完全图。记为 r ( a , b )。比如：r ( 3 , 3 )6，r ( 3 , 4