哈工大-组合数学讲义优秀PPT.ppt

《哈工大-组合数学讲义优秀PPT.ppt》由会员分享，可在线阅读，更多相关《哈工大-组合数学讲义优秀PPT.ppt（444页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、高级软件工程高级软件工程组合数学组合数学(Combinatorics)哈尔滨工业高校哈尔滨工业高校(威海威海)计算机科学与技术学院计算机科学与技术学院孟凡超孟凡超 Email:mfchitwh.edu 2组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)参考书目参考书目n组合数学组合数学(第四版第四版)/(美美)布鲁斯布鲁斯(Brualdi,R.A)著；北京机械工业出版社著；北京机械工业出版社,2005.2n卢开澄卢开澄,组合数学组合数学,清华高校出版社清华高校出版社.3组合数学组合数学组合数学组合数学(Combinatorics)(Combinato

2、rics)主要内容主要内容n概述概述n鸽巢原理鸽巢原理 n排列与组合排列与组合n生成排列和组合生成排列和组合 n二项式系数二项式系数 n容斥原理及应用容斥原理及应用 n递推关系和生成函数递推关系和生成函数n特殊计数序列特殊计数序列n二分图中的匹配二分图中的匹配 nPolya计数法计数法 4组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述n数学探讨问题数学探讨问题n探讨连续对象探讨连续对象(微积分微积分)n探讨离散对象探讨离散对象(组合数学组合数学)n组合数学探讨的问题组合数学探讨的问题n将一个集合的物体排列成满足一些指定规将一个集合的物体排列

3、成满足一些指定规则的格式，如下两类问题反复出现：则的格式，如下两类问题反复出现：n排列存在性：假如想要排列一个集合的成员使排列存在性：假如想要排列一个集合的成员使得某些条件得以满足，并且这种排列不总是可得某些条件得以满足，并且这种排列不总是可能的，那么这种排列在什么样的条件下满足。能的，那么这种排列在什么样的条件下满足。n排列的计数和分类：假如一个指定的排列是可排列的计数和分类：假如一个指定的排列是可能的，那么会有多少种方法去实现它。此时，能的，那么会有多少种方法去实现它。此时，人们就可以计数并将它们分类。人们就可以计数并将它们分类。5组合数学组合数学组合数学组合数学(Combinatoric

4、s)(Combinatorics)概述概述棋盘的完备覆盖：考虑一张棋盘的完备覆盖：考虑一张88(8行行8列列)的的64个正方形的国个正方形的国际象棋棋盘，设有形态一样的多米诺牌，每张牌恰好覆盖棋盘际象棋棋盘，设有形态一样的多米诺牌，每张牌恰好覆盖棋盘上相邻的两个方格，那么，是否能够把上相邻的两个方格，那么，是否能够把32张多米诺牌摆放到棋张多米诺牌摆放到棋盘上，使得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两盘上，使得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且棋盘上的全部方格都被覆盖住？我们把这样一种个方格，并且棋盘上的全部方格都被覆盖住？我们把这样一种排列称为棋盘的多米诺牌的完

5、备覆盖。排列称为棋盘的多米诺牌的完备覆盖。8 8棋盘棋盘完备覆盖完备覆盖1完备覆盖完备覆盖2完备覆盖数：完备覆盖数：12988816=24(901)2)6组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述与上述问题同时出现的另外两种组合数学问题：与上述问题同时出现的另外两种组合数学问题：探讨一个已知的排列：当人们建立起满足某些指定条探讨一个已知的排列：当人们建立起满足某些指定条件的一个排列以后，可能要考察这个排列的性质和件的一个排列以后，可能要考察这个排列的性质和结构，这样的结构可能会涉及到分类问题。结构，这样的结构可能会涉及到分类问题。构造一

6、个最优的排列：假如可能存在多于一个的排列，构造一个最优的排列：假如可能存在多于一个的排列，人们或许想要确定满足某些优化准则的一个排列，人们或许想要确定满足某些优化准则的一个排列，即找出某种规定意义下的即找出某种规定意义下的“最好的最好的”或或“最优的最优的”排列。排列。7组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述例，设例，设S=1,2,3,4为一个集合为一个集合 1)从从S中取两个不相同的元素进行排列，这样的排列有多少种中取两个不相同的元素进行排列，这样的排列有多少种2)列出全部可能的排列。列出全部可能的排列。3)求出两个元素之和最大的

