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

《哈工大-组合数学讲义(2010版-新)》由会员分享，可在线阅读，更多相关《哈工大-组合数学讲义(2010版-新)（444页珍藏版）》请在金锄头文库上搜索。

1、组合数学 (Combinatorics),哈尔滨工业大学(威海)计算机科学与技术学院 孟凡超Email: Tele：15163155787,参考书目,组合数学(第四版)/(美)布鲁斯(Brualdi, R.A)著；北京机械工业出版社,2005.2 卢开澄,组合数学,清华大学出版社.,主要内容,概述 鸽巢原理 排列与组合 生成排列和组合 二项式系数 容斥原理及应用 递推关系和生成函数 特殊计数序列 二分图中的匹配 Polya计数法,概述,数学研究问题 研究连续对象(微积分) 研究离散对象(组合数学) 组合数学研究的问题将一个集合的物体排列成满足一些指定规则的格式，如下两类问题反复出现： 排列存

2、在性：如果想要排列一个集合的成员使得某些条件得以满足，并且这种排列不总是可能的，那么这种排列在什么样的条件下满足。 排列的计数和分类：如果一个指定的排列是可能的，那么会有多少种方法去实现它。此时，人们就可以计数并将它们分类。,概述,棋盘的完美覆盖：考虑一张88(8行8列)的64个正方形的国际象棋棋盘，设有形状一样的多米诺牌，每张牌恰好覆盖棋盘上相邻的两个方格，那么，是否能够把32张多米诺牌摆放到棋盘上，使得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且棋盘上的所有方格都被覆盖住？我们把这样一种排列称为棋盘的多米诺牌的完美覆盖。,88棋盘,完美覆盖1,完美覆盖2,完美覆盖数：12988

3、816=24(901)2),概述,与上述问题同时出现的另外两种组合数学问题： 研究一个已知的排列：当人们建立起满足某些指定条件的一个排列以后，可能要考察这个排列的性质和结构，这样的结构可能会涉及到分类问题。 构造一个最优的排列：如果可能存在多于一个的排列，人们也许想要确定满足某些优化准则的一个排列，即找出某种规定意义下的“最好的”或“最优的”排列。,概述,例，设S=1,2,3,4为一个集合 1)从S中取两个不相同的元素进行排列，这样的排列有多少种 2)列出所有可能的排列。 3)求出两个元素之和最大的排列。,组合数学是研究离散结构的存在、计数、分析和优化等问题的一门科学。,概述,问题1. 如果将

4、棋盘变为 mn (m行n列)，则完美覆盖是否存在？,问题2. 对于什么样的m和n存在完美覆盖？,当且仅当m和n中至少有一个是偶数时，mn 棋盘存在完美覆盖。,不一定存在，例如，3行3列的棋盘就不存在完美覆盖。,概述,问题3. 88的棋盘用一把剪刀剪掉棋盘一副对角上的两个方格，总共剩下62个方格，那么是否能够排列31张多米诺牌来得出对这幅被剪过棋盘的完美覆盖？,不存在完美覆盖。 在一副88棋盘上交替地将方格涂成黑色和白色，则其中的32个方格是黑色，32个方格是白色。 如果我们剪掉棋盘一副对角线上的两个方格，那么我们就剪掉同样种颜色的两个方格，比如两个白色方格。这就变成了32个黑方格和30个白方格

5、。 但是，每张多米诺牌需要一个白方格和一个黑方格，于是，31张不重叠的多米诺牌则覆盖住31个黑方格和31个白方格。因此，这幅被剪过的棋盘不存在完美覆盖。,概述,问题4. 将mn的棋盘上的方格交替涂成黑色和白色，切除一些方格，得到一块被剪过的棋盘，这块棋盘什么时候有一个完美覆盖？,必要条件。这块被剪过的棋盘必须具有相等的黑方格数和白方格数。 该条件不是充分条件。,45棋盘,概述,B-牌：设b是一个正整数，我们用b个11的方格并排连接成的1b的方格条来代替多米诺牌，这些方方格条称为b-牌。,一张5-牌,一张2-牌 （多米诺牌）,mn棋盘被B-牌的完美覆盖：b-牌在mn棋盘上没有两张重叠，每一条b-

6、牌盖住棋盘上的b个方格，并且盘上的所有方格都被覆盖住。,概述,问题5. mn棋盘何时具有b-牌的完美覆盖？,当且仅当b是m的一个因子或者b是n的一个因子,充分性。如果b是m的一个因子或者b是n的一个因子，则mn棋盘存在b-牌完美覆盖。,如果b是m的一个因子，我们就可以对n列的每一列用m/b个b-牌覆盖并进而完成对mn棋盘的完美覆盖。 如果b是n的一个引子，我们就可以对m行的每一行用n/b个b-牌覆盖并进而完成对mn棋盘的完美覆盖。,概述,必要性。如果mn棋盘存在b-牌完美覆盖，则b或者是m一个因子或者是n的一个因子。,我们需要证明m和n除以b的余数至少有一个是零。设b除以m和n得到商p和q以及

