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

1、高级软件工程高级软件工程组合数学组合数学(Combinatorics)哈尔滨工业大学哈尔滨工业大学(威海威海)计算机科学与技术学院计算机科学与技术学院孟凡超孟凡超 Email: Tele：151631557872参考书目参考书目n组合数学组合数学(第四版第四版)/(美美)布鲁斯布鲁斯(Brualdi, R.A)著；著；北京机械工业出版社北京机械工业出版社,2005.2n卢开澄卢开澄,组合数学组合数学,清华大学出版社清华大学出版社.3主要内容主要内容n概述概述n鸽巢原理鸽巢原理 n排列与组合排列与组合n生成排列和组合生成排列和组合 n二项式系数二项式系数 n容斥原理及应用容斥原理及应用 n递推关

2、系和生成函数递推关系和生成函数n特殊计数序列特殊计数序列n二分图中的匹配二分图中的匹配 nPolya计数法计数法 4概述概述n数学研究问题数学研究问题研究连续对象研究连续对象(微积分微积分)研究离散对象研究离散对象(组合数学组合数学)n组合数学研究的问题组合数学研究的问题将一个集合的物体排列成满足一些指定规则的格式，将一个集合的物体排列成满足一些指定规则的格式，如下两类问题反复出现：如下两类问题反复出现：排列存在性：排列存在性：如果想要排列一个集合的成员使得某如果想要排列一个集合的成员使得某些条件得以满足，并且这种排列不总是可能的，那些条件得以满足，并且这种排列不总是可能的，那么这种排列在什么

3、样的条件下满足。么这种排列在什么样的条件下满足。排列的计数和分类：排列的计数和分类：如果一个指定的排列是可能的，如果一个指定的排列是可能的，那么会有多少种方法去实现它。此时，人们就可以那么会有多少种方法去实现它。此时，人们就可以计数并将它们分类。计数并将它们分类。5概述概述棋盘的完美覆盖：棋盘的完美覆盖：考虑一张考虑一张8 8(8行行8列列)的的64个正方形的国际象棋个正方形的国际象棋棋盘，设有形状一样的多米诺牌，每张牌恰好覆盖棋盘上相邻的两个棋盘，设有形状一样的多米诺牌，每张牌恰好覆盖棋盘上相邻的两个方格，那么，是否能够把方格，那么，是否能够把32张多米诺牌摆放到棋盘上，使得任何两张张多米诺

4、牌摆放到棋盘上，使得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且棋盘上的所有多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且棋盘上的所有方格都被覆盖住？我们把这样一种排列称为棋盘的多米诺牌的完美覆方格都被覆盖住？我们把这样一种排列称为棋盘的多米诺牌的完美覆盖。盖。8 8棋盘棋盘完美覆盖完美覆盖1完美覆盖完美覆盖2完美覆盖数：完美覆盖数：12988816=24 (901)2)6概述概述与上述问题同时出现的另外两种组合数学问题：与上述问题同时出现的另外两种组合数学问题：研究一个已知的排列：研究一个已知的排列：当人们建立起满足某些指定当人们建立起满足某些指定条件的一个排列以后，可能要考察

5、这个排列的性质条件的一个排列以后，可能要考察这个排列的性质和结构，这样的结构可能会涉及到分类问题。和结构，这样的结构可能会涉及到分类问题。构造一个最优的排列：构造一个最优的排列：如果可能存在多于一个的排如果可能存在多于一个的排列，人们也许想要确定满足某些优化准则的一个排列，人们也许想要确定满足某些优化准则的一个排列，即找出某种规定意义下的列，即找出某种规定意义下的“最好的最好的”或或“最优最优的的”排列。排列。7概述概述例，设例，设S=1,2,3,4为一个集合为一个集合 1)从从S中取两个不相同的元素进行排列，这样的排列有多少种中取两个不相同的元素进行排列，这样的排列有多少种2)列出所有可能的

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

7、就不存在完美覆盖。9概述概述问题问题3. 8 8的棋盘用一把剪刀剪掉棋盘一副对角上的两个的棋盘用一把剪刀剪掉棋盘一副对角上的两个方格，总共剩下方格，总共剩下62个方格，那么是否能够排列个方格，那么是否能够排列31张多米张多米诺牌来得出对这幅被剪过棋盘的完美覆盖？诺牌来得出对这幅被剪过棋盘的完美覆盖？不存在完美覆盖。不存在完美覆盖。在一副在一副8 8棋盘上交替地将方格涂成黑色和白色，则其棋盘上交替地将方格涂成黑色和白色，则其中的中的32个方格是黑色，个方格是黑色，32个方格是白色。个方格是白色。如果我们剪掉棋盘一副对角线上的两个方格，那么我们如果我们剪掉棋盘一副对角线上的两个方格，那么我们就剪掉

