哈工大-组合数学讲义(2010版-新).ppt

高级软件工程高级软件工程组合数学组合数学(Combinatorics)哈尔滨工业大学哈尔滨工业大学(威海威海)计算机科学与技术学院计算机科学与技术学院孟凡超孟凡超 Email:Tele：151631557872组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)参考书目参考书目n组合数学组合数学(第四版第四版)/(美美)布鲁斯布鲁斯(Brualdi,R.A)著；北京机械工业出版社著；北京机械工业出版社,2005.2n卢开澄卢开澄,组合数学组合数学,清华大学出版社清华大学出版社.3组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)主要内容主要内容n概述概述n鸽巢原理鸽巢原理 n排列与组合排列与组合n生成排列和组合生成排列和组合 n二项式系数二项式系数 n容斥原理及应用容斥原理及应用 n递推关系和生成函数递推关系和生成函数n特殊计数序列特殊计数序列n二分图中的匹配二分图中的匹配 nPolya计数法计数法 4组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述n数学研究问题数学研究问题研究连续对象研究连续对象(微积分微积分)研究离散对象研究离散对象(组合数学组合数学)n组合数学研究的问题组合数学研究的问题将一个集合的物体排列成满足一些指定规则的格式，将一个集合的物体排列成满足一些指定规则的格式，如下两类问题反复出现：如下两类问题反复出现：排列存在性：排列存在性：如果想要排列一个集合的成员使得某如果想要排列一个集合的成员使得某些条件得以满足，并且这种排列不总是可能的，那些条件得以满足，并且这种排列不总是可能的，那么这种排列在什么样的条件下满足。么这种排列在什么样的条件下满足。排列的计数和分类：排列的计数和分类：如果一个指定的排列是可能的，如果一个指定的排列是可能的，那么会有多少种方法去实现它。此时，人们就可以那么会有多少种方法去实现它。此时，人们就可以计数并将它们分类。计数并将它们分类。5组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述棋盘的完美覆盖：棋盘的完美覆盖：考虑一张考虑一张8 8(8行行8列列)的的64个正方形的国际象个正方形的国际象棋棋盘，设有形状一样的多米诺牌，每张牌恰好覆盖棋盘上相邻的两棋棋盘，设有形状一样的多米诺牌，每张牌恰好覆盖棋盘上相邻的两个方格，那么，是否能够把个方格，那么，是否能够把32张多米诺牌摆放到棋盘上，使得任何两张多米诺牌摆放到棋盘上，使得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且棋盘上的所张多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且棋盘上的所有方格都被覆盖住？我们把这样一种排列称为棋盘的多米诺牌的完美有方格都被覆盖住？我们把这样一种排列称为棋盘的多米诺牌的完美覆盖。覆盖。8 8棋盘棋盘完美覆盖完美覆盖1完美覆盖完美覆盖2完美覆盖数：完美覆盖数：12988816=24(901)2)6组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述与上述问题同时出现的另外两种组合数学问题：与上述问题同时出现的另外两种组合数学问题：研究一个已知的排列：研究一个已知的排列：当人们建立起满足某些指定当人们建立起满足某些指定条件的一个排列以后，可能要考察这个排列的性质条件的一个排列以后，可能要考察这个排列的性质和结构，这样的结构可能会涉及到分类问题。和结构，这样的结构可能会涉及到分类问题。构造一个最优的排列：构造一个最优的排列：如果可能存在多于一个的排如果可能存在多于一个的排列，人们也许想要确定满足某些优化准则的一个排列，人们也许想要确定满足某些优化准则的一个排列，即找出某种规定意义下的列，即找出某种规定意义下的“最好的最好的”或或“最优最优的的”排列。排列。7组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述例，设例，设S=1,2,3,4为一个集合为一个集合 1)从从S中取两个不相同的元素进行排列，这样的排列有多少种中取两个不相同的元素进行排列，这样的排列有多少种2)列出所有可能的排列。列出所有可能的排列。3)求出两个元素之和最大的排列。求出两个元素之和最大的排列。组合数学是研究离散结构的存在、计数、组合数学是研究离散结构的存在、计数、分析和优化等问题的一门科学。分析和优化等问题的一门科学。8组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述问题问题1.如果将棋盘变为如果将棋盘变为 m n(m行行n列列)，则完美覆盖是否，则完美覆盖是否存在？存在？问题问题2.对于什么样的对于什么样的m和和n存在完美覆盖？存在完美覆盖？当且仅当当且仅当m和和n中至少有一个是偶数时，中至少有一个是偶数时，m n 棋盘存在棋盘存在完美覆盖。完美覆盖。不一定存在，不一定存在，例如，例如，3行行3列的棋盘就不存在完美覆盖。列的棋盘就不存在完美覆盖。9组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述问题问题3.8 8的棋盘用一把剪刀剪掉棋盘一副对角上的两的棋盘用一把剪刀剪掉棋盘一副对角上的两个方格，总共剩下个方格，总共剩下62个方格，那么是否能够排列个方格，那么是否能够排列31张多张多米诺牌来得出对这幅被剪过棋盘的完美覆盖？米诺牌来得出对这幅被剪过棋盘的完美覆盖？不存在完美覆盖。不存在完美覆盖。在一副在一副8 8棋盘上交替地将方格涂成黑色和白色，则其棋盘上交替地将方格涂成黑色和白色，则其中的中的32个方格是黑色，个方格是黑色，32个方格是白色。个方格是白色。如果我们剪掉棋盘一副对角线上的两个方格，那么我们如果我们剪掉棋盘一副对角线上的两个方格，那么我们就剪掉同样种颜色的两个方格，比如两个白色方格。这就剪掉同样种颜色的两个方格，比如两个白色方格。这就变成了就变成了32个黑方格和个黑方格和30个白方格。个白方格。但是，每张多米诺牌需要一个白方格和一个黑方格，于但是，每张多米诺牌需要一个白方格和一个黑方格，于是，是，31张不重叠的多米诺牌则覆盖住张不重叠的多米诺牌则覆盖住31个黑方格和个黑方格和31个个白方格。因此，这幅被剪过的棋盘不存在完美覆盖。白方格。因此，这幅被剪过的棋盘不存在完美覆盖。10组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述问题问题4.将将m n的棋盘上的方格交替涂成黑色和白色，切的棋盘上的方格交替涂成黑色和白色，切除一些方格，得到一块被剪过的棋盘，这块棋盘什么时除一些方格，得到一块被剪过的棋盘，这块棋盘什么时候有一个完美覆盖？候有一个完美覆盖？必要条件。这块被剪过的棋盘必须具有相等的黑方格数必要条件。这块被剪过的棋盘必须具有相等的黑方格数和白方格数。和白方格数。该条件不是充分条件。该条件不是充分条件。4 5棋盘棋盘 11组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述nB-牌：牌：设设b是一个正整数，我们用是一个正整数，我们用b个个1 1的方格并排的方格并排连接成的连接成的1 b的方格条来代替多米诺牌，这些方方格条的方格条来代替多米诺牌，这些方方格条称为称为b-牌。牌。一张一张5-5-牌牌一张一张2-2-牌牌（多米诺牌）（多米诺牌）nm n棋盘被棋盘被B-牌的完美覆盖：牌的完美覆盖：b-牌在牌在m n棋盘上没有棋盘上没有两张重叠，每一条两张重叠，每一条b-牌盖住棋盘上的牌盖住棋盘上的b个方格，并且盘上个方格，并且盘上的所有方格都被覆盖住。的所有方格都被覆盖住。12组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述问题问题5.m n棋盘何时具有棋盘何时具有b-牌的完美覆盖？牌的完美覆盖？当且仅当当且仅当b是是m的一个因子或者的一个因子或者b是是n的一个因子的一个因子充分性。充分性。如果如果b是是m的一个因子或者的一个因子或者b是是n的一个因子，的一个因子，则则m n棋盘存在棋盘存在b-牌完美覆盖。牌完美覆盖。如果b是m的一个因子，我们就可以对n列的每一列用m/b个b-牌覆盖并进而完成对mn棋盘的完美覆盖。如果b是n的一个引子，我们就可以对m行的每一行用n/b个b-牌覆盖并进而完成对mn棋盘的完美覆盖。13组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)概述概述必要性。必要性。如果如果m n棋盘存在棋盘存在b-牌完美覆盖，则牌完美覆盖，则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特殊计数序列特殊计数序列 n二分图匹配二分图匹配nPolya计数法计数法 15组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理n鸽巢原理：简单形式鸽巢原理：简单形式定理定理1.如果如果n+1个物体被放进个物体被放进n个盒子中，那么至少有一个盒个盒子中，那么至少有一个盒子包含两只或更多的物体。子包含两只或更多的物体。其它表述形式：其它表述形式：如果如果n+1只鸽子被放进只鸽子被放进n个鸽巢中，那么至少有一个鸽巢包含个鸽巢中，那么至少有一个鸽巢包含两只或更多的鸽子。两只或更多的鸽子。如果如果n+1个物体用种颜色涂色，那么必然有两个物体被涂成相个物体用种颜色涂色，那么必然有两个物体被涂成相同的颜色。同的颜色。16组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理4个物体个物体3个盒子个盒子存放存放1234517组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p例题：例题：例例1：在在13个人中存在两个人，他们的生日在同一个月份里个人中存在两个人，他们的生日在同一个月份里。考虑12个盒子，每个盒子对应一个月份，将13个人放到12个盒子中，则至少有一个盒子包含两个或两个以上的人，即，这在13个人中存在两个人，他们的生日在同一个月份里。例例2：设有设有n对已婚夫妇。为保证能够有一对夫妇被选出，至对已婚夫妇。为保证能够有一对夫妇被选出，至少要从这少要从这2n个人中选出多少人。个人中选出多少人。应至少选择n+1个人。考虑n个盒子，每个盒子对应一对夫妇。如果我们选择n+1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去，那么就有同一个盒子含有两个人，也就是说，我们选择了一对已婚夫妇。如果选择n个人，可以只选择所有丈夫或只选择所有的妻子。18组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p与鸽巢原理相关的原理与鸽巢原理相关的原理定理定理2：如果将如果将n个物体放入个物体放入n个盒子并且没有一个盒子是空的，个盒子并且没有一个盒子是空的，那么每个盒子恰好包含一个物体。那么每个盒子恰好包含一个物体。定理定理3：如果将如果将n个物体放入个物体放入n个盒子且没有一个盒子被放入多个盒子且没有一个盒子被放入多于一个物体，那么每个盒子里有一个物体。于一个物体，那么每个盒子里有一个物体。19组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p函数基本知识函数基本知识函数：函数：集合之间的函数集合之间的函数(function，或说映射，或说映射mapping)：设：设X和和Y是任意两个集合，而是任意两个集合，而f 是是X到到Y的一个关系，如果对于每一个的一个关系，如果对于每一个x X,有唯一的有唯一的y Y，使得，使得 f，称关系，称关系f 为函数，记作为函数，记作f:XY或或 X Y。原象和象：原象和象：如果如果 f，则则x称为自变元（原象），称为自变元（原象），y称为在称为在f 作用下作用下x的象的象(image)，f 亦可记作亦可记作y=f(x)，且记，且记f(X)=f(x)|x X。20组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p函数基本知识函数基本知识定义域：定义域：函数函数f:XY的定义域的定义域(domain)dom f 定义为：定义为：dom f =x|存在某个存在某个y Y使得使得 f =X。值域：值域：函数函数f:XY的值域的值域(range)ran f 定义为：定义为：ran f=y|(x)(x X)f Y。全函数：全函数：f 是全函数是全函数(total function)若若dom f=X，f 是全函数是全函数,否则称否则称f是偏函数是偏函数(partial function)。21组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p函数基本知识函数基本知识满射：满射：f 是满射是满射(surjection,或说或说f maps X onto Y)如果如果ran f =Y，即对任意的，即对任意的y Y都有原像。都有原像。设设f:XY是满射，即对任意的是满射，即对任意的y Y，必存在，必存在x X，使得，使得f(x)=y成立。成立。入射：入射：f 是入射是入射(injection，或说，或说f is one to one 是一对一是一对一)设设f:XY是入射，即对任意的是入射，即对任意的x1,x2 X，如果，如果f(x1)=f(x2),则则x1=x2，或者，或者 如果如果x1x2，则得，则得f(x1)f(x2)。22组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理p从函数角度来分析鸽巢原理的含义从函数角度来分析鸽巢原理的含义设设X和和Y是两个有限集，并令是两个有限集，并令f:XY是一个从是一个从X到到Y的函数。的函数。如果如果X的元素多于的元素多于Y的元素，那么的元素，那么f 就不是一对一的。就不是一对一的。如果如果X和和Y含有相同个数的元素，并且含有相同个数的元素，并且f 是映上是映上(onto)的，那么的，那么f 就是一对一的。就是一对一的。如果如果X和和Y含有相同个数的元素，并且含有相同个数的元素，并且f是一对一的，那么是一对一的，那么f 就就是映上的。是映上的。23组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理例例3：给定给定m个整数个整数a1,a2,am,存在整数存在整数k和和l，0klm，使得使得ak+1,ak+2,al能够被能够被m整除。也就是说，在序列整除。也就是说，在序列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，a1+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盘棋。盘棋。一共备战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组合数学组合数学组合数学组合数学(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组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理例例5：从整数从整数1,2,3,200中我们选择中我们选择101个整数。证明，在所个整数。证明，在所选择的这些整数之间存在两个这样的整数，其中一个可以被另选择的这些整数之间存在两个这样的整数，其中一个可以被另一个整除。一个整除。整数分解知识：整数分解知识：任何一个整数都可以写成2ka的形式，其中，k0，a为奇数。对于1,2,3,200之间的一个整数，a是100个数1,3,199中的一个。因此，如果我们将所选择的101个数作为物体，1,3,199这100个奇数作为盒子，根据鸽巢原则，在这101中存在两个整数，当写成上述形式时这两个数具有相同的a值。令这两个数是2ra和2sa。如果rs，那么第二个数就能被第一个数整除。27组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理例例6(中国乘余定理中国乘余定理)：令令m和和n是两个互素的整数，并令是两个互素的整数，并令a和和b为两个整数，且为两个整数，且0am-1以及以及0bn-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)，考虑如下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作为盒子，根据鸽巢原理(定理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，用第二个方程减去第一个方程，得到(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鸽巢原理：加强形式鸽巢原理：加强形式定理定理4.令令q1,q2,qn为为n个正整数。如果将个正整数。如果将q1+q2+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这与物体的总数为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或或或或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个物体。个物体。这个推论相当于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个物体放入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组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理例例7.一篮子水果装有苹果、香蕉和橘子。为了保证篮子内或一篮子水果装有苹果、香蕉和橘子。为了保证篮子内或者至少者至少8个苹果或者至少个苹果或者至少6个香蕉或者至少个香蕉或者至少9个橘子，则放入篮子个橘子，则放入篮子中的水果的最小件数是多少？中的水果的最小件数是多少？例例8.两个碟子，其中一个比另一个小，它们均被分成两个碟子，其中一个比另一个小，它们均被分成200个恒个恒等的扇形。在大碟子中任选等的扇形。在大碟子中任选100个扇形并涂成红色，而其余的个扇形并涂成红色，而其余的100个扇形则涂成蓝色。在小碟子中，每一个扇形或者涂成红色，个扇形则涂成蓝色。在小碟子中，每一个扇形或者涂成红色，或者涂成蓝色，所涂红色和蓝色扇形的数目没有限制。然后将或者涂成蓝色，所涂红色和蓝色扇形的数目没有限制。然后将小蝶子放到大碟子上面是两个碟子的中心重合。证明，能够将小蝶子放到大碟子上面是两个碟子的中心重合。证明，能够将两个碟子的扇形对齐使得小碟子和大碟子上相同颜色重合的扇两个碟子的扇形对齐使得小碟子和大碟子上相同颜色重合的扇形数目至少是形数目至少是100个。个。36组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理例例8：证明每个由证明每个由n2+1个实数构成的序列个实数构成的序列a1,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则不是。递增递增/减子序列：减子序列：子序列 若满足条件则称为递增子序列，而满足 则称为递减子序列。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个是相等的。令其中，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的边都涂成蓝色，那么我们既得不到红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数的求法，目前还没有非平凡数的求法，目前还没有非平凡的结论，比如说的结论，比如说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条，这些边要么为红色，要么为蓝色。根据鸽巢原理的加强形式，要么至少有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之间的红边，就构成一个红色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)KN=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数的推广情况：数的推广情况：Ramsey数数r(n1,n2,n3)是使得是使得KpKn1,Kn2,Kn3成立的最小整数成立的最小整数p。Ramsey定理的任意推广情况：定理的任意推广情况：KpKn1,Kn2,Kn3,Kns。Ramsey数的任意推广情况数的任意推广情况：r(n1,n2,ns)。51组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理证明证明r(3,3,3)17。证明：证明：考虑用3种颜色进行着色的完全图K17，设p是K17的一个顶点。由鸽巢原理可知，以p为端点连接其余16个顶点的16条线中必有6条颜色相同(比如都是红色)。考察这6条线的除p外的6个顶点所形成的完全图K6。如果K6中有一条是红色，则这条边的两个顶端加上p就形成了一个红色三角形，结论成立。否则，K6中没有一条红色边，则K6为用两种颜色着色的完全图，此时K6必含有一个同色的三角形。因此，K17中必含有一个同色的三角形，从而r(3,3,3)17。52组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理pRamsey定理的一般形式：定理的一般形式：在这种形式中点对在这种形式中点对(两个元素的子两个元素的子集集)由由t个元素的子集代替，其中个元素的子集代替，其中t1为某个整数。令为某个整数。令Knt表示表示n个个元素的集合中所有的元素的集合中所有的t个元素的子集的集合。个元素的子集的集合。定理定理6(Ramsey定理一般形式定理一般形式)：给定整数给定整数t2及整数及整数q1,q2,qkt，存在一个整数，存在一个整数p使得使得KptKq1t,Kq2t,Kqkt，也，也就是说，存在一个整数就是说，存在一个整数p使得如果将使得如果将p元素集合中的每一个元素集合中的每一个t元素元素子集指定子集指定k种颜色种颜色c1,c2,ck中的一种，那么或者存在中的一种，那么或者存在q1个元素，个元素，这些元素的所有这些元素的所有t元素子集都被指定颜色元素子集都被指定颜色c1，或者存在，或者存在q2个元素，个元素，这些元素的所有这些元素的所有t元素子集都被指定颜色元素子集都被指定颜色c2,或者存在或者存在qk个元个元素，这些元素的所有素，这些元素的所有t元素子集都被指定颜色元素子集都被指定颜色ck。Ramsey数的一般形式：数的一般形式：满足上述条件的最小整数满足上述条件的最小整数p被称为被称为Ramsey数数rt(qk,q1,q2,qk)。53组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理r1(q1,q2,qk)=q1+q2+qk-q+1。设t=1，于是，r1(q1,q2,qk)就是最小的数p，它满足如果p个元素集合的元素用颜色c1,c2,ck中的一种颜色涂色，那么或者存在q1个涂成颜色c1的元素，或者存在q2个涂成颜色c2的元素，或者存在qk个涂成颜色ck的元素。因此，由鸽巢原理的加强形式，有r1(q1,q2,qk)=q1+q2+qk-q+1。这说明Ramsey定理是鸽巢原理的加强形式的推广。54组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)鸽巢原理鸽巢原理若令若令R(m)=r(3,3,3)目前已知目前已知R(1)=3,R(2)=6,R(3,3,3)=17。m思考题：证明思考题：证明R(m)mR(m-1)-1+2。55组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)主要内容主要内容 n概述概述n鸽巢原理鸽巢原理 n排列与组合排列与组合 n生成排列和组合生成排列和组合n二项式系数二项式系数 n容斥原理及应用容斥原理及应用 n递推关系和生成函数递推关系和生成函数n特殊计数序列特殊计数序列 n二分图匹配二分图匹配nPolya计数法计数法 56组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)排列与组合排列与组合n四个计数原理四个计数原理加法原理加法原理 集合划分：集合划分：令令S为给定的非空集合，为给定的非空集合，A=S1,S2,Sn，若，若1)Si S,Si，i=1,2,n;2)SiSj=,ij,i,j=1,2,n；3)S=S1S2 Sn.则称则称A为集合为集合S的划分，其中的划分，其中Si(i=1,2,n)称为该划分的部分。称为该划分的部分。例：例：对对08级的研究生按照性别、年龄、专业进行划分。级的研究生按照性别、年龄、专业进行划分。57组合数学组合数学组合数学组合数学(Combinatorics)(Combinatorics)排列与组合排列与组合 加法原理：加法原理：设设S1,S2,Sn为