7、排列。求出两个元素之和最大的排列。组合数学是探讨离散结构的存在、计数、组合数学是探讨离散结构的存在、计数、分析和优化等问题的一门科学。分析和优化等问题的一门科学。8组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述问题问题1.假如将棋盘变为假如将棋盘变为 mn(m行行n列列)，则完备覆盖是否，则完备覆盖是否存在？存在？问题问题2.对于什么样的对于什么样的m和和n存在完备覆盖？存在完备覆盖？当且仅当当且仅当m和和n中至少有一个是偶数时，中至少有一个是偶数时，mn 棋盘存在棋盘存在完备覆盖。完备覆盖。不确定存在，例如，不确定存在，例如，3行行3列的

8、棋盘就不存在完备覆盖。列的棋盘就不存在完备覆盖。9组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述问题问题3.88的棋盘用一把剪刀剪掉棋盘一副对角上的两的棋盘用一把剪刀剪掉棋盘一副对角上的两个方格，总共剩下个方格，总共剩下62个方格，那么是否能够排列个方格，那么是否能够排列31张多张多米诺牌来得出对这幅被剪过棋盘的完备覆盖？米诺牌来得出对这幅被剪过棋盘的完备覆盖？不存在完备覆盖。不存在完备覆盖。在一副在一副88棋盘上交替地将方格涂成黑色和白色，则其棋盘上交替地将方格涂成黑色和白色，则其中的中的32个方格是黑色，个方格是黑色，32个方格是白色。

9、个方格是白色。假如我们剪掉棋盘一副对角线上的两个方格，那么我们假如我们剪掉棋盘一副对角线上的两个方格，那么我们就剪掉同样种颜色的两个方格，比如两个白色方格。这就剪掉同样种颜色的两个方格，比如两个白色方格。这就变成了就变成了32个黑方格和个黑方格和30个白方格。个白方格。但是，每张多米诺牌须要一个白方格和一个黑方格，于但是，每张多米诺牌须要一个白方格和一个黑方格，于是，是，31张不重叠的多米诺牌则覆盖住张不重叠的多米诺牌则覆盖住31个黑方格和个黑方格和31个个白方格。因此，这幅被剪过的棋盘不存在完备覆盖。白方格。因此，这幅被剪过的棋盘不存在完备覆盖。10组合数学组合数学组合数学组合数学(Comb

10、inatorics)(Combinatorics)概述概述问题问题4.将将mn的棋盘上的方格交替涂成黑色和白色，切的棋盘上的方格交替涂成黑色和白色，切除一些方格，得到一块被剪过的棋盘，这块棋盘什么时除一些方格，得到一块被剪过的棋盘，这块棋盘什么时候有一个完备覆盖？候有一个完备覆盖？必要条件。这块被剪过的棋盘必需具有相等的黑方格数必要条件。这块被剪过的棋盘必需具有相等的黑方格数和白方格数。和白方格数。该条件不是充分条件。该条件不是充分条件。4 5棋盘棋盘 11组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述nB-牌：牌：设设b是一个正整数，我们

11、用是一个正整数，我们用b个个1 1的方格并排的方格并排连接成的连接成的1 b的方格条来代替多米诺牌，这些方方格条的方格条来代替多米诺牌，这些方方格条称为称为b-牌。牌。一一张张5-牌牌一一张张2-牌牌（多米（多米诺诺牌）牌）nmn棋盘被棋盘被B-牌的完备覆盖：牌的完备覆盖：b-牌在牌在mn棋盘上没有棋盘上没有两张重叠，每一条两张重叠，每一条b-牌盖住棋盘上的牌盖住棋盘上的b个方格，并且盘上个方格，并且盘上的全部方格都被覆盖住。的全部方格都被覆盖住。12组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述问题问题5.mn棋盘何时具有棋盘何时具有b-

12、牌的完备覆盖？牌的完备覆盖？当且仅当当且仅当b是是m的一个因子或者的一个因子或者b是是n的一个因子的一个因子充分性。假如充分性。假如b是是m的一个因子或者的一个因子或者b是是n的一个因子，的一个因子，则则mn棋盘存在棋盘存在b-牌完备覆盖。牌完备覆盖。假如b是m的一个因子，我们就可以对n列的每一列用m/b个b-牌覆盖并进而完成对mn棋盘的完备覆盖。假如b是n的一个引子，我们就可以对m行的每一行用n/b个b-牌覆盖并进而完成对mn棋盘的完备覆盖。13组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述必要性。假如必要性。假如mn棋盘存在棋盘存在b-