8、同样种颜色的两个方格，比如两个白色方格。这就剪掉同样种颜色的两个方格，比如两个白色方格。这就变成了就变成了32个黑方格和个黑方格和30个白方格。个白方格。但是，每张多米诺牌需要一个白方格和一个黑方格，于但是，每张多米诺牌需要一个白方格和一个黑方格，于是，是，31张不重叠的多米诺牌则覆盖住张不重叠的多米诺牌则覆盖住31个黑方格和个黑方格和31个个白方格。因此，这幅被剪过的棋盘不存在完美覆盖。白方格。因此，这幅被剪过的棋盘不存在完美覆盖。10概述概述问题问题4. 将将m n的棋盘上的方格交替涂成黑色和白色，切的棋盘上的方格交替涂成黑色和白色，切除一些方格，得到一块被剪过的棋盘，这块棋盘什么时除一些

9、方格，得到一块被剪过的棋盘，这块棋盘什么时候有一个完美覆盖？候有一个完美覆盖？必要条件。这块被剪过的棋盘必须具有相等的黑方格数必要条件。这块被剪过的棋盘必须具有相等的黑方格数和白方格数。和白方格数。该条件不是充分条件。该条件不是充分条件。 4 5棋盘棋盘 11概述概述nB-牌：牌：设设b是一个正整数，我们用是一个正整数，我们用b个个1 1的方格并排连的方格并排连接成的接成的1 b的方格条来代替多米诺牌，这些方方格条称为的方格条来代替多米诺牌，这些方方格条称为b-牌。牌。一张一张5-5-牌牌一张一张2-2-牌牌（多米诺牌）（多米诺牌）nm n棋盘被棋盘被B-牌的完美覆盖：牌的完美覆盖：b-牌在牌

10、在m n棋盘上没有棋盘上没有两张重叠，每一条两张重叠，每一条b-牌盖住棋盘上的牌盖住棋盘上的b个方格，并且盘上个方格，并且盘上的所有方格都被覆盖住。的所有方格都被覆盖住。12概述概述问题问题5. m n棋盘何时具有棋盘何时具有b-牌的完美覆盖？牌的完美覆盖？当且仅当当且仅当b是是m的一个因子或者的一个因子或者b是是n的一个因子的一个因子充分性。充分性。如果如果b是是m的一个因子或者的一个因子或者b是是n的一个因子，的一个因子，则则m n棋盘存在棋盘存在b-牌完美覆盖。牌完美覆盖。如果b是m的一个因子，我们就可以对n列的每一列用m/b个b-牌覆盖并进而完成对mn棋盘的完美覆盖。如果b是n的一个引

11、子，我们就可以对m行的每一行用n/b个b-牌覆盖并进而完成对mn棋盘的完美覆盖。13概述概述必要性。必要性。如果如果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主要内容主要内容n概述概述n鸽巢原理鸽巢原理 n排列与组合排列与组合 n生成排列和组合生成排列和组合n二项式系数二项式系数 n容斥原理及应用容斥原理

12、及应用 n递推关系和生成函数递推关系和生成函数n特殊计数序列特殊计数序列 n二分图匹配二分图匹配nPolya计数法计数法 15鸽巢原理鸽巢原理n鸽巢原理：简单形式鸽巢原理：简单形式定理定理1. 如果如果n+1个物体被放进个物体被放进n个盒子中，那么至少有一个盒个盒子中，那么至少有一个盒子包含两只或更多的物体。子包含两只或更多的物体。其它表述形式：其它表述形式：如果如果n+1只鸽子被放进只鸽子被放进n个鸽巢中，那么至少有一个鸽巢包含个鸽巢中，那么至少有一个鸽巢包含两只或更多的鸽子。两只或更多的鸽子。如果如果n+1个物体用种颜色涂色，那么必然有两个物体被涂成相个物体用种颜色涂色，那么必然有两个物体

