《哈工大组合数学讲义新.pptx》由会员分享，可在线阅读，更多相关《哈工大组合数学讲义新.pptx（444页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、参考书目组合数学(第四版)/(美)布鲁斯(Brualdi,R.A)著；北京机械工业出版社,2005.2卢开澄,组合数学,清华大学出版社.第1页/共444页主要内容概述鸽巢原理 排列与组合生成排列和组合 二项式系数 容斥原理及应用 递推关系和生成函数特殊计数序列二分图中的匹配 Polya计数法 第2页/共444页概述数学研究问题研究连续对象(微积分)研究离散对象(组合数学)组合数学研究的问题将一个集合的物体排列成满足一些指定规则的格式，如下两类问题反复出现：排列存在性：如果想要排列一个集合的成员使得某些条件得以满足，并且这种排列不总是可能的，那么这种排列在什么样的条件下满足。排列的计数和分类：如
2、果一个指定的排列是可能的，那么会有多少种方法去实现它。此时，人们就可以计数并将它们分类。第3页/共444页概述棋盘的完美覆盖：考虑一张8 8(8行8列)的64个正方形的国际象棋棋盘，设有形状一样的多米诺牌，每张牌恰好覆盖棋盘上相邻的两个方格，那么，是否能够把32张多米诺牌摆放到棋盘上，使得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且棋盘上的所有方格都被覆盖住？我们把这样一种排列称为棋盘的多米诺牌的完美覆盖。8 8棋盘完美覆盖1完美覆盖2完美覆盖数：12988816=24(901)2)第4页/共444页概述与上述问题同时出现的另外两种组合数学问题：研究一个已知的排列：当人们建立起满足
3、某些指定条件的一个排列以后，可能要考察这个排列的性质和结构，这样的结构可能会涉及到分类问题。构造一个最优的排列：如果可能存在多于一个的排列，人们也许想要确定满足某些优化准则的一个排列，即找出某种规定意义下的“最好的”或“最优的”排列。第5页/共444页概述例，设S=1,2,3,4为一个集合 1)从S中取两个不相同的元素进行排列，这样的排列有多少种2)列出所有可能的排列。3)求出两个元素之和最大的排列。组合数学是研究离散结构的存在、计数、组合数学是研究离散结构的存在、计数、分析和优化等问题的一门科学。分析和优化等问题的一门科学。第6页/共444页概述问题1.如果将棋盘变为 m n(m行n列)，则
4、完美覆盖是否存在？问题2.对于什么样的m和n存在完美覆盖？当且仅当m和n中至少有一个是偶数时，m n 棋盘存在完美覆盖。不一定存在，例如，3行3列的棋盘就不存在完美覆盖。第7页/共444页概述问题3.8 8的棋盘用一把剪刀剪掉棋盘一副对角上的两个方格，总共剩下62个方格，那么是否能够排列31张多米诺牌来得出对这幅被剪过棋盘的完美覆盖？不存在完美覆盖。在一副8 8棋盘上交替地将方格涂成黑色和白色，则其中的32个方格是黑色，32个方格是白色。如果我们剪掉棋盘一副对角线上的两个方格，那么我们就剪掉同样种颜色的两个方格，比如两个白色方格。这就变成了32个黑方格和30个白方格。但是，每张多米诺牌需要一个
5、白方格和一个黑方格，于是，31张不重叠的多米诺牌则覆盖住31个黑方格和31个白方格。因此，这幅被剪过的棋盘不存在完美覆盖。第8页/共444页概述问题4.将m n的棋盘上的方格交替涂成黑色和白色，切除一些方格，得到一块被剪过的棋盘，这块棋盘什么时候有一个完美覆盖？必要条件。这块被剪过的棋盘必须具有相等的黑方格数和白方格数。该条件不是充分条件。4 5棋盘 第9页/共444页概述nB-牌：设b是一个正整数，我们用b个1 1的方格并排连接成的1 b的方格条来代替多米诺牌，这些方方格条称为b-牌。一张一张5-5-牌牌一张一张2-2-牌牌（多米诺牌）（多米诺牌）nm n棋盘被B-牌的完美覆盖：b-牌在m
6、n棋盘上没有两张重叠，每一条b-牌盖住棋盘上的b个方格，并且盘上的所有方格都被覆盖住。第10页/共444页概述问题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棋盘的完美覆盖。第11页/共444页概述必要性。如果m n棋盘存在b-牌完美覆盖，则b或者是m一个因子或者是n的一个因子。我们需要证明m和n
7、除以b的余数至少有一个是零。设b除以m和n得到商p和q以及余数r和s,m=pb+r (0rb-1)n=qb+s (0sb-1)我们不妨设rs，因此，我们需要证明r=0。采用反证法，设r0。第12页/共444页主要内容概述鸽巢原理 排列与组合 生成排列和组合二项式系数 容斥原理及应用 递推关系和生成函数特殊计数序列 二分图匹配Polya计数法 第13页/共444页鸽巢原理n鸽巢原理：简单形式定理1.如果n+1个物体被放进n个盒子中，那么至少有一个盒子包含两只或更多的物体。其它表述形式：如果n+1只鸽子被放进n个鸽巢中，那么至少有一个鸽巢包含两只或更多的鸽子。如果n+1个物体用种颜色涂色，那么必然
8、有两个物体被涂成相同的颜色。第14页/共444页鸽巢原理4个物体3个盒子存放12345第15页/共444页鸽巢原理p例题：例1：在13个人中存在两个人，他们的生日在同一个月份里。考虑12个盒子，每个盒子对应一个月份，将13个人放到12个盒子中，则至少有一个盒子包含两个或两个以上的人，即，这在13个人中存在两个人，他们的生日在同一个月份里。例2：设有n对已婚夫妇。为保证能够有一对夫妇被选出，至少要从这2n个人中选出多少人。应至少选择n+1个人。考虑n个盒子，每个盒子对应一对夫妇。如果我们选择n+1个人并把他们中的每一个人放到他们对偶所在的那个盒子中去，那么就有同一个盒子含有两个人，也就是说，我们
9、选择了一对已婚夫妇。如果选择n个人，可以只选择所有丈夫或只选择所有的妻子。第16页/共444页鸽巢原理p与鸽巢原理相关的原理定理2：如果将n个物体放入n个盒子并且没有一个盒子是空的，那么每个盒子恰好包含一个物体。定理3：如果将n个物体放入n个盒子且没有一个盒子被放入多于一个物体，那么每个盒子里有一个物体。第17页/共444页鸽巢原理p函数基本知识函数：集合之间的函数(function，或说映射mapping)：设X和Y是任意两个集合，而f 是X到Y的一个关系，如果对于每一个x X,有唯一的y Y，使得 f，称关系f 为函数，记作f:XY或 X Y。原象和象：如果 f，则x称为自变元（原象），y
10、称为在f 作用下x的象(image)，f 亦可记作y=f(x)，且记f(X)=f(x)|x X。第18页/共444页鸽巢原理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)。第19页/共444页鸽巢原理p函数基本知识满射：f 是满射(surjection,或说f maps X onto
11、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)。第20页/共444页鸽巢原理p从函数角度来分析鸽巢原理的含义设X和Y是两个有限集，并令f:XY是一个从X到Y的函数。如果X的元素多于Y的元素，那么f 就不是一对一的。如果X和Y含有相同个数的元素，并且f 是映上(onto)的，那么f 就是一对一的。如果X和Y含
12、有相同个数的元素，并且f是一对一的，那么f 就是映上的。第21页/共444页鸽巢原理例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有相同
13、的余数。因此，存在整数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整除。第22页/共444页鸽巢原理例4：一位国际象棋大师有11周的时间备战一场锦标赛，他决定每天至少下一盘棋，但是为了使自己不过分疲劳他还决定在每周不能下棋超过12盘。证明存在连续若干天，期间这位大师恰好下了21盘棋。一共备战117=77天。令x1,x2,x77分别为第1,2,77天下的棋数，则xi1(i=1,2,77)。我们构造如下严
14、格递增序列：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。第23页/共444页鸽巢原理于是，这154个数：a1,a2,a77,a1+21,a2+21,a77+21中的每一个都是1到153中的一个整数。如果我们将这个序列中的每个元素作为物体，1到153中的每个数作为盒子，根据鸽巢原理，在这154中必有两个元素相等，既然a
15、1,a2,a77中没有相等的元素，a1+21,a2+21,a77+21中也没有相等的元素，则必然存在一个i和j(1i,j 77)使得aj=ai+21，从而这位国际象棋大师在第i+1,i+2,j天总共下了21盘棋。第24页/共444页鸽巢原理例5：从整数1,2,3,200中我们选择101个整数。证明，在所选择的这些整数之间存在两个这样的整数，其中一个可以被另一个整除。整数分解知识：任何一个整数都可以写成2ka的形式，其中，k0，a为奇数。对于1,2,3,200之间的一个整数，a是100个数1,3,199中的一个。因此，如果我们将所选择的101个数作为物体，1,3,199这100个奇数作为盒子，根
16、据鸽巢原则，在这101中存在两个整数，当写成上述形式时这两个数具有相同的a值。令这两个数是2ra和2sa。如果rs，那么第二个数就能被第一个数整除。第25页/共444页鸽巢原理例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
17、-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的形式，则即可证明本题结论。第26页/共444页鸽巢原理如果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
18、=qn+b，因此，x=pm+a且x=qn+b，从而x具有所要求的性质。否则，如果这n个数存在两个数除以n有相同的余数r，我们令这两个数分别为im+a和jm+a，其中，0ijn-1，因此，存在两个整数qi和qj，使得第27页/共444页鸽巢原理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会有相同的余数。因此，
19、我们断言，这n个数中的每一个除以n都会有不同的余数，这样根据前述结论即可证明本题正确性。第28页/共444页鸽巢原理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相矛
20、盾，所以或者第一个盒子至少含有q1个物体，或者第二个盒子至少含有q2个物体,或者第n个盒子至少含有qn个物体。第29页/共444页鸽巢原理鸽巢原理的简单形式是其加强形式通过q1=q2=qn=2来实现的。这时，q1+q2+qn-n+1=2n-n+1=n+1。q1=2q2=3q3=4q1+q2+q3-3+1=7b12或或b1b2b3b13b14第30页/共444页鸽巢原理推论1.m个物体，n个盒子，则至少有一个盒子里有不少于(m-1)/n+1个物体。证明：采用反证法，设所有盒子了最多有(m-1)/n个物体，则n个盒子中的物体数最多为n(m-1)/n m-1，与假设矛盾。推论2：若取n(m-1)+1
21、个物体放入n个盒子中，则至少有1个盒子有m个物体。这个推论相当于q1=q2=qn=m时的特殊情况。采用着色的术语来表述：如果q1+q2+qn-n+1个物体中的每一个物体被指定用n种颜色中的一种着色，那么，存在这样一个i，使得第i种颜色的物体至少有qi个。第31页/共444页鸽巢原理推论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。第32页/共44
22、4页鸽巢原理练习1：如果n个非负整数m1,m2,mn的平均数小于r+1，即则m1,m2,mn中至少有1个数不超过r。练习2：如果n个非负整数m1,m2,mn的平均数小于r+1，即则m1,m2,mn中至少有1个数不超过r。第33页/共444页鸽巢原理例7.一篮子水果装有苹果、香蕉和橘子。为了保证篮子内或者至少8个苹果或者至少6个香蕉或者至少9个橘子，则放入篮子中的水果的最小件数是多少？例8.两个碟子，其中一个比另一个小，它们均被分成200个恒等的扇形。在大碟子中任选100个扇形并涂成红色，而其余的100个扇形则涂成蓝色。在小碟子中，每一个扇形或者涂成红色，或者涂成蓝色，所涂红色和蓝色扇形的数目没
23、有限制。然后将小蝶子放到大碟子上面是两个碟子的中心重合。证明，能够将两个碟子的扇形对齐使得小碟子和大碟子上相同颜色重合的扇形数目至少是100个。第34页/共444页鸽巢原理例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则不是。递增/减子序列：子序列 若满足条件则称为递增子序列，而满足 则
24、称为递减子序列。第35页/共444页鸽巢原理我们假设不存在长度为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的边或者涂成红色或者涂
25、成蓝色，那么，或者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。第45页/共444页鸽巢原理2345672234567336914194491831551431661977mn常见的Ramsey数r(m,n)非平凡Ramsey数平凡Ramsey数Ramsey定理说明了对于任意m、n，r(m,n)都是存在的。虽然Ramsey定理说明了Ramsey
26、数的存在性，但是对于Ramsey数的求法，目前还没有非平凡的结论，比如说r(3,10)、r(5,5)，现在还没人知道它们的准确取值。第46页/共444页鸽巢原理推论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
27、(m-1,n)个顶点构成的完全图Kr(m-1,n)中，或者有一个红色Km-1，或者有一个蓝色的Kn。如果有一个红色的Km-1，则该红色Km-1加上顶点p以及p与Km-1之间的红边，就构成一个红色Km；否则，就有一个蓝色的Kn。第47页/共444页鸽巢原理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)是使得
28、KNKm,Kn成立的最小整数N，所以，r(m,n)KN=r(m-1,n)+r(m,n-1)。第48页/共444页鸽巢原理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)。
29、第49页/共444页鸽巢原理证明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。第50页/共444页鸽巢原理pRamsey定理的一般形式：在这种形式中点对(两个元素的子集)由t个元
30、素的子集代替，其中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,q
31、2,qk)。第51页/共444页鸽巢原理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定理是鸽巢原理的加强形式的推广。第52页/共444页鸽巢原理若令R(m)=r(3,3,3)目前已知R(1)=3,R(2)=6,R(3,3,3)=17。m思考题：证明R(m)mR(
32、m-1)-1+2。第53页/共444页主要内容 概述鸽巢原理 排列与组合 生成排列和组合二项式系数 容斥原理及应用 递推关系和生成函数特殊计数序列 二分图匹配Polya计数法 第54页/共444页排列与组合n四个计数原理加法原理 集合划分：令S为给定的非空集合，A=S1,S2,Sn，若1)Si S,Si，i=1,2,n;2)SiSj=,ij,i,j=1,2,n；3)S=S1 S2 Sn.则称A为集合S的划分，其中Si(i=1,2,n)称为该划分的部分。例：对08级的研究生按照性别、年龄、专业进行划分。第55页/共444页排列与组合 加法原理：设S1,S2,Sn为集合S的划分，则S的元素的个数可
33、以通过找出它的每一个部分的元素的个数来确定，我们把这些数相加，得到|S|=|S1|+|S2|+|Sn|。加法原理的另一表述方式：如果有p种方法能够从一堆物品中选择一个物品，而有q种方法也能够从另一堆物品中选择一个物品，那么从这两堆物品中选择一个物品的方法共有p+q种。例：从ICES中心(9人)和信息安全中心(6人)选择一名研究生的方法数是多少？第56页/共444页排列与组合乘法原理：乘法原理：令S是元素的序偶(a,b)的集合，其中第一个元素a来自大小为p的一个集合，而对于a的每个选择，元素b存在着q种选择，于是，S的大小为pq，即，|S|=pq。乘法原理的另一种表述方式：一项任务有p个结果，而
34、不论第一项任务的结果如何，第二项任务都有q个结果，那么，这两项任务连续执行就有pq个结果。12abS1S21a1b2a2bc1c2c第57页/共444页排列与组合乘法原理是加法原理的一个推论。令a1,a2,ap是对元素a的p个不同的选择。我们将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=6第58页/共444页排列与组合例：从ICES中心(9
35、人)和信息安全中心(6人)各选择一名研究生的方法数是多少？12abICES中心c3456789efgij信息安全中心123456789|S|=|S1|+|S2|+|S9|=89=72第59页/共444页排列与组合思考题：从08级研究生选择两名属于不同中心的学生方法数是多少？08级研究生情况：(1)ICES：9人；(2)信息安全：6人；(3)生物信息：4人；(4)嵌入式：2人；(5)医学图像：2人；(6)在职：1人。第60页/共444页排列与组合减法原理：令A是一个集合，而U是包含A的更大的集合。设 是A在U中的补。那么A中的元素个数|A|由下列法则给出：第61页/共444页排列与组合除法原理：
36、令S是一个有限集，它以下述方式方式被划分成k部分，每一部分包含相同数目的元素。此时，划分中的部分数目由下述公式给出：第62页/共444页排列与组合例1：确定数34 52 117 138的正整数因子的个数？例2：两位数字有多少两个位互异且非零的两位数？例3：计算口令字计划由0,1,2,9和小写字母a,b,c,z中取出的6个字符构成的一个串组成。具有重复字符的计算机口令共有多少？例4：在1000和9999之间有多少具有不同数字的奇数？例5：在0和10000之间有多少个整数恰好有一位数字是5？第63页/共444页排列与组合n集合的排列S的r排列：令r为正整数，我们把n个元素的集合S的一个r排列定义为
37、n个元素中的r个元素的有序摆放。例如，S=a,b,c，则S的1排列为：abcS的2排列为：abacbabccacbS的3排列为：abcacbbacbcacabcba第64页/共444页排列与组合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)(n-r+1)。证明：在构建n-元素集的一个r排列时，我们可以用n种方法选择第一项，不论第一项如何选出，都可以用n-1种方法选择第二项，以及不论前r-1项如何选出，都可以用n-(r-1)种方法选择第r项。根据乘法原理，这r
38、项可以用n(n-1)(n-r+1)种方法选出。第65页/共444页排列与组合123n第一项有n种方法第二项有n-1种方法12r第r项有n-r+1种方法S第66页/共444页排列与组合例：将08级的24个研究生排列使得ICES中心(9个学生)的任意两个学生都不能相继出现，这种排列的方法总数是多少？例：有多少种方法从08级的24个研究生中取7个人进行排列，并且使得王伟和谢冬辉不能以任何顺序相继出现？第67页/共444页排列与组合n循环排列：例：6个孩子沿圆圈行进，他们能够以多少种不同的方式形成一个圆？1234566123455612344561233456122345611234566123455
39、61234456123345612234561第68页/共444页排列与组合如果两个循环排列通过一个旋转，即一个循环移位，从其中的一个变到另一个，那么可以将它们看成是相同的。这样，在6个孩子的线性排列和6个孩子的循环排列之间就存在着6到1的对应。因此，要想求得循环排列的数目，我们只要用6去除线性排列的数目即可。所以，6个孩子的循环排列数目等于6!/6=5!第69页/共444页排列与组合定理2：n个元素的集合的循环r-排列的个数为特别地，n个元素的循环排列的个数是(n-1)!。证明：可以把线性r-排列的集合划分成一些部分，使得两个线性r-排列对应同一个循环r-排列当且仅当它们在同一个部分中。于是
40、，循环r-排列的个数等于部分的个数。既然每一个部分都含有r个线性r-排列，根据除法原理，部分的数目等于第70页/共444页排列与组合例：ICES中心08级的9个研究生要围坐一个圆桌，其中有两个人不愿意彼此挨着就座，共有多少循环座位排放方法？例：6男6女围坐一个圆桌，如果男女交替围坐，可以有多少围坐方式？第71页/共444页排列与组合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-组合的个数。如果rn
41、，=0；如果r0，=0。nrnr0rn0=1n1=nnn=100=1第72页/共444页排列与组合定理3：对于0rn，因此，证明：令S是一个n-元素集。S的每个r-排列都是由下面的两个任务执行结果产生。1)从S中选出r个元素。2)将所选出的r个元素以某种顺序排列。执行第一个任务的方法数根据定义可知为组合数 。nr第73页/共444页排列与组合执行第二个任务的方法数则是P(r,r)=r!。根据乘法原理我们有所以，第74页/共444页排列与组合定理4：证明：通过对n-元素集S的组合计数来证明。1)S的每一个组合是S对于r(r=0,1,2,n)的一个r-组合。由于nr等于S的r-组合数，由加法原理等
42、于S的所有组合的总个数。第75页/共444页排列与组合2)把一个组合的选取分成n个任务来完成。令S的元素为x1,x2,xn。在选择S的一个组合时，对n个元素的每一个都有两种选择：xi(i=1,2,n)要么在这个组合里；xi(i=1,2,n)要么不在这个组合里。因此，由乘法原理，存在2n种方法使得我们可以形成S的一个组合。使两种方法相等就完成了定理的证明。第76页/共444页排列与组合n多重集排列多重集多重集同一般集合一样，是一组对象的整体，只不过不像一般集合那样必须要求集合中的每个元素互不相同。例如，S=a,a,a,b,c,c,d,d,d,d,d是一个10元素的多重集，其中，有3个a，1个b，
43、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。第77页/共444页排列与组合多重集排列设S=3 a,1 b,2 c,4 d，那么acbc，cbcc为S的4排列，而abaacddcdd是S的一个排列(10排列)。p定理：令S=a1,a2,ak是一个多重集，则S的r-排列的个数为kr。证明：第一项有k种方法第二项有k种方法12r第r项有k种方法Sa1a1a1a2a2
44、a2akakak所以，S的r-排列个数为kr第78页/共444页排列与组合该问题是求S=a,b,z的包含4个元音字母的8-排列数。在长度为8的字符串中，4个元音字母出现的位置的选择方式有 种，而每个元音位置可以取5个元音字母中的任何一个，4个辅音位置可以取21个辅音字母中的任何一个。因此，满足要求的字符串有848454214个。例：用26个英文字母可以构造出多少个包含4个元音字母、长度为8的字符串。第79页/共444页排列与组合例：把r个不同的球放入k个不同的盒子中，每个盒子可以放多个，也可以不放，其方案数为多少？方法1：第一个球有k个盒子可放，第二个球有k个盒子可放，第r个球也有k个盒子可放
45、，由乘法原理知，不同的方案数为kr。方法2：把这r个球分别记作x1,x2,xr，这k个不同的盒子分别记为a1,a2,ak，令S=a1,a2,ak是一个多重集，将球xi放入盒子aj对应于多重集S的r排列，因此，方案数为kr。第80页/共444页排列与组合p定理：令S=n1 a1,n2 a2,nk ak是一个多重集，n=n1+n2+nk，则S的排列数等于证明：12nSa1a1a1n1akakaknk第81页/共444页排列与组合首先决定哪些位置被a1占据。由于S中有n1个a1，必须从n个位置的集合选出n1个位置的子集。有 种方法。然后决定哪些位置被a2占据。由于S中有n2个a2，必须从剩下的n-n
46、1个位置的集合选出n2个位置的子集。有 种方法。最后决定哪些位置被ak占据。由于S中有nk个ak，必须从剩下的n-n1-nk-1个位置的集合选出nk个位置的子集。有 种方法。第82页/共444页排列与组合由乘法原理可知，S的排列的总数等于根据组合数计算公式，这个数等于化简后得到第83页/共444页排列与组合例：将6个篮球、5个红球、4个白球和3个黄球排成一排，要求黄球不挨着，问有多少种排列方式？在构造排列时，先将蓝、红、白三种球进行全排列，再将3个黄球插入其中。令S=6 b,5 r,4 w，则S的排列数为15!/(6!5!4!)。然后在15个空选出3个位置插入黄球，共有 种取法。所以，共有15
47、!/(6!5!4!)种取法。第84页/共444页排列与组合其中，盒子1含有n1个元素，盒子2含有n2个元素，,盒子k含有nk个元素。如果这些盒子不被做成标签，那么划分的个数为 。p定理：令n是一个正整数，并令n1,n2,nk是正整数且n=n1+n2+nk。将n个元素的集合划分成k个被做标签的盒子B1,B2,Bk的方式数为 。a2a2a2anB1B2Bk该问题等价于多重集S=n1 B1,n2 B2,nk Bk的全排列。n1n2nk第85页/共444页排列与组合证明：首先选择n1个元素放入第一个盒子，然后从剩下的n-n1个元素中取n2个元素放入第2个盒子中，然后从剩下的n-n1-n2个元素中取n3
48、个元素放入第3个盒子中,最后从剩下的n-n1-n2-n3-nk-1个盒子中取nk个元素放入第k个盒子中。根据乘法原理，进行这些选择的方法数为：=第86页/共444页排列与组合a1a2a3n例.4元素的集合S=a1,a2,a3,a4，2个盒子B1和B2,B1含有2个元素，盒子B2含有2个元素。a1a2a3a1a2a3a1a2a36 6种划分种划分a4a4a4a4a1a2a3a1a2a3a1a2a3a4a4a4第87页/共444页排列与组合如果盒子不做标签a1a2a3a1a2a3a1a2a3a4a4a43 3种划分种划分第88页/共444页排列与组合a1a2a3n例.3元素的集合S=a1,a2,a
49、3，2个盒子B1和B2,B1含有2个元素，盒子B2含有1个元素。a1a2a3a1a2a3a1a2a3划分划分1 1划分划分2 2划分划分3 3第89页/共444页排列与组合如果盒子不做标签a1a2a3a1a2a3a1a2a3第90页/共444页排列与组合现在设对这些盒子不做标签，此时的结果必须被k!整除。因为对于把元素放入k个无标签的盒子中的每一种方法，现在存在k!种方法将标签1,2,k贴在盒子上。因此，使用除法原理，具有无标签盒子的划分的个数为：p该定理等价于把r个不同的球放入k个不同的盒子中，第1个盒子放r1个球，第2个盒子放r2个球，第k个盒子放rk个球，且r1+r2+rk=r。第91页
50、/共444页排列与组合例：在88棋盘上对于8个非攻击型车有多少可能的方法？我们给棋盘上的每个方块一对坐标(i,j)。整数i指出方块的行数，整数j指出方块的列数。因此，i和j是1和8之间的整数。由于棋盘是88，棋盘上就能有8个车它们不能彼此攻击，每行上必然有一个车。因此，这些车必然占据8个方块而且具有坐标(1,j1),(2,j2),(8,j8)。由于每一列上恰好有一个车，这使得数j1,j2,j8中没有两个是相等的。因此，该问题可以等价于1,2,8的全排列，其总数为8！。第92页/共444页排列与组合例：在88棋盘上对于8个不同颜色的非攻击型车有多少可能的方法？例：假设有1个红(R)车，3个蓝车、