13、牌完备覆盖，则牌完备覆盖，则b或者是或者是m一个因子或者是一个因子或者是n的一个因子。的一个因子。我们须要证明m和n除以b的余数至少有一个是零。设b除以m和n得到商p和q以及余数r和s,m=pb+r (0rb-1)n=qb+s (0sb-1)我们不妨设rs，因此，我们须要证明r=0。接受反证法，设r0。14组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)主要内容主要内容n概述概述n鸽巢原理鸽巢原理 n排列与组合排列与组合 n生成排列和组合生成排列和组合n二项式系数二项式系数 n容斥原理及应用容斥原理及应用 n递推关系和生成函数递推关系和生成函数n特殊

14、计数序列特殊计数序列 n二分图匹配二分图匹配nPolya计数法计数法 15组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理n鸽巢原理：简洁形式鸽巢原理：简洁形式n定理定理1.假如假如n+1个物体被放进个物体被放进n个盒子中，那么至少个盒子中，那么至少有一个盒子包含两只或更多的物体。有一个盒子包含两只或更多的物体。n其它表述形式：其它表述形式：n假如假如n+1只鸽子被放进只鸽子被放进n个鸽巢中，那么至少有一个个鸽巢中，那么至少有一个鸽巢包含两只或更多的鸽子。鸽巢包含两只或更多的鸽子。n假如假如n+1个物体用种颜色涂色，那么必定有两个物体

15、个物体用种颜色涂色，那么必定有两个物体被涂成相同的颜色。被涂成相同的颜色。16组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理4个物体个物体3个盒子个盒子存放存放1234517组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p例题：例题：p例例1：在：在13个人中存在两个人，他们的生日在同一个月份里。个人中存在两个人，他们的生日在同一个月份里。p考虑考虑12个盒子，每个盒子对应一个月份，将个盒子，每个盒子对应一个月份，将13个人放到个人放到12个个盒子中，则至少有一个盒子包含

16、两个或两个以上的人，即，这盒子中，则至少有一个盒子包含两个或两个以上的人，即，这在在13个人中存在两个人，他们的生日在同一个月份里。个人中存在两个人，他们的生日在同一个月份里。p例例2：设有：设有n对已婚夫妇。为保证能够有一对夫妇被选出，至对已婚夫妇。为保证能够有一对夫妇被选出，至少要从这少要从这2n个人中选出多少人。个人中选出多少人。p应至少选择应至少选择n+1个人。考虑个人。考虑n个盒子，每个盒子对应一对夫妇。个盒子，每个盒子对应一对夫妇。假如我们选择假如我们选择n+1个人并把他们中的每一个人放到他们对偶所在个人并把他们中的每一个人放到他们对偶所在的那个盒子中去，那么就有同一个盒子含有两个

17、人，也就是说，的那个盒子中去，那么就有同一个盒子含有两个人，也就是说，我们选择了一对已婚夫妇。我们选择了一对已婚夫妇。p假如选择假如选择n个人，可以只选择全部丈夫或只选择全部的妻子。个人，可以只选择全部丈夫或只选择全部的妻子。18组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p与鸽巢原理相关的原理与鸽巢原理相关的原理p定理定理2：假如将：假如将n个物体放入个物体放入n个盒子并且没有一个盒子是空的，个盒子并且没有一个盒子是空的，那么每个盒子恰好包含一个物体。那么每个盒子恰好包含一个物体。p定理定理3：假如将：假如将n个物体放入个物体放

18、入n个盒子且没有一个盒子被放入多个盒子且没有一个盒子被放入多于一个物体，那么每个盒子里有一个物体。于一个物体，那么每个盒子里有一个物体。19组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p函数基本学问函数基本学问p函数：集合之间的函数函数：集合之间的函数(function，或说映射，或说映射mapping)：设：设X和和Y是随意两个集合，而是随意两个集合，而f 是是X到到Y的一个关系，假如对于每一个的一个关系，假如对于每一个xX,有唯一的有唯一的yY，使得，使得f，称关系，称关系f 为函数，记作为函数，记作f:XY或或 X Y。p原