13、被涂成相同的颜色。同的颜色。16鸽巢原理鸽巢原理4个物体个物体3个盒子个盒子存放存放1234517鸽巢原理鸽巢原理p例题：例题：例例1：在在13个人中存在两个人，他们的生日在同一个月份里个人中存在两个人，他们的生日在同一个月份里。考虑12个盒子，每个盒子对应一个月份，将13个人放到12个盒子中，则至少有一个盒子包含两个或两个以上的人，即，这在13个人中存在两个人，他们的生日在同一个月份里。例例2：设有设有n对已婚夫妇。为保证能够有一对夫妇被选出，至对已婚夫妇。为保证能够有一对夫妇被选出，至少要从这少要从这2n个人中选出多少人。个人中选出多少人。应至少选择n+1个人。考虑n个盒子，每个盒子对应一

14、对夫妇。如果我们选择n+1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去，那么就有同一个盒子含有两个人，也就是说，我们选择了一对已婚夫妇。如果选择n个人，可以只选择所有丈夫或只选择所有的妻子。18鸽巢原理鸽巢原理p与鸽巢原理相关的原理与鸽巢原理相关的原理定理定理2：如果将如果将n个物体放入个物体放入n个盒子并且没有一个盒子是空的，个盒子并且没有一个盒子是空的，那么每个盒子恰好包含一个物体。那么每个盒子恰好包含一个物体。定理定理3：如果将如果将n个物体放入个物体放入n个盒子且没有一个盒子被放入多个盒子且没有一个盒子被放入多于一个物体，那么每个盒子里有一个物体。于一个物体，那么每个盒子里有

15、一个物体。19鸽巢原理鸽巢原理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

16、。20鸽巢原理鸽巢原理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鸽巢原理鸽巢原理p函数基本知识函数基本知识满射：满射： f