7、余数r和s, m=pb+r (0rb-1) n=qb+s (0sb-1) 我们不妨设rs，因此，我们需要证明r=0。 采用反证法，设r0。,主要内容,概述 鸽巢原理 排列与组合 生成排列和组合 二项式系数 容斥原理及应用 递推关系和生成函数 特殊计数序列 二分图匹配 Polya计数法,鸽巢原理,鸽巢原理：简单形式 定理1. 如果n+1个物体被放进n个盒子中，那么至少有一个盒子包含两只或更多的物体。 其它表述形式： 如果n+1只鸽子被放进n个鸽巢中，那么至少有一个鸽巢包含两只或更多的鸽子。 如果n+1个物体用种颜色涂色，那么必然有两个物体被涂成相同的颜色。,鸽巢原理,4个物体,3个盒子,存放,1

8、,2,3,4,5,鸽巢原理,例题： 例1：在13个人中存在两个人，他们的生日在同一个月份里。 考虑12个盒子，每个盒子对应一个月份，将13个人放到12个盒子中，则至少有一个盒子包含两个或两个以上的人，即，这在13个人中存在两个人，他们的生日在同一个月份里。 例2：设有n对已婚夫妇。为保证能够有一对夫妇被选出，至少要从这2n个人中选出多少人。 应至少选择n+1个人。考虑n个盒子，每个盒子对应一对夫妇。如果我们选择n+1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去，那么就有同一个盒子含有两个人，也就是说，我们选择了一对已婚夫妇。 如果选择n个人，可以只选择所有丈夫或只选择所有的妻子。,鸽

9、巢原理,与鸽巢原理相关的原理 定理2：如果将n个物体放入n个盒子并且没有一个盒子是空的，那么每个盒子恰好包含一个物体。 定理3：如果将n个物体放入n个盒子且没有一个盒子被放入多于一个物体，那么每个盒子里有一个物体。,鸽巢原理,函数基本知识 函数：集合之间的函数(function，或说映射mapping)：设X和Y是任意两个集合，而f 是X到Y的一个关系，如果对于每一个xX,有唯一的yY，使得f，称关系f 为函数，记作f : XY或 X Y。 原象和象：如果f，则x称为自变元（原象），y称为在f 作用下x的象(image)，f 亦可记作y=f(x)，且记f(X)= f(x)| xX 。,鸽巢原理

10、,函数基本知识 定义域：函数f : XY的定义域(domain) dom f 定义为：dom f = x | 存在某个yY使得f =X 。 值域：函数f : XY的值域(range) ran f 定义为：ran f = y | (x)(xX)f Y。 全函数：f 是全函数(total function) 若dom f=X， f 是全函数,否则称f是偏函数(partial function)。,鸽巢原理,函数基本知识 满射： f 是满射( surjection, 或说f maps X onto Y ) 如果ran f = Y，即对任意的yY都有原像。 设f : XY是满射，即对任意的yY，必存在

11、xX，使得f(x) = y成立。入射：f 是入射(injection，或说f is one to one 是一对一) 设f : XY是入射，即对任意的x1, x2X，如果f (x1) = f (x2), 则x1 = x2，或者 如果x1x2，则得f (x1) f (x2)。,鸽巢原理,从函数角度来分析鸽巢原理的含义 设X和Y是两个有限集，并令f :XY是一个从X到Y的函数。 如果X的元素多于Y的元素，那么f 就不是一对一的。 如果X和Y含有相同个数的元素，并且f 是映上(onto)的，那么f 就是一对一的。 如果X和Y含有相同个数的元素，并且f是一对一的，那么f 就是映上的。,鸽巢原理,例3：

12、给定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除

13、以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整除。,鸽巢原理,例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+

14、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 。,鸽巢原理,于是，这154个数：a1,a2,a77,a1+21,a2+21,a77+21中的每一个都是1到153中的一个整数。如果我们将这个序列中的每个元素作为物体，1到153中的每个数作为盒子，根据鸽巢原理，在这154中必有两个元素相等，既然a1,a2,a77中没有相等的元素，a1+21,a2+21,a77+21中也没有相等的元素，则

15、必然存在一个i和j(1i,j 77)使得aj=ai+21，从而这位国际象棋大师在第i+1,i+2,j天总共下了21盘棋。,鸽巢原理,例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

16、。如果rs，那么第二个数就能被第一个数整除。,鸽巢原理,例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的形式，则即可证明本题结论。,