19、象和象：假如原象和象：假如f，则，则x称为自变元（原象），称为自变元（原象），y称为称为在在f 作用下作用下x的象的象(image)，f 亦可记作亦可记作y=f(x)，且记，且记f(X)=f(x)|xX。20组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p函数基本学问函数基本学问p定义域：函数定义域：函数f:XY的定义域的定义域(domain)dom f 定义为：定义为：p dom f =x|存在某个存在某个yY使得使得f =X。p值域：函数值域：函数f:XY的值域的值域(range)ran f 定义为：定义为：p ran f=y|

20、(x)(xX)f Y。p全函数：全函数：f 是全函数是全函数(total function)p若若dom f=X，f 是全函数是全函数,否则称否则称f是偏函数是偏函数(partial function)。21组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p函数基本学问函数基本学问p满射：满射：f 是满射是满射(surjection,或说或说f maps X onto Y)p假如假如ran f =Y，即对随意的，即对随意的yY都有原像。都有原像。p设设f:XY是满射，即对随意的是满射，即对随意的yY，必存在，必存在xX，使得，使得f(

21、x)=y成立。成立。p入射：入射：f 是入射是入射(injection，或说，或说f is one to one 是一对一是一对一)p设设f:XY是入射，即对随意的是入射，即对随意的x1,x2X，假如，假如f(x1)=f(x2),则则x1=x2，或者，或者 假如假如x1x2，则得，则得f(x1)f(x2)。22组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p从函数角度来分析鸽巢原理的含义从函数角度来分析鸽巢原理的含义p设设X和和Y是两个有限集，并令是两个有限集，并令f:XY是一个从是一个从X到到Y的函数。的函数。p假如假如X的元素多

22、于的元素多于Y的元素，那么的元素，那么f 就不是一对一的。就不是一对一的。p假如假如X和和Y含有相同个数的元素，并且含有相同个数的元素，并且f 是映上是映上(onto)的，那么的，那么f 就是一对一的。就是一对一的。p假如假如X和和Y含有相同个数的元素，并且含有相同个数的元素，并且f是一对一的，那么是一对一的，那么f 就就是映上的。是映上的。23组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理例例3：给定给定m个整数个整数a1,a2,am,存在整数存在整数k和和l，0klm，使得使得ak+1,ak+2,al能够被能够被m整除。也就是说

23、，在序列整除。也就是说，在序列a1,a2,am中存在连续个元素，它们的和能被中存在连续个元素，它们的和能被m整除。整除。考虑m个和：a1,a1+a2,a1+a2+a3,a1+a2+a3+.+am假如这些和中存在一个可以被m整除，那么结论就成立。否则，这些和中的随意一个都不能被m整除，即，这些和中的每一个除以m都有一个非零余数，余数等于1,2,m-1。由于m个和而只有m-1个余数，假如我们将和看成是物体，余数看成是盒子，依据鸽巢原理，那么必有两个和除以m有相同的余数。因此，存在整数k和l，kl，使得a1+a2+.+ak和a1+a2+.+al除以m有相同的余数r，a1+a2+.+ak=bm+r，a

24、1+a2+.+al=cm+r两式相减，有ak+1+ak+2+.+al=(c-b)m，从而ak+1+ak+2+.+al能够被m整除。24组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理例例4：一位国际象棋大师有：一位国际象棋大师有11周的时间备战一场锦标赛，他确周的时间备战一场锦标赛，他确定每天至少下一盘棋，但是为了使自己不过分疲惫他还确定在定每天至少下一盘棋，但是为了使自己不过分疲惫他还确定在每周不能下棋超过每周不能下棋超过12盘。证明存在连续若干天，期间这位大师盘。证明存在连续若干天，期间这位大师恰好下了恰好下了21盘棋。盘棋。一共

25、备战一共备战117=77天。令天。令x1,x2,x77分别为第分别为第1,2,77天下天下的棋数，则的棋数，则xi1(i=1,2,77)。我们构造如下严格递增序列：。我们构造如下严格递增序列：a1=x1,a2=x1+x2,a3=x1+x2+x3,a77=x1+x2+x3+x77，其中，其中，ai表示前表示前i(i=1,2,77)天下棋的总数，并且天下棋的总数，并且1a1a2a3,a77 1112=132。则序列则序列a1+21,a2+21,a3+21,a77+21 也是一个严格递增序也是一个严格递增序列，并且列，并且22a1+21a2+21a3+21,a77+21 153。25组合数学组合数学