17、 是满射是满射( 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鸽巢

18、原理鸽巢原理p从函数角度来分析鸽巢原理的含义从函数角度来分析鸽巢原理的含义设设X和和Y是两个有限集，并令是两个有限集，并令f :XY是一个从是一个从X到到Y的函数。的函数。如果如果X的元素多于的元素多于Y的元素，那么的元素，那么f 就不是一对一的。就不是一对一的。如果如果X和和Y含有相同个数的元素，并且含有相同个数的元素，并且f 是映上是映上(onto)的，那么的，那么f 就是一对一的。就是一对一的。如果如果X和和Y含有相同个数的元素，并且含有相同个数的元素，并且f是一对一的，那么是一对一的，那么f 就就是映上的。是映上的。23鸽巢原理鸽巢原理例例3：给定给定m个整数个整数a1,a2,am,存

19、在整数存在整数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，使得a

20、1+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鸽巢原理鸽巢原理例例4：一位国际象棋大师有一位国际象棋大师有11周的时间备战一场锦标赛，他决周的时间备战一场锦标赛，他决定每天至少下一盘棋，但是为了使自己不过分疲劳他还决定在定每天至少下一盘棋，但是为了使自己不过分疲劳他还决定在每周不能下棋超过每周不能下棋超过12盘。证明存在连续若干天，期间这位大师盘。证明存在连续若干天，期间这位大师恰好下了恰好下了21盘棋。盘棋。

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鸽巢原理鸽巢原理于是，这154个数：a1,a2,a77,a1+21,a2+21,a77+21中的每一个都是1到153中的一个整

22、数。如果我们将这个序列中的每个元素作为物体，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鸽巢原理鸽巢原理例例5：从整数从整数1,2,3,200中我们选择中我们选择101个整数。证明，在所个整数。证明，在所选择的这些整数之间存在两个这样的整数，其中一个可以被另选择的这些整数之间存在两个这样的整数，其中一个可以被另一个整除。一个整除。整数分解知识：整

23、数分解知识：任何一个整数都可以写成2ka的形式，其中，k0，a为奇数。对于1,2,3,200之间的一个整数，a是100个数1,3,199中的一个。因此，如果我们将所选择的101个数作为物体，1,3,199这100个奇数作为盒子，根据鸽巢原则，在这101中存在两个整数，当写成上述形式时这两个数具有相同的a值。令这两个数是2ra和2sa。如果rs，那么第二个数就能被第一个数整除。27鸽巢原理鸽巢原理例例6(中国乘余定理中国乘余定理)：令令m和和n是两个互素的整数，并令是两个互素的整数，并令a和和b为两个整数，且为两个整数，且0am-1以及以及0bn-1 。于是存在一个整数。于是存在一个整数x，使得

24、使得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+

25、a这n个数中存在一个数能够写成qn+b的形式，则即可证明本题结论。28鸽巢原理鸽巢原理如果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，因

26、此，存在两个整数qi和qj，使得29鸽巢原理鸽巢原理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鸽巢原理鸽巢原理n鸽巢原理：加强形式鸽巢原理：加强形式定理定理4. 令令q1,q2,qn

27、为为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相矛盾，所以或者第一个盒子至

28、少含有q1个物体，或者第二个盒子至少含有q2个物体,或者第n个盒子至少含有qn个物体。 31鸽巢原理鸽巢原理鸽巢原理的简单形式是其加强形式通过鸽巢原理的简单形式是其加强形式通过q1=q2=qn=2来实现来实现的。这时，的。这时， q1+q2+qn-n+1=2n-n+1=n+1。q1=2q2=3q3=4q1+q2+q3-3+1=7b12或或或或b1b2b3b13b1432鸽巢原理鸽巢原理推论推论1. m个物体，个物体，n个盒子，则至少有一个盒子里有不少于个盒子，则至少有一个盒子里有不少于(m-1)/n+1个物体。个物体。 证明：证明：采用反证法，设所有盒子了最多有(m-1)/n个物体，则n个盒子

29、中的物体数最多为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鸽巢原理鸽巢原理推论推论3：若m1,m2,mn是n个正整数，而且1.21rnmmmn

30、则m1,m2,mn中至少有1个数不小于r。证明证明：将该问题与推论2建立联系。取n(r-1)+1个物体放入n个盒子中，设mi (i=1,2,n)是第i个盒子中的物体个数，于是，这n个数m1,m2,mn的平均数为11) 1(1) 1(.21rnrnrnnmmmn由于这个平均数大于r-1，故而有一个整数mi至少是r。34鸽巢原理鸽巢原理练习练习1：如果n个非负整数m1,m2,mn的平均数小于r+1，即1.21rnmmmn则m1,m2,mn中至少有1个数不超过r。练习练习2：如果n个非负整数m1,m2,mn的平均数小于r+1，即1.21rnmmmn则m1,m2,mn中至少有1个数不超过r。35鸽巢原

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

32、，或者涂成蓝色，所涂红色和蓝色扇形的数目没有限制。然色，或者涂成蓝色，所涂红色和蓝色扇形的数目没有限制。然后将小蝶子放到大碟子上面是两个碟子的中心重合。证明，能后将小蝶子放到大碟子上面是两个碟子的中心重合。证明，能够将两个碟子的扇形对齐使得小碟子和大碟子上相同颜色重合够将两个碟子的扇形对齐使得小碟子和大碟子上相同颜色重合的扇形数目至少是的扇形数目至少是100个。个。36鸽巢原理鸽巢原理kiiibbb,.,21kiiibbb.21例例8：证明每个由证明每个由n2+1个实数构成的序列个实数构成的序列a1,a2,an2+1或者含或者含有长度为有长度为n+1的递增子序列，或者含有长度为的递增子序列，或

33、者含有长度为n+1的递减子序列。的递减子序列。证明：证明：我们首先了解一下什么是子序列的概念。子序列：子序列：如果b1,b2,bm是一个序列，那么，则是一个子序列，其中，1i1 i2 ik m。例如，b2,b4,b5是序列b1,b2,b3,b4,b5,b6的一个子序列，而b2,b6,b5则不是。递增递增/减子序列：减子序列：子序列 若满足条件则称为递增子序列，而满足 则称为递减子序列。kiiibbb,.,21kiiibbb.2137鸽巢原理鸽巢原理1iikkaa我们假设不存在长度为n+1的递增子序列，则需要证明必然存在长度为n+1的递减子序列。对于每一个k=1,2,n2+1，令mk为从ak开始

34、的最长递增子序列长度。由于假设不存在长度为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个是相等的。令121.nkkkmmm其中，1k1k2kn+1。设对于某个i=1,2,n，有于是，由于kin-1。1)如果我们把Kn的边或者涂成红色或者涂成蓝色，那么，或者Kn的某条边是红色的，因此我们得到了一个红K2，或者Kn的所有边都是蓝色的，因此我们得到了一个蓝Kn。即，KnK2,Kn，由于r(

35、2,n)是使得KnK2,Kn成立的最小整数，所以，r(2,n)n。2)如果我们将Kn-1的边都涂成蓝色，那么我们既得不到红K2，也得不到蓝Kn，所以，r(2,n)n-1。47鸽巢原理鸽巢原理2345672234567336914194491831551431661977mn常见的常见的Ramsey数数r(m,n)非平凡非平凡Ramsey数数平凡平凡Ramsey数数Ramsey定理说明了对于任意定理说明了对于任意m、n，r(m,n)都是存在的。虽然都是存在的。虽然Ramsey定理定理说明了说明了Ramsey数的存在性，但是对于数的存在性，但是对于Ramsey数的求法，目前还没有非平凡数的求法，目

