第四组合数学.pptx

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,组合数学,河北工业大学计算机学院 李建伟,lijianwei,组合数学是一门研究离散对象的科学，是计算机的核心课程之一，在众多的计算机系统软件和信息安全软件中都要用到本课程的内容。它是近代密码学和算法的理论基础，在计算机科学的理论体系中占有极其重要的位置。对计算机专业本科的学生进行组合数学教学和训练，为进一步学习计算机算法（组合算法）打下坚实基础。,组合数学是为学习,”,算法与复杂性分析,”,作理论的准备。,本课程的学习目的,通过本课程的学习，理解组合理论的基本概念，掌握组合理论的基本方法和技巧，了解一些简单算法，为深入研究、应用组合数学打好基础。,前言,组合数学是一个古老而又年轻的数学分支。,据传说，大禹在4000多年前就观察到神龟背上的幻方,.,前言,幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。,5,1,9,3,7,2,4,8,6,前言,贾宪,北宋数学家（约11世纪）著有黄帝九章细草、算法斅古集斅 音“笑（“古算法导引”）都已失传。杨辉著详解九章算法（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（,William Geoge Horner，1786,1837）,的方法（1819年）早,770年。,前言,1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（,Combinatorics）,一词。,前言,组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照,。,前言,本学期主要讲组合分析（计数和枚举）以及组合优化的一部分（线性规划的单纯形解法）。,组合分析是组合算法的基础。,前言,组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。,但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。,第一章排列组合,1.1,加法法则与乘法法则,加法法则 设事件,A,有,m,种产生方式，,事件,B,有,n,种产生方式，则事件,A,或,B,之一,有,m+n,种产生方式。,集合论语言：,若|,A|=m,|B|=n,A,B=,则|,AB|=m+n。,1.1,加法法则与乘法法则,例 某班选修企业管理的有 18 人，不选,的有 10 人，则该班共有 18+10=28 人。,例 北京每天直达上海的客车有 5 次，客机有 3 次，则每天由北京直达上海的旅行方式有 5+3=8 种。,1.1,加法法则与乘法法则,乘法法则 设事件,A,有,m,种产生式，事件,B,有,n,种产生方式，则事件,A,与,B,有,m n,种产生方式。,集合论语言：,若|,A|=m,|B|=n,A,B=(a,b)|a A,b B,则|,A B|=m,n。,1.1,加法法则与乘法法则,例 某种字符串由两个字符组成，第一个字符可选自,a，b，c，d，e，,第二个字符可选自1，2，3，则这种字符串共有5,3=15 个。,例 从,A,到,B,有三条道路，从,B,到,C,有两条道路，则从,A,经,B,到,C,有3,2=6 条道路。,1.1,加法法则与乘法法则,例,某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有4,2 =8种着色方案。,若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是4 4=16，而只有 4 3=12 种。,在乘法法则中要注意事件,A,和 事件,B,的相互独立性。,1.1,加法法则与乘法法则,例,1)求小于10000的含1的正整数的个数,2)求小于10000的含0的正整数的个数,1)小于10000的不含1的正整数可看做4位数,但0000除外。,故有999916560个.,含1的有：99996560=3439个,另:全部4位数有10 个,不含1的四位数有9 个,含1的4位数为两个的差:10 9=3439个,4 4,4 4,2),“含0”和“含1”不可直接套用。,0019,含1但不含0,。,在组合的习题中有许多类似的,隐含,的,规定，要特别留神。,不含0的1位数有,9,个，2位数有,9,个，,3位数有,9,个，4位数有,9,个,不含0小于10000的正整数有,9+9 +9 +9 =(9 1)/(91)=7380个,含0小于10000的正整数有,99997380=2619个,2,3,4,2,3,4,5,排列,定义,从,n,个不同的元素中，取,r,个不重复的元素，,按次序排列,，,称为从,n,个中取,r,个的,无重排列,。排列的全体组成的集合用,P(n,r),表示。排列的个数用,P(n,r),表示。当,r=n,时称为,全排列,。一般不说可重即无重。可重排列的相应记号为,-,P(n,r),P(n,r),。,排列,排列研究事物的有序安排或有序选择数。,例如：,125,和,251,虽然都由,1,，,2,，,5,三个数字构成，但这是两个不同的排列。,分为：,线排列,（简单排列，我们高中所学的排列）,圆排列,（排列的首尾元素相连）,重排列,（排列中的元素可以重复）,组合,定义从,n,个不同元素中取,r,个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从,n,个中取,r,个的,无重组合,。,组合的全体组成的集合用,C(n,r),表示，组合的个数用,C(n,r),表示，对应于可重组合,-,有记号,C,(n,r),C(n,r),。,组合,组合研究事物的无序安排或无序选择数。,例如：,125,和,251,都由,1,，,2,，,5,三个数字构成，被看成是同一个组合。,1.1排列与组合,从,n,个中取,r,个的排列的典型例子是从,n,个不同的球中,取出,r,个,放入,r,个不同的盒子里,每盒1个。第1个盒子有,n,种选择，第2个有,n-1,种选择，,，第,r,个有,n-r+1,种选择。,故有,P(n,r)=n(n-1),(n-r+1),有时也用,n,r,记,n(n-1),(n-r+1),排列计数定理,P(n,r)=n(n-1),(n-r+1),=,n!,(n-r)!,1.1排列与组合,若球不同，盒子相同，则是从,n,个中取,r,个的,组合,的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有,r!,个标号方案。,故有,C(n,r),r!=P(n,r),C(n,r),=P(n,r)/r!=n,r,/r!=,(,),=,易见,P(n,r)=n,n,r,r,n!,r!(n-r)!,排列与组合,例,有5本不同的日文书，7本不同的英文书，10本不同的中文书。,1)取2本不同文字的书；,2)取2本相同文字的书；,3)任取两本书,排列与组合,5+7+10,2,解,1)57+510+710=155;,2),C(5,2)+C(7,2)+C(10,2),=10+21+45=76;,3)155+76=231=(),排列与组合,从,n,个中取,r,个的圆排列的排列数为,P(n,r)/r,2,r,n,以4个元素为例,1,2 4,3,1234,1,2 4,3,2341,1,2 4,3,3412,1,2 4,3,4123,排列与组合,从,n,个中取,r,个的项链排列的排列数为,P(n,r)/2r,3,r,n,项链排列就是说排列的方法和项链一样,在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。,例,下面两种方式实际上表示的都是3个元素的同一种排列。,1,1,2 3 3 2,排列与组合,例,从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？,解,将1,300分成3类：,A=i|i1(mod 3)=1,4,7,298,B=i|i2(mod 3)=2,5,8,299,C=i|i3(mod 3)=3,6,9,300.,要满足条件，有四种解法：,1)3个数同属于,A;2)3,个数同属于,B,3)3,个数同属于,C;4)A,B,C,各取一数。,故共有3,C(100,3)+100,3,=485100+1000000=1485100,1.2一一对应,“,一一对应,”,概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。,如我们说,A,集合有,n,个元素|,A|=n，,无非是建立了将,A,中元与1,n,元一一对应的关系。,在组合计数时往往借助于一一对应实现模型转换,。,比如要对,A,集合计数，但直接计数有困难，于是可设法构造一易于计数的,B,，,使得,A,与,B,一一对应。,1.,2,模型转换,例,简单格路问题|(0,0)(,m,n)|=(),从(0,0)点出发沿,x,轴或,y,轴的正方向每步,走一个单位，最终走到(,m,n),点，有多少,条路径？,m+n,m,y,(m,n),.,.,.,0 .x,1.,2,模型转换,无论怎样走法，在,x,方向上总共走,m,步，在,y,方向上总共走,n,步。若用一个,x,表示,x,方向上的一步，一个字母,y,表示,y,方向上的一步。,则(0,0)(,m,n),的每一条路径可表示为,m,个,x,与,n,个,y,的一个,有重排列,。将每一个有重排列的,x,与,y,分别编号，可得,m!n!,个,m+n,元的,无重全排列,。,有重排列的计算方法,求,r,1,个1，,r,2,个2，,，,r,t,个,t,的排列数，设,r,1,+r,2,+,+r,t,=n,设此排列数为,P(n;r,1,r,2,r,t,),对1，2，,，,t,分别加下标，得到,P(n,；,r,1,r,2,r,t,),r,1,!,r,2,!,r,t,!=n!,P(n；r,1,r,2,r,t,)=,=(),n!,r,1,!r,2,!r,t,!,n,r,1,r,2,r,t,1.4模型转换,设所求方案数为,p(m+n,；,m,，,n),则,P(m+n,；m，n),m!,n!=(m+n)!,故,P(m+n;m,n)=,=()=()=C(m+n,m),设,ca,db,则由(,a,b),到(,c,d),的简单格路数为|(,a,b)(c,d)|=(),(,m+n)!m+n m+n,m!n!m n,(,c-a)+(d-b),c-a,(,c,d),(a,b),1.,2,模型转换,例,在上例的基础上若设,mn,，,求(0,1)点到(,m,n),点不接触对角线,x=y,的格路的数目 (“接触”包括“穿过”),从(0,1)点到(,m,n),点的格路，有的接触,x=y,，有的不接触。,对每一条接触,x=y,的格路，做(0,1)点到第一个接触点部分关于,x=y,的对称格路，这样得到一条从(1,0)到(,m,n),的格路,。,1.,2,模型转换,容易看出从(0,1)到(,m,n),接触,x=y,的格路与(1,0)到(,m,n),的格路(必穿过,x=y),一一对应,y,y=x,(m,n),0 (1,0)x,(0,1),.,.,y,x-y=1,(m,n),x,(0,0),(1,-1),.,.,.,1.2一一对应,例,C,n,H,2n+2,是碳氢化合物,随着,n,的不同有下列不同的枝链：,H,|,H,C,H,|,H,H,|,H,C,H,|,H,C,H,|,H,H,|,H,C,H,|,H,C,H,|,H,C,H,|,H,n=1,甲烷,n=2,乙烷,n=3,丙烷,1.2一一对应,H,|,H,C,H,|,H,C,H,|,H,C,H,|,H,C,H,|,H,H,|H,H,C,H,|,H,C,C,H,|,H,C,H,|H,H,n=4,丁烷,n=4,异丁烷,这说明对应,CnH2n+2,的,枝链是有3,n+2,个顶点的一棵树，其中,n,个顶点与之关联的边数为4；其它2,n+2,个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物,CnH2n+2,.,（化学性质有微小的别）。,树的模型和碳氢化合物模型，两个模型是一一对应的。,1.2一一对应,例,在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？,解,一种常见的思路是按轮计场，共需要,99,次比较可以决出冠军是谁。但该方法较为费事，用程序实现较为麻烦。但该方法同时可以知道亚军、四强、八强等是谁，可这些不是题目所要求的任务，题目只要求求出冠军是谁即可。,另一种思路是任选两名选手进行比赛，胜者留下，败者淘汰，同样需要99场比赛，决出冠军。但该方法比第一种方法要容易实现。但不能知道亚军等信息。,两者是一一对应的求冠军的模型。但第二种模型更容易实现。,1.2一一对应,例,(,Cayley,定理),n,个有标号的顶点的树的数目等于,n,。,n-2,生长点不是叶子,每个生长点是1,n,中的,任一元.有,n,种选择。两个顶点的树是唯一的。,所以共有,n,。,详见课本的证明（采用一一对应模型证明）。,一一对应的模型证明该定理成立，则该定理在,原模型上也是成立的。,课本,；,例1.11,n-2,1.2一一对应,|,4,1 2 5 3,逐个摘去标号最小的叶子，叶子的相邻,顶点(不是叶子，是内点)形成一个序列，,序列的长度为,n-2,例,给定一棵有标号的树,边上的标号表示摘去叶,的顺序。(,摘去一个叶子,相应去掉一条边,),第一次摘掉，为相邻的顶点，,得到序列的第一个数3,以此类推，得到序列,31551,长度为72=5,这是由树形成序列的过程。,76,|,2*154,(1),a,1,=2,b,1,=3,(2),7 6,|,3*,54,a,2,=3,b,2,=1,(3),7 6,|,1,4*,a,3,=4,b,3,=5,7 6*,|,1,(4),a,4,=6,b,4,=5,由树得到序列,b,的过程:,(5),7,|,5*,a,5,=5,b,5,=1,(6),7,|,1,结果为,b=(3,1,5,5,1),反之，由序列,b=(3,1,5,5,1),恢复树的过程为,(1),(1,2*,3,4,5,6,7),(,1,5,5,1),可,a,1,=2,b,1,=3.,得分别删去,a,1,和,b,1,得:,(2),(1,3*,4,5,6,7),(,5,5,1),可,a,2,=3,b,2,=1.,得分别删去,a,2,和,b,2,得:,(3),(1,4*,5,6,7),(,5,1),可,a,3,=4,b,3,=5.,得分别删去,a,3,和,b,3,得:,(4),(1,5,6*,7),(,1),可,a,4,=6,b,4,=5.,得分别删去,a,4,和,b,4,得:,(5),(1,5*,7),(,),可,a,5,=5,b,5,=1.,得分别删去,a,5,和,b,5,得:,(6),(1,7),故(1,7)是树枝。,即树由下列树枝构成：,(2,3),(3,1),(4,5),(6,5),(5,1),(1,7)可以容易的恢复这棵树。,此例可描述为：假定,T,是一棵树，树叶中标号最小者设为,a,1，,a,1,的邻接点为,b,1。,消去点,a,1,和边(,a,1,b,1,),点,b,1,变成为余下的树的树叶，在余下的树中继续寻找标号最小的树叶，设为,a,2,，a,2,以边(,a,2,b,2,)相连接，再消去,a,2,及(,a,2,b,2,).继续以上的步骤,n-2,次，直到最后剩下的一条边为止。于是一棵树对应一个序列,b,1,b,2,b,n-2,b,1,b,2,b,n-2,是1到,n,中的数，且并不一定不相同。,反之，任给一个序列,b,1,b,2,b,n-2,（1）,其中1,b,i,n,i=1,2,n-2,便可找到与之对应的树,T，,方法如下：,从序列,1,2,n （2）,中找到第一个不出现在,b,1,b,2,b,n-2,中的树，这个数显然就是,a,1,，,同时找到树,T,的边(,a,1,b,1,)。从序列1和序列2中分别删去,b,1,，,a,1。,在余下的序列中继续以上的步骤,n-2,次，直到序列1空为止。这是序列2剩下的两个数设为,a,k,b,k,.,边(,a,k,b,k,)也是树,T,的最后一条边，于是得到树,T。,这就证明了,n,个标号顶点的树和,n-2,个数,b,1,b,2,b,n-2,一一对应，其中1,b,i,n,i=1,2,n-2。,根据乘法法则，序列1的数目为,n,n-2,1.6,全排列,的生成算法,就是对于给定的组合模型,，用有效的方法将该模型中所有可能的,全排列,无重复无遗漏,地枚举出来。（这是组合数学的一个研究内容）。根据全排列的模型设计相关的生成算法,。,全排列的生成算法,计数与枚举,排列的个数,P(n,r),（有,r,个无区别的盒子，把,n,个带有标号的球，依次放到,r,个盒子中，每个盒子放一个球，每种取法就是,n,个球中取,r,个球的一种排列）,组合的个数,C(n,r),（有,r,个无区别的盒子，把,n,个带有标号的球，依次放到,r,个盒子中，每个盒子放一个球，取出球时不考虑取球的次序，取出的,r,个球如果相同，就认为是同一种取法，每种取法就是,n,个球中取,r,个球的一种组合。）,组合数学中求符合满足某种条件的排列或组合数是一种任务，把满足某条件的所有排列和组合（通常很多）都枚举出来又是组合数学的一种任务。,全排列的枚举,n,个元素的全排列为,P(n,n),，其个数为,n!,个。下面讲解方法就是通过程序把,n!,个排列枚举出来。,1.6,全排列的生成（枚举）算法,这里介绍全排列算法三种：,(,A),序数法,(,B),字典序法,(,C),换位法,1.6.1序数法,常用的十进制表示法：,n,=,a,k,10,k,0,a,k,9,下面给出另一种整数表示法：,n,!=(,n,-1)(,n,-1)!+,(,n,-1)!,(,n,-1)!=(,n,-2)(,n,-2)!+,(,n,-2)!,，递推下去。,n,!=(,n,-1)(,n,-1)!+(,n,-2)(,n,-2)!+(,n,-3)(,n,-3)!+,+,2*2!+,2!,n,!=(,n,-1)(,n,-1)!+(,n,-2)(,n,-2)!+(,n,-3)(,n,-3)!+,2*2!+,1!+1,=,k,*,k,!+,1,即,n,!-1,=,k,*,k,!,可以证明，从0到,n,!-1,（共,n!,个数）的任何整数,m,可,唯一,的表示为：,m=a,n-,1,(,n-,1)!,+a,n-,2,(,n-,2)!,+a,1,*,1!,其中,0,a,i,i,i=,1,2,n-,1,.,从0到,n,!-1,的,n,!,个整数与,(,a,n-,1,a,n-,2,a,1,),一一对应。,(,典型的一一对应的模型,),反之，从,m,算出,a,n-,1,a,n-,2,a,1,。,数,m,除以2的商为,1.6.1 序数法,那么，我们得到,m,除以2的余数为,a,1,。,(,为什么？,m,除以2，可以看作是除以2！),同理，把除,2,后的商再用3除（可以看作是除以,3,！)，余数为,a,2,，依此类推。,n,m,n,i,1,n,i,/(,i,1)，,r,i,n,i,(,i,+1),n,i,1,=,a,i,即,n,i,1,为,n,i,对,i,1,作整数除法得到的商，而,r,i,为相应的余数。显然有：,1.6.1 序数法,a,1,r,1,，,a,2,r,2,，,即,a,i,r,i,，,i,1，2，,，,n,1。,例,m,4000，,即,n,4000,n,2,n,1,/2 2000，,r,1,0,n,3,n,2,/3 666，,r,2,2,n,4,n,3,/4 166，,r,3,2,n,5,n,4,/5 33，,r,4,1,n,6,n,5,/6 5，,r,5,3,n,6,n,6,/7 0，,r,6,5,1.6.1 序数法,所以40005,6,！3,5,！4！2,3,！2,2,！,综上所述，可见满足条件,0=,a,i,=,i,，1=,i,=,n,1,的序列,(,a,n,1,，,a,n,2,，,a,n,3,，,，,a,2,，,a,1,),共有,n,！,个，正好和从0到,n,！1,之间的正整数一一对应。下面试图将,n1,个元素的序列,(,a,n,1,，,a,n,2,，,a,n,3,，,，,a,2,，,a,1,),与,n,个元素的排列建立起一一对应关系（即一一映射函数关系），从而从序列得到一种生成排列的算法。,1.6.1 序数法,n,个元素的全排列和序数,(,a,n,1,，,a,n,2,，,a,n,3,，,，,a,2,，,a,1,),建立起一一对应关系,。,令序列(,a,n,1,，,a,n,2,，,a,n,3,，,，,a,2,，,a,1,),对应,n,个元素全排列的某一排,p=p,1,p,2,p,n,，,其中,排列,p,中，,p,i+1,的值为数,i+1,所在位置的右边比,i+1,小的数的个数，依此类推。,参见课本,P16,的例子,序数法小结,因此，如果想枚举出,n,个元素的全排列，共有,n!,个排列，现在无需列举出来，而是把与之对应的,n!,个序列枚举出来即可，而枚举该序列比枚举,n!,个,n,个元素的排列要更容易用计算机编写程序实现。这即是序数方法列举,n,个元素的全排列。,1.6.2字典序法,对给定的字符集中的字符规定了一个先后关系,(,按照字典的排序,),，在此基础上规定两个全排列的先后是,从左到右,逐个比较对应的字符的先后。,一般是从左到右，从小到大进行枚举。,全排列的生成转换为全排列字符串的按字典序排列,。,全排列的生成算法,1.6.2字典序法,例字符集1,2,3,较小的数字较先,这样按字典序生成的全排列是:,123,132,213,231,312,321。,一个全排列可看做一个字符串，字,符串可有,前缀,、,后缀,。,1.6.2字典序法,1）,直接生成给定全排列的下一个排列,所谓,一个的下一个,就是,这一个,与,下一个,之间,没有其他的排列,。这就要求这一个与下一个有尽可能,长,的,共同前缀,，也即变化限制在尽可能,短,的,后缀,上。,1.6.2字典序法,例 839647521是1,9,的排列。1,9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到,了,987654321，也就没有下一个了。否则找出第一次出现下降的位置,。,字典序法,求83964,7521,的下一个排列,7 5 2 1,7,4,7,42,2,41,1,在后缀7521中找出比4大的数,7 5,找出其中比,4,大的最小数,5,5,4,、,5,对换,8396,7 21,5,4,后缀变为,7421,将此后缀翻转,12 4 7,接上前缀83965得到,839651247,即839647521的下一个。,例,在后边找出比,4,大的最小的数和,4,交换。,即,5,和,4,交换，然后把,1,，,2,，,4,，,7,按递增排序。,从右边开始查找，找出比右边数字小的第一个数,4,1.6.2字典序法,把前面的例子一般化后为，,设,P,是,1,n,的一个全排列,：,P=P,1,P,2,P,n,=P,1,P,2,P,i-1,P,i,P,i+1,P,j-1,P,j,P,j+1,P,n,(a)i=maxj|P,j-1,P,j,/,找出比右边数字小的第一个数,4,(b)j=maxk|P,i-1,1,有,C(n-1,r),种方案,共有,C(n-1,r)+C(n-1,r-1),中方案，故,C(n,r)=C(n-1,r)+C(n-1,r-1),举例,例如,1,，,2,，,3,，,4,，,5,取,3,各组合得：,123,，,124,，,125,，,134,，,135,，,145,，,234,，,235,，,245,，,345,（,即,C(5,3)=10,个,）,其中：,123,，,124,，,125,，,134,，,135,，,145,可以看成是由,2,，,3,，,4,，,5,取两个组合然后加上,1,得到的（,即,C(4,2)=6,个,），而,234,，,235,，,245,，,345,可以看成是由,2,，,3,，,4,，,5,四个元素中取三个元素得到的。（,即,C(4,3)=4,个,）,C(5,3)=,C(4,2)+C(4,3),1.9若干等式及其组合意义,C(m+n,m)=,C(m+n-1,m),+,C(m+n-1,m-1,),(0,0)(m,n)=(0,0)(m,n-1)(0,0)(m-1,n),组合意义：从（,0,0,）点到（,m,n,）的路径数,=,（,0,0,）点到（,m,n-1,）的路径数,+,（,0,0,）点到（,m-1,n,）的路径数,1.9若干等式及其组合意义,（4）,(,)+()+()+,+()=(),证明方法1,从,1,n+r+1,取,a,1,a,2,a,r-1,a,r,，,设,a,1,a,2,a,r,可按是否含有,a,i,的分类：,a,i,=1,2,3,r.,不含,a,1,则,a,2,a,r,取自,2,n+r+1,有()种取法,n n+1 n+2 n+r,n+r+1,0 1 2 r,r,n+r,r,也可看做按含1不含1，含2不含2,含,r,不含,r,的不断分类，也可以得到式,（4）,含有,a,1,，,但不包含,a,2,，,相当于从除去元素,a,1,，,a,2,后的,n+r-1,个元素,3,n+r+1,中取,r-1,个元素的组合，然后再加上元素,a,1,而成。即,(),有,a,1,a,2,a,r-1,无,a,r,第,r,个取自,r+1,n+r+1,有()种取法,n+1,1,由,a,1,a,2,a,r,组成，有(),=1,种取法,n,0,n+r-1,r-1,1.9若干等式及其组合意义,方法2从(0,0)到(,n+1,r),的路径数,任何一条路径过且仅过一条带箭头的边,而过这些边的路径有(从下到上),(),(),(),有.,(,)+()+()+,+()=(),n,n+1,n+r,0 1 r,n n+1 n+2 n+r n+r+1,0 1 2 r r,r (n+1,r),.,.,.,(0,0)n n+1,1.9若干等式及其组合意义,方法3,可重组合（可重组合定理）,1,n+2,的,C(n+2,r),模型,(),不含1,含1个1,含2个1,含,r,-1,个1,含,r,个1,(),(),(),(),n+r+1,r,n+r,n,+,r-1,n+r-2,n,r r-1 r-2 0,举例,从,1,，,2,，,3,中取,4,个做允许重复的组合,令,a1=1,则有,不出现,1,的有：,2222,，,2223,，,2233,，,2333,，,3333,出现,1,个,1,的有：,1222,，,1223,，,1233,，,1333,出现,2,个,1,的有：,1122,，,1123,，,1133,，,出现,3,个,1,的有：,1112,，,1113,出现,4,个,1,的有：,1111,等式（,4,）的另一种表达形式,(,)+()+()+,+()=(),n n+1 n+2 n+r n+r+1,n n n n n,作业：仿照等式（,4,）的证明，分三种方法证明该等式或说明该等式意义。,1.9若干等式及其组合意义,(5),()()=()(),选政治局,再选常委,n,个中央委员选出,L,名政治局委员,再从其中选出,r,名常委。,选常委,再选非常委的政治局委员。,两种选法都,无遗漏,无重复,地给出可能的方案，即,n,个中央委员中有几种政治局委员和政治局常委的组合，应该相等。,n L n n-r,L r r L-r,1.9若干等式及其组合意义,C(m+n,2)-C(m,2)-C(n,2)=mn,m,个男生和,n,个女生，一男一女的组合为,mn,中方案,等式左端为从,m+n,个人中取,2,个组合，减去两个男生的组合和两个女生的组合，余下的为一男一女的组合。,1.9若干等式及其组合意义,(,7),()+()+,+()=2,m,0,证1,(,x+y),=,(,)x,y,令,x=y=1,得(6),组合证1,1,m,的所有状态.每一元素都可取,k1,m,或不取,k,.,这样有2 个方案.左端说明所有状态可分解为,m,个元素中分别取,0,个，,1,个，,，,m,个组合的总和。,组合证2,从(0,0)走,m,步，有2,种走法,每步两种走法,，,都落在直线,x+y=m,上,而到(,m,0),(m-1,1),(m-2,2),(2,m-2),(1,m-1),(0,m),各点的走法各有(,),(,),(,),(,),(,),()种,m m m m,0 1 m,m k m-k,m,m,k,k=0,m,m,m m m m m m,0 1 2 m-2 m-1 m,1.9若干等式及其组合意义,(8),()-()+()-,()=0,证1,在(,x+y)=,()x y,中令,x=1,y=-1,即得.,n n n n,0 1 2 n,n n-k k,n,k,n,k=0,1.9若干等式及其组合意义,证2,在1,n,的所有组合中,含,a,的组合不含,a,的组合，有1,1对应关系。在任一含,a,组合及与之对应的不含,a,组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集，将含偶数个元的组合做成另一集。此二集的元数相等。,举例,以,4,个元素为例，设,4,个元素为,a,b,c,d,。,r,为奇数的组合个数为：,a,、,b,、,c,、,d,、,a,b,c,、,a,b,d,、,a,c,d,、,b,c,d,r,为偶数的组合个数为：,、,a,b,、,a,c,、,a,d,、,b,c,、,b,d,、,c,d,、,a,b,c,d,1.9若干等式及其组合意义,(9),(),=,()(),+,()(),+,+,()(),即,Vandermonde,恒等式,证1,从,m,个互异红球和,n,个互异蓝球中取,r,个球,按,r,个球中红球的个数分类.,组合证法,:(0,0)到(,m+n-r,r,),点的路径.(0,0)(,m-l,l)(m+n-r,r),路径数,()(),()=()(),m+n m n m n m n,r 0 r 1 r-1 r 0,m,路径数,n,l r-l,m+n m n,r l r-l,P(m-r,r)(m+n-r,r),(m-l,l)l=0,1,2,r,Q(m,0),r,l=0,1.9若干等式及其组合意义,(10),在(,9),中令,r=m,n,再将,(),等价换成,(),得,()=()()+()()+,+()(),m m,k m-k,m+n m n m n m n,m 0 0 1 1 m m,等式的组合意义,参见课本的,P45,组合意义,只说明一一对应关系。,P46,的例,1.29,1.10应用举例,例,某保密装置须同时使用若干把不同的钥匙才能打开。现有人，每人持若干钥匙。,须人到场,，所备钥匙才能开锁。问至少有多少把不同的钥匙？每人至少持几把钥匙？,解,每人至少缺把钥匙，且每人所缺钥匙不同。故至少共有,()=,35把不同的钥匙。,7,3,1.10应用举例,任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁。故每人至少持()20把不同的钥匙。,为加深理解，举一个较简单的例子：人中人到场，所求如上。共需要有()=6把不同的钥匙。每人有()=3把钥匙。（见下页图）,1.10应用举例,钥 匙,A ,人,B ,C ,D ,1.10应用举例,例,有4个相同质点,总能量为4,E,0,E,0,是常数。每个质点所具能量为,kE,0,k=0,1,2,3,4.,A),若能级为,kE,0,的质点可有,k+1,种状态，而且服从,Bose,-Einstein,分布，即同能级的质点,可以,处于相同的状态，问系统有几种不同的状态？（或图像）,(,可重排列,),B),若能级为,kE,0,的质点可有2(,k+1),种状态，而且服从,Fermi-Dirac,分布，即,不允许,同能级的两个质点有相同状态，问系统有几种不同状态？（或图像）,(,不可重排列,),2,2,1.10应用举例,解,能级,k 0 1 2 3 4,A)k+1 1 2 5 10 17,状,B)2(k+1)2 4 10 20 34,态,2,2,能量分布 0,0,0,4,0,0,1,3,0,0,2,2,A)11117 11210 11C(5,2),B)420 C(10,2),能量分布0,1,1,2 1,1,1,1,A)1C(2,2)5 C(2,4)72,B)2*C(4,2)*10 C(4,4)246,可重组合，把,4,个相同的球，放入两个不同的盒子中，每盒子允许多放球,C,（,2+4-1,，,4,）,1.10应用举例,3个相同的质点分布在2个相同的势,阱里，这3个质点的总能量为3,E,0,每个质,点的能级为,kE,0,k=0,1,2,3.,能级为,kE,0,的,质点有2(,k+1),种状态，服从,Fermi-Dirac,分布即同一势阱中的质点,不可,处于同一,状态，问系统有几种状态？,2,1.10应用举例,0,0|3 0|0,3 0,1|2 0|1,2 1|0,2,1120 2220 2410 80 80,=20 =80 =80,1,1|1,111|,0,0,3|0,1,2|,C(4,2)4 ()1120 2410,=24 =4 =20 =80,4,3,202+805+24+4=468,解,：,例,1.33,从（,0,，,0,）点出发到（,m,，,n,）点，其中,mn,，要求中间所经过的路径上的点,(a,b),恒满足,ab,，问有多少条路径？,N=,从（,0,，,0,）点出发到（,m,，,n,）点的路径数,-,从（,1,，,0,）点出发到（,m,，,n,）点的路径数,例,1.34,音乐会买票,利用了模型转换的技术,N=,从（,0,，,0,）点出发到（,m,，,n,）点的路径数,-,从（,1,，,-1,）点出发到（,m,，,n,）点的路径数,N=C(m+n,m)-C(m-1)+(n-(-1),m-1),=C(m+n,m)-C(m+n,m-1),作业,P63,第一章习题,1.11,、,1.12,、,1.13,、,1.14,、,1.16,1.37,、,1.38,、,1.39,1.45,、,1.47,、,1.50,、,1.56,、,1.57,