26、组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理于是，这154个数：a1,a2,a77,a1+21,a2+21,a77+21中的每一个都是1到153中的一个整数。假如我们将这个序列中的每个元素作为物体，1到153中的每个数作为盒子，依据鸽巢原理，在这154中必有两个元素相等，既然a1,a2,a77中没有相等的元素，a1+21,a2+21,a77+21中也没有相等的元素，则必定存在一个i和j(1i,j 77)使得aj=ai+21，从而这位国际象棋大师在第i+1,i+2,j天总共下了21盘棋。26组合数学组合数学组合数学组合数学(Combinatoric

27、s)(Combinatorics)鸽巢原理鸽巢原理例例5：从整数：从整数1,2,3,200中我们选择中我们选择101个整数。证明，在所个整数。证明，在所选择的这些整数之间存在两个这样的整数，其中一个可以被另选择的这些整数之间存在两个这样的整数，其中一个可以被另一个整除。一个整除。整数分解学问：任何一个整数都可以写成整数分解学问：任何一个整数都可以写成2ka的形式，其中，的形式，其中，k0，a为奇数。为奇数。对于对于1,2,3,200之间的一个整数，之间的一个整数，a是是100个数个数1,3,199中中的一个。因此，假如我们将所选择的的一个。因此，假如我们将所选择的101个数作为物体，个数作为物

28、体，1,3,199这这100个奇数作为盒子，依据鸽巢原则，在这个奇数作为盒子，依据鸽巢原则，在这101中中存在两个整数，当写成上述形式时这两个数具有相同的存在两个整数，当写成上述形式时这两个数具有相同的a值。令值。令这两个数是这两个数是2ra和和2sa。假如。假如rs，那么其次个数就能被第一个数整除。，那么其次个数就能被第一个数整除。27组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理例例6(中国乘余定理中国乘余定理)：令：令m和和n是两个互素的整数，并令是两个互素的整数，并令a和和b为两个整数，且为两个整数，且0am-1以及以及0b

29、n-1。于是存在一个整数。于是存在一个整数x，使得使得x除以除以m的余数为的余数为a，并且，并且x除以除以n的余数为的余数为b，即，即，x既可以既可以写成写成x=pm+a的同时又可以写成的同时又可以写成x=qn+b的形式，在这里，的形式，在这里，p和和q为两个整数。为两个整数。素数定义：假如两个整数素数定义：假如两个整数m和和n的最大公约数为的最大公约数为1，我们称，我们称m和和n为互素。为互素。为了证明这个结论，我们须要构造出为了证明这个结论，我们须要构造出x，那么如何构造？，那么如何构造？我们首先依据我们首先依据x=pm+a的形式构造的形式构造x(p取取0,1,n-1)，考虑如，考虑如下下

30、n个整数：个整数：a,m+a,2m+a,(n-1)m+a。这些整数中的每个。这些整数中的每个除以除以m的余数都为的余数都为a，即，即x可以写成可以写成pm+a的形式。的形式。假如我们能够证明假如我们能够证明a,m+a,2m+a,(n-1)m+a这这n个数中存在个数中存在一个数能够写成一个数能够写成qn+b的形式，则即可证明本题结论。的形式，则即可证明本题结论。28组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理假如a,m+a,2m+a,(n-1)m+a中的每个数除以n的余数都不相等，则我们将这n个数作为物体，n的余数0,1,2,n-1

31、作为盒子，依据鸽巢原理(定理3)，0,1,2,n-1中的每个数作为余数都会出现，特殊是数b作为余数也会出现。令p为整数，满足0 p n-1，且使数x=pm+a除以n的余数为b，则对某个适当的q，有x=qn+b，因此，x=pm+a且x=qn+b，从而x具有所要求的性质。否则，假如这n个数存在两个数除以n有相同的余数r，我们令这两个数分别为im+a和jm+a，其中，0ijn-1，因此，存在两个整数qi和qj，使得29组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理im+a=qin+r,jm+a=qjn+r，用其次个方程减去第一个方程，得到