36、前还没有非平凡的结论，比如说的结论，比如说r(3,10)、r(5,5)，现在还没人知道它们的准确取值。，现在还没人知道它们的准确取值。48鸽巢原理鸽巢原理推论推论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相连的红

37、边除p以外的r(m-1,n)个顶点构成的完全图Kr(m-1,n)中，或者有一个红色Km-1，或者有一个蓝色的Kn。如果有一个红色的Km-1，则该红色Km-1加上顶点p以及p与Km-1之间的红边，就构成一个红色Km；否则，就有一个蓝色的Kn。49鸽巢原理鸽巢原理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)

38、是使得KNKm,Kn成立的最小整数N，所以，r(m,n)KN=r(m-1,n)+r(m,n-1)。50鸽巢原理鸽巢原理pRamsey定理的推广情况：定理的推广情况： 如果如果n1,n2和和n3是大于或等于是大于或等于2的的3个整数，则存在一个整数个整数，则存在一个整数p使得使得KpKn1,Kn2,Kn3，也就是说，也就是说，如果如果Kp的每条边被涂上红色或蓝色或绿色，那么或者存在一个的每条边被涂上红色或蓝色或绿色，那么或者存在一个红红Kn1，或者存在一个蓝，或者存在一个蓝Kn2，或者存在一个绿，或者存在一个绿Kn3。pRamsey数的推广情况：数的推广情况：Ramsey数数r(n1,n2,n3

39、)是使得是使得KpKn1,Kn2,Kn3成立的最小整数成立的最小整数p。Ramsey定理的任意推广情况：定理的任意推广情况： KpKn1,Kn2,Kn3,Kns。Ramsey数的任意推广情况数的任意推广情况：r(n1,n2,ns)。51鸽巢原理鸽巢原理证明证明r(3,3,3)17。证明：证明：考虑用3种颜色进行着色的完全图K17，设p是K17的一个顶点。由鸽巢原理可知，以p为端点连接其余16个顶点的16条线中必有6条颜色相同(比如都是红色)。考察这6条线的除p外的6个顶点所形成的完全图K6。如果K6中有一条是红色，则这条边的两个顶端加上p就形成了一个红色三角形，结论成立。否则，K6中没有一条红

40、色边，则K6为用两种颜色着色的完全图，此时K6必含有一个同色的三角形。因此，K17中必含有一个同色的三角形，从而r(3,3,3)17。52鸽巢原理鸽巢原理pRamsey定理的一般形式：定理的一般形式： 在这种形式中点对在这种形式中点对(两个元素的子两个元素的子集集)由由t个元素的子集代替，其中个元素的子集代替，其中t1为某个整数。令为某个整数。令Knt表示表示n个个元素的集合中所有的元素的集合中所有的t个元素的子集的集合。个元素的子集的集合。定理定理6(Ramsey定理一般形式定理一般形式)： 给定整数给定整数t2及整数及整数q1,q2,qkt，存在一个整数，存在一个整数p使得使得KptKq1

41、t,Kq2t,Kqkt，也就，也就是说，存在一个整数是说，存在一个整数p使得如果将使得如果将p元素集合中的每一个元素集合中的每一个t元素子元素子集指定集指定k种颜色种颜色c1,c2,ck中的一种，那么或者存在中的一种，那么或者存在q1个元素，个元素，这些元素的所有这些元素的所有t元素子集都被指定颜色元素子集都被指定颜色c1，或者存在，或者存在q2个元素，个元素，这些元素的所有这些元素的所有t元素子集都被指定颜色元素子集都被指定颜色c2,或者存在或者存在qk个元个元素，这些元素的所有素，这些元素的所有t元素子集都被指定颜色元素子集都被指定颜色ck。Ramsey数的一般形式：数的一般形式：满足上述

42、条件的最小整数满足上述条件的最小整数p被称为被称为Ramsey数数rt(qk,q1,q2,qk)。53鸽巢原理鸽巢原理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鸽巢原理鸽巢原理若令若令R(m)=r(3,3,3)目前已知目前已