32、(j-i)m=(qj-qi)n，这说明n是(j-i)m的一个因子。由于n与m没有除了1之外的公因子，因此n是j-i的一个因子，然而，0j-in-1，也就是说，n不行能是j-i的一个因子。这个冲突产生于我们假设a,m+a,2m+a,(n-1)m+a中有两个除以n会有相同的余数。因此，我们断言，这n个数中的每一个除以n都会有不同的余数，这样依据前述结论即可证明本题正确性。30组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理n鸽巢原理：加强形式鸽巢原理：加强形式n定理定理4.令令q1,q2,qn为为n个正整数。假如将个正整数。假如将q1+q

33、2+qn-n+1个物体放入个物体放入n个盒子内，那么，或个盒子内，那么，或者第一个盒子至少含有者第一个盒子至少含有q1个物体，或者其次个盒子至个物体，或者其次个盒子至少含有少含有q2个物体个物体,或者第或者第n个盒子至少含有个盒子至少含有qn个物个物体。体。证明：接受反证法，设将证明：接受反证法，设将q1+q2+qn-n+1个物体放入到个物体放入到n个个盒子中，假如对于每个盒子中，假如对于每个i=1,2,n，第，第i个盒子含有少于个盒子含有少于qi个物体，个物体，那么全部盒子中的物体总数不超过那么全部盒子中的物体总数不超过(q1-1)+(q2-1)+(qn-1)=q1+q2+qn-n这与物体的

34、总数为这与物体的总数为q1+q2+qn-n+1相冲突，所以或者第一个相冲突，所以或者第一个盒子至少含有盒子至少含有q1个物体，或者其次个盒子至少含有个物体，或者其次个盒子至少含有q2个物体个物体,或者第或者第n个盒子至少含有个盒子至少含有qn个物体。个物体。31组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理鸽巢原理的简洁形式是其加强形式通过鸽巢原理的简洁形式是其加强形式通过q1=q2=qn=2来实来实现的。这时，现的。这时，q1+q2+qn-n+1=2n-n+1=n+1。q1=2q2=3q3=4q1+q2+q3-3+1=7b12或或

35、或或b1b2b3b13b1432组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理推论推论1.m个物体，个物体，n个盒子，则至少有一个盒子里有不少于个盒子，则至少有一个盒子里有不少于(m-1)/n+1个物体。个物体。证明：接受反证法，设全部盒子了最多有证明：接受反证法，设全部盒子了最多有(m-1)/n个物体，则个物体，则n个盒子中的物体数最多为个盒子中的物体数最多为n(m-1)/n m-1，与假设冲突。，与假设冲突。推论推论2：若取若取n(m-1)+1个物体放入个物体放入n个盒子中，则至少有个盒子中，则至少有1个盒个盒子有子有m个物体。

36、个物体。这个推论相当于q1=q2=qn=m时的特殊状况。接受着色的术语来表述：假如接受着色的术语来表述：假如q1+q2+qn-n+1个物体中的个物体中的每一个物体被指定用每一个物体被指定用n种颜色中的一种着色，那么，存在这样一种颜色中的一种着色，那么，存在这样一个个i，使得第，使得第i种颜色的物体至少有种颜色的物体至少有qi个。个。33组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理推论推论3：若m1,m2,mn是n个正整数，而且则m1,m2,mn中至少有1个数不小于r。证明证明：将该问题与推论2建立联系。取n(r-1)+1个物体放入

37、n个盒子中，设mi(i=1,2,n)是第i个盒子中的物体个数，于是，这n个数m1,m2,mn的平均数为由于这个平均数大于r-1，故而有一个整数mi至少是r。34组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理练习练习1：假如：假如n个非负整数个非负整数m1,m2,mn的平均数小于的平均数小于r+1，即，即则m1,m2,mn中至少有1个数不超过r。练习练习2：假如：假如n个非负整数个非负整数m1,m2,mn的平均数小于的平均数小于r+1，即，即则m1,m2,mn中至少有1个数不超过r。35组合数学组合数学组合数学组合数学(Combina

38、torics)(Combinatorics)鸽巢原理鸽巢原理例例7.一篮子水果装有苹果、香蕉和橘子。为了保证篮子内或一篮子水果装有苹果、香蕉和橘子。为了保证篮子内或者至少者至少8个苹果或者至少个苹果或者至少6个香蕉或者至少个香蕉或者至少9个橘子，则放入篮子个橘子，则放入篮子中的水果的最小件数是多少？中的水果的最小件数是多少？例例8.两个碟子，其中一个比另一个小，它们均被分成两个碟子，其中一个比另一个小，它们均被分成200个恒个恒等的扇形。在大碟子中任选等的扇形。在大碟子中任选100个扇形并涂成红色，而其余的个扇形并涂成红色，而其余的100个扇形则涂成蓝色。在小碟子中，每一个扇形或者涂成红色，个