43、知R(1)=3, R(2)=6, R(3,3,3)=17。m思考题：证明思考题：证明R(m) mR(m-1)-1+2。55主要内容主要内容 n概述概述n鸽巢原理鸽巢原理 n排列与组合排列与组合 n生成排列和组合生成排列和组合n二项式系数二项式系数 n容斥原理及应用容斥原理及应用 n递推关系和生成函数递推关系和生成函数n特殊计数序列特殊计数序列 n二分图匹配二分图匹配nPolya计数法计数法 56排列与组合排列与组合n四个计数原理四个计数原理加法原理加法原理 集合划分：集合划分：令令S为给定的非空集合，为给定的非空集合，A=S1,S2,Sn，若，若1)Si S, Si ，i=1,2,n;2)Si

44、Sj= , ij, i,j=1,2,n；3)S=S1S2 Sn.则称则称A为集合为集合S的划分，其中的划分，其中Si(i=1,2,n)称为该划分的部分。称为该划分的部分。例：例：对对08级的研究生按照性别、年龄、专业进行划分。级的研究生按照性别、年龄、专业进行划分。57排列与组合排列与组合 加法原理：加法原理：设设S1,S2,Sn为集合为集合S的划分，则的划分，则S的元素的个的元素的个数可以通过找出它的每一个部分的元素的个数来确定，我们把数可以通过找出它的每一个部分的元素的个数来确定，我们把这些数相加，得到这些数相加，得到|S|=|S1|+|S2|+|Sn|。加法原理的另一表述方式：加法原理的

45、另一表述方式：如果有如果有p种方法能够从一堆物品中种方法能够从一堆物品中选择一个物品，而有选择一个物品，而有q种方法也能够从另一堆物品中选择一个物种方法也能够从另一堆物品中选择一个物品，那么从这两堆物品中选择一个物品的方法共有品，那么从这两堆物品中选择一个物品的方法共有p+q种。种。例：例：从从ICES中心中心(9人人)和信息安全中心和信息安全中心(6人人)选择一名研究生的选择一名研究生的方法数是多少？方法数是多少？ 58排列与组合排列与组合乘法原理：乘法原理：乘法原理：乘法原理：令令S是元素的序偶是元素的序偶(a,b)的集合，其中第一个元素的集合，其中第一个元素a来自大小为来自大小为p的一个

46、集合，而对于的一个集合，而对于a的每个选择，元素的每个选择，元素b存在着存在着q种选择，于是，种选择，于是，S的大小为的大小为pq，即，即，|S|=pq。 乘法原理的另一种表述方式：乘法原理的另一种表述方式：一项任务有一项任务有p个结果，而不论第个结果，而不论第一项任务的结果如何，第二项任务都有一项任务的结果如何，第二项任务都有q个结果，那么，这两项个结果，那么，这两项任务连续执行就有任务连续执行就有pq个结果。个结果。12abS1S21a1b2a2bc1c2c59排列与组合排列与组合乘法原理是加法原理的一个推论。乘法原理是加法原理的一个推论。令令a1,a2,ap是对元素是对元素a的的p个不同

47、的选择。我们将个不同的选择。我们将S划分成部分划分成部分S1,S2,Sp，其中，其中Si是是S内内第一个元素为第一个元素为ai(i=1,2,p)的序偶的集合。每个的序偶的集合。每个Si的大小为的大小为q，因此由加法原理有因此由加法原理有|S|=|S1|+|S2|+|Sp|=q+q+q=pq。1a1b2a2b1c2c集合集合1：第一个元素为：第一个元素为1，集合大小为，集合大小为3集合集合2：第一个元素为：第一个元素为2，集合大小为，集合大小为3|S|=3+3=23=660排列与组合排列与组合例：例：从从ICES中心中心(9人人)和信息安全中心和信息安全中心(6人人)各选择一名研究生各选择一名研

48、究生的方法数是多少？的方法数是多少？ 12abICES中心中心c3456789efgij信息安全中心信息安全中心123456789|S|=|S1|+|S2|+|S9|=89=7261排列与组合排列与组合思考题：思考题：从从08级研究生选择两名属于不同中心的学生方法数级研究生选择两名属于不同中心的学生方法数是多少？是多少？08级研究生情况：级研究生情况：(1)ICES：9人；人；(2)信息安全：信息安全：6人；人；(3)生物信息：生物信息：4人；人；(4)嵌入式：嵌入式：2人；人；(5)医学图像：医学图像：2人；人；(6)在职：在职：1人。人。62排列与组合排列与组合减法原理：减法原理：令令A是