39、扇形则涂成蓝色。在小碟子中，每一个扇形或者涂成红色，或者涂成蓝色，所涂红色和蓝色扇形的数目没有限制。然后将或者涂成蓝色，所涂红色和蓝色扇形的数目没有限制。然后将小蝶子放到大碟子上面是两个碟子的中心重合。证明，能够将小蝶子放到大碟子上面是两个碟子的中心重合。证明，能够将两个碟子的扇形对齐使得小碟子和大碟子上相同颜色重合的扇两个碟子的扇形对齐使得小碟子和大碟子上相同颜色重合的扇形数目至少是形数目至少是100个。个。36组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理例例8：证明每个由：证明每个由n2+1个实数构成的序列个实数构成的序列a1

40、,a2,an2+1或者或者含有长度为含有长度为n+1的递增子序列，或者含有长度为的递增子序列，或者含有长度为n+1的递减子序的递减子序列。列。证明：我们首先了解一下什么是子序列的概念。证明：我们首先了解一下什么是子序列的概念。子序列：假如子序列：假如b1,b2,bm是一个序列，那么，是一个序列，那么，则是一个子序列，其中，则是一个子序列，其中，1i1 i2 ik m。例如，例如，b2,b4,b5是序列是序列b1,b2,b3,b4,b5,b6的一个子序列，而的一个子序列，而b2,b6,b5则不是。则不是。递增递增/减子序列：子序列减子序列：子序列 若满足条件若满足条件则称为递增子序列，而满足则称

41、为递增子序列，而满足 则称为递减子序列。则称为递减子序列。37组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理我们假设不存在长度为n+1的递增子序列，则须要证明必定存在长度为n+1的递减子序列。对于每一个k=1,2,n2+1，令mk为从ak起先的最长递增子序列长度。由于假设不存在长度为n+1的递增子序列，则对每个k=1,2,n2+1，有1 mkn。假如将m1,m2,mn2+1这n2+1个数作为物体，最长子序列的长度1,2,n作为n个盒子，其中，第i个盒子代表长度为i的序列。依据鸽巢原理的加强形式，在m1,m2,mn2+1中有n+1个是

42、相等的。令其中，1k1k2kn+1。设对于某个i=1,2,n，有于是，由于kin-1。1)假如我们把假如我们把Kn的边或者涂成红色或者涂成蓝色，那么，或的边或者涂成红色或者涂成蓝色，那么，或者者Kn的某条边是红色的，因此我们得到了一个红的某条边是红色的，因此我们得到了一个红K2，或者，或者Kn的全部边都是蓝色的，因此我们得到了一个蓝的全部边都是蓝色的，因此我们得到了一个蓝Kn。即，。即，KnK2,Kn，由于，由于r(2,n)是使得是使得KnK2,Kn成立的最小整数，成立的最小整数，所以，所以，r(2,n)n。2)假如我们将假如我们将Kn-1的边都涂成蓝色，那么我们既得不到红的边都涂成蓝色，那么

43、我们既得不到红K2，也得不到蓝，也得不到蓝Kn，所以，所以，r(2,n)n-1。47组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理2345672234567336914194491831551431661977mn常见的常见的Ramsey数数r(m,n)非平凡非平凡Ramsey数数平凡平凡Ramsey数数Ramsey定理说明白对于随意定理说明白对于随意m、n，r(m,n)都是存在的。虽然都是存在的。虽然Ramsey定理定理说明白说明白Ramsey数的存在性，但是对于数的存在性，但是对于Ramsey数的求法，目前还没有非平凡数的求法，

44、目前还没有非平凡的结论，比如说的结论，比如说r(3,10)、r(5,5)，现在还没人知道它们的精确取值。，现在还没人知道它们的精确取值。48组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理推论推论5：当：当m,n3时，时，r(m,n)r(m-1,n)+r(m,n-1)。证明：令证明：令N=r(m-1,n)+r(m,n-1)。对。对KN的边接受红、蓝两色进的边接受红、蓝两色进行随意着色。设行随意着色。设p是是KN的一个顶点，在的一个顶点，在KN中与中与p相连的边有相连的边有r(m-1,n)+r(m,n-1)-1条，这些边要么为红色，要么

45、为蓝色。依条，这些边要么为红色，要么为蓝色。依据鸽巢原理的加强形式，要么至少有据鸽巢原理的加强形式，要么至少有r(m-1,n)条红边，要么至少条红边，要么至少有有r(m,n-1)条蓝边。条蓝边。1)对于至少有对于至少有r(m-1,n)条红边的情形，以这些与条红边的情形，以这些与p相连的红边相连的红边除除p以外的以外的r(m-1,n)个顶点构成的完全图个顶点构成的完全图Kr(m-1,n)中，或者有中，或者有一个红色一个红色Km-1，或者有一个蓝色的，或者有一个蓝色的Kn。假如有一个红色的。假如有一个红色的Km-1，则该红色，则该红色Km-1加上顶点加上顶点p以及以及p与与Km-1之间的红边，就之

46、间的红边，就构成一个红色构成一个红色Km；否则，就有一个蓝色的；否则，就有一个蓝色的Kn。49组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理2)对于至少有r(m,n-1)条蓝边的情形，以这些与p相连的蓝边除p以外的r(m,n-1)个顶点构成的完全图Kr(m,n-1)中，或者有一个红色Km，或者有一个蓝色的Kn-1。假如有一个蓝色的Kn-1，则该蓝色Kn-1加上顶点p以及p与Kn-1之间的蓝边，就构成一个蓝色Kn；否则，就有一个红色的Km。这说明KNKm,Kn。由于r(m,n)是使得KNKm,Kn成立的最小整数N，所以，r(m,n)K

47、N=r(m-1,n)+r(m,n-1)。50组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理pRamsey定理的推广状况：定理的推广状况：假如假如n1,n2和和n3是大于或等于是大于或等于2的的3个整数，则存在一个整数个整数，则存在一个整数p使得使得KpKn1,Kn2,Kn3，也就是说，也就是说，假如假如Kp的每条边被涂上红色或蓝色或绿色，那么或者存在一个的每条边被涂上红色或蓝色或绿色，那么或者存在一个红红Kn1，或者存在一个蓝，或者存在一个蓝Kn2，或者存在一个绿，或者存在一个绿Kn3。pRamsey数的推广状况：数的推广状况：Ra

48、msey数数r(n1,n2,n3)是使得是使得KpKn1,Kn2,Kn3成立的最小整数成立的最小整数p。pRamsey定理的随意推广状况：定理的随意推广状况：KpKn1,Kn2,Kn3,Kns。pRamsey数的随意推广状况：数的随意推广状况：r(n1,n2,ns)。51组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理证明证明r(3,3,3)17。证明：考虑用证明：考虑用3种颜色进行着色的完全图种颜色进行着色的完全图K17，设，设p是是K17的一的一个顶点。由鸽巢原理可知，以个顶点。由鸽巢原理可知，以p为端点连接其余为端点连接其余16

49、个顶点的个顶点的16条线中必有条线中必有6条颜色相同条颜色相同(比如都是红色比如都是红色)。考察这。考察这6条线的除条线的除p外外的的6个顶点所形成的完全图个顶点所形成的完全图K6。假如。假如K6中有一条是红色，则这中有一条是红色，则这条边的两个顶端加上条边的两个顶端加上p就形成了一个红色三角形，结论成立。否就形成了一个红色三角形，结论成立。否则，则，K6中没有一条红色边，则中没有一条红色边，则K6为用两种颜色着色的完全图，为用两种颜色着色的完全图，此时此时K6必含有一个同色的三角形。因此，必含有一个同色的三角形。因此，K17中必含有一个同中必含有一个同色的三角形，从而色的三角形，从而r(3,

50、3,3)17。52组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理pRamsey定理的一般形式：定理的一般形式：在这种形式中点对在这种形式中点对(两个元素的子两个元素的子集集)由由t个元素的子集代替，其中个元素的子集代替，其中t1为某个整数。令为某个整数。令Knt表示表示n个个元素的集合中全部的元素的集合中全部的t个元素的子集的集合。个元素的子集的集合。p定理定理6(Ramsey定理一般形式定理一般形式)：给定整数给定整数t2及整数及整数q1,q2,qkt，存在一个整数，存在一个整数p使得使得KptKq1t,Kq2t,Kqkt，也就是