49、一个集合，而是一个集合，而U是包含是包含A的更大的集合。设的更大的集合。设 :AxUxA是是A在在U中的补。那么中的补。那么A中的元素个数中的元素个数|A|由下列法则给出：由下列法则给出：|AUA63排列与组合排列与组合除法原理：除法原理：令令S是一个有限集，它以下述方式方式被划分成是一个有限集，它以下述方式方式被划分成k部分，每一部分，每一部分包含相同数目的元素。此时，划分中的部分数目由下述公部分包含相同数目的元素。此时，划分中的部分数目由下述公式给出：式给出：数在一个部分中的元素个| Sk 64排列与组合排列与组合例例1：确定数确定数34 52 117 138的正整数因子的个数？的正整数因

50、子的个数？例例2：两位数字有多少两个位互异且非零的两位数？两位数字有多少两个位互异且非零的两位数？例例3：计算口令字计划由计算口令字计划由0,1,2,9和小写字母和小写字母a, b, c,z中取中取出的出的6个字符构成的一个串组成。具有重复字符的计算机口令共个字符构成的一个串组成。具有重复字符的计算机口令共有多少？有多少？例例4：在在1000和和9999之间有多少具有不同数字的奇数？之间有多少具有不同数字的奇数？例例5：在在0和和10000之间有多少个整数恰好有一位数字是之间有多少个整数恰好有一位数字是5？65排列与组合排列与组合n集合的排列集合的排列S的的r排列：排列：令令r为正整数，我们把

51、为正整数，我们把n个元素的集合个元素的集合S的一个的一个r排排列定义为列定义为n个元素中的个元素中的r个元素的有序摆放。个元素的有序摆放。例如，例如，S=a, b, c，则，则S的的1排列为：排列为：abcS的的2排列为：排列为：abacbabccacbS的的3排列为：排列为：abcacbbacbcacabcba66排列与组合排列与组合r-排列数目：排列数目：我们用我们用P(n,r)表示表示n个元素集合的个元素集合的r-排列的数目。排列的数目。如果如果rn，P(n,r)=0； 如果如果r=1，P(n,1)=n；定理定理1：对于正整数：对于正整数n和和r，rn，有，有P(n,r)=n(n-1)

52、(n-r+1)。证明：证明：在构建n-元素集的一个r排列时，我们可以用n种方法选择第一项，不论第一项如何选出，都可以用n-1种方法选择第二项，以及不论前r-1项如何选出，都可以用n-(r-1)种方法选择第r项。根据乘法原理，这r项可以用n(n-1) (n-r+1)种方法选出。67排列与组合排列与组合123n第一项第一项有有n种种方法方法第二项第二项有有n-1种方法种方法12r第第r项有项有n-r+1种种方法方法S68排列与组合排列与组合例：例：将将08级的级的24个研究生排列使得个研究生排列使得ICES中心中心(9个学生个学生)的任意的任意两个学生都不能相继出现，这种排列的方法总数是多少？两个

53、学生都不能相继出现，这种排列的方法总数是多少？例：例：有多少种方法从有多少种方法从08级的级的24个研究生中取个研究生中取7个人进行排列，个人进行排列，并且使得王伟和谢冬辉不能以任何顺序相继出现？并且使得王伟和谢冬辉不能以任何顺序相继出现？69排列与组合排列与组合n循环排列：循环排列：例：例：6个孩子沿圆圈行进，他们能够以多少种不同的方式形成个孩子沿圆圈行进，他们能够以多少种不同的方式形成一个圆？一个圆？12345661234556123445612334561223456112345661234556123445612334561223456170排列与组合排列与组合如果两个循环排列通过一个

54、旋转，即一个循环移位，从其中的如果两个循环排列通过一个旋转，即一个循环移位，从其中的一个变到另一个，那么可以将它们看成是相同的。一个变到另一个，那么可以将它们看成是相同的。这样，在这样，在6个孩子的线性排列和个孩子的线性排列和6个孩子的循环排列之间就存在个孩子的循环排列之间就存在着着6到到1的对应。因此，要想求得循环排列的数目，我们只要用的对应。因此，要想求得循环排列的数目，我们只要用6去除线性排列的数目即可。所以，去除线性排列的数目即可。所以，6个孩子的循环排列数目等个孩子的循环排列数目等于于6!/6=5!71排列与组合排列与组合定理定理2：n个元素的集合的循环个元素的集合的循环r-排列的个

55、数为排列的个数为)!(!),(rnrnrrnP特别地，特别地，n个元素的循环排列的个数是个元素的循环排列的个数是(n-1)!。证明：证明：可以把线性r-排列的集合划分成一些部分，使得两个线性r-排列对应同一个循环r-排列当且仅当它们在同一个部分中。于是，循环r-排列的个数等于部分的个数。既然每一个部分都含有r个线性r-排列，根据除法原理，部分的数目等于)!(!),(rnrnrrnP72排列与组合排列与组合例：例：ICES中心中心08级的级的9个研究生要围坐一个圆桌，其中有两个研究生要围坐一个圆桌，其中有两个人不愿意彼此挨着就座，共有多少循环座位排放方法？个人不愿意彼此挨着就座，共有多少循环座位

56、排放方法？例：例：6男男6女围坐一个圆桌，如果男女交替围坐，可以有多少女围坐一个圆桌，如果男女交替围坐，可以有多少围坐方式？围坐方式？73排列与组合排列与组合n集合的组合集合的组合S的的r组合：组合：令令r为非负整数，我们把为非负整数，我们把n个元素的集合个元素的集合S的的r-组合组合可以定义为从可以定义为从S的的n个元素中对个元素中对r个元素的无序选择。个元素的无序选择。例如，例如，S=a, b, c, d 的的3的组合为的组合为a, b, c，a, b, d，a, c, d，b, c, dr-组合数目：组合数目：我们用我们用 表示表示n-元素集的元素集的r-组合的个数。组合的个数。如果如果

57、rn， =0；如果；如果r0， =0。nrnr0rn0=1n1=nnn=100=174排列与组合排列与组合定理定理3：对于对于0rn，rnrrnP!),(因此，因此，)!( !rnrnrn证明：证明：令S是一个n-元素集。S的每个r-排列都是由下面的两个任务执行结果产生。1)从S中选出r个元素。2)将所选出的r个元素以某种顺序排列。执行第一个任务的方法数根据定义可知为组合数 。nr75排列与组合排列与组合执行第二个任务的方法数则是P(r,r)=r!。 根据乘法原理我们有rnrrnP!),(所以，)!( !),(rnrnrrnPrn76排列与组合排列与组合定理定理4：nnnnnn2.210证明：

58、通过对证明：通过对n-元素集元素集S的组合计数来证明。的组合计数来证明。1)S的每一个组合是的每一个组合是S对于对于r(r=0,1,2,n)的一个的一个r-组合。由于组合。由于nr等于等于S的的r-组合数，由加法原理组合数，由加法原理nnnnn.210等于等于S的所有组合的总个数。的所有组合的总个数。77排列与组合排列与组合2)把一个组合的选取分成把一个组合的选取分成n个任务来完成。令个任务来完成。令S的元素为的元素为x1,x2,xn。在选择。在选择S的一个组合时，对的一个组合时，对n个元素的每一个都个元素的每一个都有两种选择：有两种选择：xi(i=1,2,n)要么在这个组合里；要么在这个组合

59、里； xi(i=1,2,n)要么不在这个组合里。因此，由乘法原理，存要么不在这个组合里。因此，由乘法原理，存在在2n种方法使得我们可以形成种方法使得我们可以形成S的一个组合。的一个组合。使两种方法相等就完成了定理的证明。使两种方法相等就完成了定理的证明。78排列与组合排列与组合n多重集排列多重集排列多重集多重集多重集同一般集合一样，是一组对象的整体，只不过不像一多重集同一般集合一样，是一组对象的整体，只不过不像一般集合那样必须要求集合中的每个元素互不相同。例如，般集合那样必须要求集合中的每个元素互不相同。例如，S=a,a,a,b,c,c,d,d,d,d,d是一个是一个10元素的多重集，其中，有

60、元素的多重集，其中，有3个个a，1个个b，2个个c和和4个个d。我们可以将。我们可以将S表示为表示为S=3 a,1 b,2 c,4 d。一般地，多重集可以表示为一般地，多重集可以表示为S=k1 a1,k2 a2,kn an，其中，其中，a1,a2,an为为S中所有的互不相同的元素，中所有的互不相同的元素，S中有中有ki个个ai(1i n)，称称ki为为ai的重数，的重数，ki是正整数，也可以是是正整数，也可以是，表示，表示S中有无限多个中有无限多个ai。79排列与组合排列与组合多重集排列多重集排列设设S=3 a,1 b,2 c,4 d ，那么，那么acbc，cbcc为为S的的4排列，而排列，而