卢开澄组合数学--组合数学第一章PPT课件

-,1,组合数学,清华大学计算机黄连生1999年7月,-,2,前言,组合数学是一个古老而又年轻的数学分支。据传说，大禹在4000多年前就观察到神龟背上的幻方.,-,3,前言,幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。,5,1,9,3,7,2,4,8,6,-,4,前言,贾宪北宋数学家（约11世纪）著有黄帝九章细草、算法斅古集斅音“笑（“古算法导引”）都已失传。杨辉著详解九章算法（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（WilliamGeogeHorner，17861837）的方法（1819年）早770年。,-,5,前言,1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。,-,6,前言,组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。,-,7,前言,本学期主要讲组合分析（计数和枚举）以及组合优化的一部分（线性规划的单纯形解法）。组合分析是组合算法的基础。,-,8,前言,组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。,-,9,第一章排列组合,1.1加法法则与乘法法则,-,10,1.1加法法则与乘法法则,加法法则设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。,集合论语言：若|A|=m,|B|=n,AB=,则|AB|=m+n。,-,11,1.1加法法则与乘法法则,例某班选修企业管理的有18人，不选的有10人，则该班共有18+10=28人。,例北京每天直达上海的客车有5次，客机有3次，则每天由北京直达上海的旅行方式有5+3=8种。,-,12,1.1加法法则与乘法法则,乘法法则设事件A有m种产生式，事件B有n种产生方式，则事件A与B有mn种产生方式。,集合论语言：若|A|=m,|B|=n,AB=(a,b)|aA,bB,则|AB|=mn。,-,13,1.1加法法则与乘法法则,例某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则这种字符串共有53=15个。,例从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6条道路。,-,14,1.1加法法则与乘法法则,例某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是44=16，而只有43=12种。在乘法法则中要注意事件A和事件B的相互独立性。,-,15,1.1加法法则与乘法法则,例1)求小于10000的含1的正整数的个数2)求小于10000的含0的正整数的个数,1)小于10000的不含1的正整数可看做4位数,但0000除外.故有999916560个.含1的有：99996560=3439个,另:全部4位数有10个,不含1的四位数有9个,含1的4位数为两个的差:109=3439个,44,44,-,16,2)“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。,不含0的1位数有9个，2位数有9个，3位数有9个，4位数有9个,不含0小于10000的正整数有9+9+9+9=(91)/(91)=7380个,含0小于10000的正整数有99997380=2619个,2,3,4,2,3,4,5,-,17,1.2排列与组合,定义从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。一般不说可重即无重。可重排列的相应记号为-P(n,r),P(n,r)。,l,-,18,1.2排列与组合,定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)表示，对应于可重组合-有记号C(n,r),C(n,r)。,-,19,1.2排列与组合,从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，第r个有n-r+1种选择。故有P(n,r)=n(n-1)(n-r+1)有时也用nr记n(n-1)(n-r+1),-,20,1.2排列与组合,若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)r!=P(n,r),C(n,r)=P(n,r)/r!=nr/r!=()=易见P(n,r)=n,nr,r,n!r!(n-r)!,-,21,1.2排列与组合,例有5本不同的日文书，7本不同的英文书，10本不同的中文书。1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书,-,22,1.2排列与组合,解1)57+510+710=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=(),5+7+102,-,23,1.2排列与组合,例从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？,解将1,300分成3类：A=i|i1(mod3)=1,4,7,298,B=i|i2(mod3)=2,5,8,299,C=i|i3(mod3)=3,6,9,300.要满足条件，有四种解法：1)3个数同属于A;2)3个数同属于B3)3个数同属于C;4)A,B,C各取一数.,故共有3C(100,3)+100=485100+1000000=1485100,3,-,24,1.2排列与组合,例某车站有6个入口处，每个入口处每次只能进一人，一组9个人进站的方案有多少？,解一进站方案表示成：00011001010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。,-,25,1.2排列与组合,解法1标号可产生5!个14个元的全排列。故若设x为所求方案，则x5!=14!x=14!/5!=726485760,-,26,1.2排列与组合,解法2在14个元的排列中先确定“1”的位置，有C(14,5)种选择，在确定人的位置，有9！种选择。故C(14,5)9!即所求,-,27,1.2排列与组合,解法3把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种。以此类推，9号有14种选择。9故所求方案为6,-,28,1.3Stirling近似公式,组合计数的渐进值问题是组合论的一个研究方向。Stirling公式给出一个求n!的近似公式，它对从事计算和理论分析都是有意义的。,-,29,1.3Stirling近似公式,1)Wallis公式,令Ik=sinxdx.显然I0=,I1=1.k2时，Ik=cosxsinx|+(k1)cosxsinxdx=0+(k1)(1sinx)sinxdx=(k1)(Ik2Ik),k,2,k-1,20,20,20,20,2k-2,2k-2,故Ik=Ik-2(1-3-1),k-1k,-,30,1.3Stirling近似公式,令n!=,135(n-2)n，n是奇数。246(n-2)n，n是偶数。,(1-3-2),由(1-3-1)，I1,k是奇数Ik=I0,k是偶数,(k-1)!k!(k-1)!k!,当x(0,/2)时，sinxsinx因而I2k+1I2kI2k-1,k=1,2,。,k+1k,-,31,1.3Stirling近似公式,由(1-3-2),，,(2k)!(2k-1)!(2k-2)!(2k+1)!(2k)!2(2k-1)!,11.,2,(2k)!(2k-1)!,12k+1,2k+12k,2,k,-,32,1.3Stirling近似公式,所以,lim=,(2k)!(2k-1)!,12k+1,2,2,k,lim=,(2k)!(2k)!(2k)!,12k+1,2,2,k,lim=。(1-10-3),2(k!)(2k)!,12k+1,2,2,k,2k2,-,33,1.3Stirling近似公式,2)stirling公式,yy=lnx0123n-1nx,-,34,1.3Stirling近似公式,令An=lnxdx=xlnx|dx=nlnnn+1(1-3-4)tn=ln1+ln2+ln(n1)+lnn=ln(n!)lnn(1-3-5)tn的几何意义是由x轴,x=n,以及连接(1,0),(2,ln2),(n1,ln(n1),(n,lnn)诸点而成的折线围成的面积。,nnn111,1122,12,-,35,1.3Stirling近似公式,Tn=+ln2+ln(n1)+lnn(1-3-6),1182,Tn是由三部分面积之和构成的。一是曲线y=lnx在x=k点的切线和x轴，以及x=k,x=k包围的梯形，当k分别为2,3,n-1时的面积之和；一是由y=lnx在x=1点的切线，x=3/2线，以及x轴围城的梯形；另一是由y=lnn,x=n,x=n及x轴包围的矩形面积。因而有tnAnTn(1-3-7),12,12,12,-,36,1.3Stirling近似公式,令bn=Antn.序列b1,b2,是单调增，而且有上界，故有极限，令limbn=b1由(1-3-4),(1-3-5)得bn=nlnnn+1ln(n!)+lnn=lnnn+1ln(n!)+lnnln(n!)=1bn+lnnlnnlnen!=en()(1-3-8),0AntnTntn=,18,n,12,n,nn,1-bn,ne,n,-,37,1.3Stirling近似公式,令n=e,limn=.将(1-3-8)代入(1-3-3),整理得=2.所以n!2n(),n,1-bn,ne,n,-,38,1.4模型转换,“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。如我们说A集合有n个元素|A|=n，无非是建立了将A中元与1,n元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换。比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。,-,39,1.4模型转换,例,简单格路问题|(0,0)(m,n)|=()从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？,m+nm,y(m,n).0.x,-,40,1.4模型转换,无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。则(0,0)(m,n)的每一条路径可表示为m个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。,-,41,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+nm+nm!n!mn,(c-a)+(d-b)c-a,(c,d)(a,b),-,42,1.4模型转换,例在上例的基础上若设m1,1,在后缀7521中找出比4大的数,75,找出其中比4大的最小数,5,5,4、5对换,8396721,5,4,后缀变为7421,将此后缀翻转,1247,接上前缀83965得到839651247即839647521的下一个。,例,为后缀,大于4的用橙色表示小于4的用绿色表示,找出比右边数字小的第一个数4,-,63,1.5.1字典序法,在1,n的全排列中,nn-1321是最后一个排列,其中介数是(n-1,n-2,.,3,2,1)其序号为,n-1kk!k=1,另一方面可直接看出其序号为n!-1n-1n-1于是n!-1=kk!即n!=kk!+1k=1k=1,-,64,1.5.1字典序法,一般而言，设P是1,n的一个全排列。,P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1Pnj=maxi|PiPj对换Pj，Pk，将Pj+1Pk-1PjPk+1Pn翻转，P=P1P2Pj-1PkPnPk+1PjPk-1Pj+1即P的下一个,-,65,1.5.1字典序法,2)计算给定排列的序号,839647521的序号即先于此排列的排列的个数。将先于此排列的排列按前缀分类。,前缀先于8的排列的个数：78!,第一位是8,先于83得的排列的个数：27!,前2位是83,先于839得的排列的个数：66!,先于此排列的的排列的个数：,78!,+27!,+66!,前3位是839,先于8396得的排列的个数：45!,+45!,前4位是8396,先于83964得的排列的个数：24!,+24!,前5位是83964,先于839647得的排列的个数：33!,+33!,前6位是839647,先于8396475得的排列的个数：22!,+22!,前7位是8396475,先于83964752得的排列的个数：11!,+11!,297191,前8位固定，则最后一位也随之固定,将8!,7!,1!前面的系数抽出，放在一起得到,72642321,此数的特点：,7：8的右边比8小的数的个数,2：3的右边比3小的数的个数,6：9的右边比9小的数的个数,4：6的右边比6小的数的个数,2：4的右边比4小的数的个数,3：7的右边比7小的数的个数,2：5的右边比5小的数的个数,1：2的右边比2小的数的个数,72642321是计算排列839647521的序号的中间环节，我们称之为中介数。这是一个很有用的概念。,-,66,1.5.1字典序法,一般而言,对于1,9的全排列中介数首位的取值为08，第2位的取值为07，以此类推，第8位的取值为0、1。从而序号可表示为：n-1ki(n-i)!i=1ki：Pi的右边比Pi小的数的个数i=1,2,n-1,-,67,1.5.1字典序法,由中介数推出排列的算法,例由72642321推算出839647521,方法1：,P1P2P3P4P5P6P7P8P9_,P1=8,8,7+1=8,2+1=3,P2=3,3,6+1=7，但3已在P3左边出现，,7+1=8，但8已在P3左边出现，,8+1=9P3=9,9,4+1=5，但3已经在P4左边出现，5+1=6P4=6,6,2+1=3，但3已经在P5左边出现，3+1=4P4=4,4,3+1=4，但3,4已经在P6左边出现，4+1+1=6，但6已经在P6左边出现，6+1=7P6=7,7,2+1=3，但3已经在P7左边出现，3+1=4，但4已经在P7左边出现，4+1=5P7=5,5,1+1=2P8=2P9=1,21,这个过程比较麻烦(这酝酿着改进的可能)，该算法从左到右依次推出P1,P2,P9。下述算法依次定出1,2,3,9的位置。,-,68,1.5.1字典序法,方法2-1：,72642321中未出现0，1在最右边,中介数右端加一个0扩成9位，先定1，每定一位，其左边未定位下加一点，从（位位下点数=0）的位中选最左的。,726423210,定1的位置,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,由72642321推算出839647521,-,69,1.5.1字典序法,方法2-2：,已定出上标，找左起第一个0，下标_,由72642321推算出839647521,72642321-11111111=61531210,_1,2,61531210-11111110=50420100,3,50420100-10000000=40420100,4,40420100-10110000=30310100,5,30310100-10110100=20200000,6,20200000-10100000=10100000,7,10100000-10100000=00000000,8,00000000,9,以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数进位链（中介数的后继）递增进位制数,-,70,1.5.2递增进位制数法,1)由排列求中介数,在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。,在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2n)一致。,-,71,1.5.2递增进位制数法,可看出n-1位的进位链。右端位逢2进1，右起第2位逢3进1，右起第i位逢i+1进1，i=1,2,n-1.这样的中介数我们称为递增进位制数。上面是由中介数求排列。,-,72,1.5.2递增进位制数法,由序号（十进制数）求中介数（递增进位制数）如下：m=m1,0mn!-1m1=2m2+kn-1,0kn-11m2=3m3+kn-2,0kn-22.mn-2=(n-1)mn-1+k2,0k2n-2mn-1=k1,0k1n-1p1p2pn(k1k2kn-1)m,-,73,1.5.2递增进位制数法,在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。,为方便起见，令ai+1=kn-I，i=1,2,n-1(k1k2kn-1)=(anan-1a2)ai：i的右边比i小的数字的个数,-,74,1.5.2递增进位制数法,在这样的定义下，有839647521(67342221)(67342221)+1=(67342300)84961752368+7)7+3)6+4)5+2)4+2)3+2)2+1=279905,-,75,1.5.2递增进位制数法,由(anan-1a2)求p1p2pn。,从大到小求出n,n-1,2,1的位置_._n_an个空格n的右边有an个空格。n-1的右边有an-1个空格。2的右边有a2个空格。最后一个空格就是1的位置。,_/V,-,76,1.5.2递增进位制数法,_,67342221a9a8a7a6a5a4a3a2,_/V6个空格,9,_/V7个空格,8,_/V3个空格,7,6,5,4,3,1,_/V4个空格,_/V2个空格,1个空格,序号nm=ak(k-1)!k=2,2,-,77,1.5.3递减进位制数法,在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。,把递增进位制数翻转,就得到递减进位制数。,(anan-1a2)(a2a3an-1an)839647521(12224376),nnm=akn!/k!=n!ak/k!k=2k=2,(12224376)=13+2)4+2)5+2)6+4)7+3)8+7)9+6=340989求下一个排列十分容易,-,78,1.5.4邻位对换法,递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。,-,79,1.5.4邻位对换法,这个算法可描述如下：对1n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1n的n个排列。对1n-1的每一个奇排列，n从左到右插入n个空档，生成1n的n个排列。对2,n的每个数字都是如此。,-,80,1.5.4邻位对换法,例,839647521836947521,解,2的右边有1个数字(奇数)比2小,2上加一个点。,3的右边有2个数字(偶数)比3小,3上不加点。,4的右边有2个数字(偶数)比4小,4上不加点。,5的右边有2个数字(偶数)比5小,5上不加点。,6的右边有2个数字(偶数)比6小,6上不加点。,7的右边有3个数字(奇数)比7小,7上加一个点。,8的右边有7个数字(奇数)比8小,8上加一个点。,18上共有3个(奇数)点，9上箭头向右。,P=839647521()b2b3b4b5b6b7b8b9,1,0,1,2,1,3,7,2,2上箭头向左，2右边有1个数字比2小，b2=1,3上箭头向右，3左边有0个数字比3小，b3=0,4上箭头向右，4左边有1个数字比4小，b4=1,5上箭头向右，5左边有2个数字比5小，b5=2,6上箭头向右，6左边有1个数字比6小，b6=1,7上箭头向左，7右边有3个数字比7小，b7=3,8上箭头向左，8右边有7个数字比8小，b8=7,9上箭头向右，9左边有2个数字比9小，b9=2,839647521的中介数为10121372,-,81,1.5.4邻位对换法,ak(p)：p中1k排列的序号，ak(p)的奇偶性与1k排列的奇偶性相同。,a9(p)=9a8(p)+b9(p)=9(8a7(p)+b8(p)+b9(p),an(p)，bn(p)简写成an，bn,-,82,1.5.4邻位对换法,已知(10121372)求排列。,9的位置由b9和a8的奇偶性决定。a8的奇偶性同b8的奇偶性。a7的奇偶性同b7+b6的奇偶性。b2=0,1。,b8奇9，b6+b7偶8，b6奇7，b4+b5奇6，b4奇5,-,83,1.5.4邻位对换法,序号=13+0)4+1)5+2)6+1)7+3)8+7)9+2=203393(10121372),-,84,1.5.4邻位对换法,-,85,1.6组合的生成,设从1,n中取r元的组合全体为C(n,r).C1C2CrC(n,r).不妨设C1C2CriCi(nr+i),i=1,2,r令j=maxi|Cinr+i.则C1C2Cr的下一个组合为C1C2Cj-1(Cj+1)(Cj+2)(Cj+rj+1)这等于给C(n,r)的元素建立了字典序。12r的序号为0，n-r+1n-r+2n的序号为()1,_nr,-,86,1.6组合的生成,例在C(10,4)中4679的序号是首位小于4的组合的个数；首位是4，第2位小于6的组合的个数；前2位是46，第3位小于7的组合的个数；前3位是467，第4位小于9的组合的个数之和。反之，也可以由序号求组合。,-,87,1.6组合的生成,A(m,l)：1,m的l-组合(或l-子集)。第1个组合：1,2,l-1,l.最后1个组合：1,2,l-1,mA(n,k)=A(n-1,k)，A(n-1,k-1)nA：将有序集A(或线性表)的顺序逆转的有序集。An：将A中每个元素(是集合)都与n求并的有序集,_,_,_,-,88,1.6组合的生成,例用两种方法计算1,n的无重不相邻组合C(n,r)的计数问题解法100100100100100其中不可含11,/,共n位,r个1,/,以1结尾：r-1个10与n-1-2(r-1)个0的排列r-1+n-1-2(r-1)=n-r这样的排列有,(n-r)!=(r-1)!(n-2r+1)!,(),n-rr-1,-,89,1.6组合的生成,以0结尾：r个10与n-2r个0的排列r+n-2r=n-r这样的排列有()个()+()=()f(a1a2ar)=b1b2br,n-rr,n-rn-rn-r+1r-1rr,-,90,1.6组合的生成,解法任给a1a2arC(n,r),a1a2ar令f：a1a2arb1b2brbi=ai-i+1,i=1,2,r.1b1b2brn-r+1,b1b2brC(n-r+1,r)C(n,r)=C(n-r+1,r),-,91,1.7可重组合,C(n,r)的计数问题相当于r相同的球放入n个互异的盒子，每盒球的数目不同的方案的计数。而后一问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。易知所求计数为=C(n+r-1,r)即C(n,r)=()=C(n-1,r)+C(n,r-1)不含“”至少含一个“”,(n-1+r)!r!(n-1)!,n+r-1r,r个相同的球/001001100/n-1个相同的盒壁,-,92,1.7可重组合,另证设a1a2arC(n,r)1a1a2arn,令C(n,r)上的f，使得bi=ai+i-1,i=1,2,r.则b1b2br满足1b1b2brn+r-1b1b2brC(n+r-1,r)f：a1a2arb1b2br显然f是单射，f：b1b2bra1a2ar,-1,-,93,1.7可重组合,ai=bi-i+1,i=1,2,r.a1a2arC(n,r)f是单射C(n,r)C(n+r-1,r)f是单射C(n,r)C(n+r-1,r)C(n,r)=C(n+r-1,r)第二个证明可说一种“拉伸压缩”技巧。不可谓不巧妙。但仍不如第一证明来的明快，由此可见组合证明的功效。,-1,-,94,1.8若干等式及其组合意义,组合意义或组合证明，含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。,-,95,1.8若干等式及其组合意义,1.C(n,r)=C(n,n-r)(1.7.1)从1,n去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。故C(n,r)=C(n,n-r),-,96,1.8若干等式及其组合意义,2.C(n,r)=C(n-1,r)+C(n-1,r-1)(1.7.2)从1,n取a1,a2,ar.设1a1a2arn,对取法分类：a1=1,有C(n-1,r-1)种方案a11,有C(n-1,r-1)种方案共有C(n-1,r)+C(n-1,r-1)中方案，故C(n,r)=C(n-1,r)+C(n-1,r-1),-,97,1.8若干等式及其组合意义,杨辉三角除了(0,0)点，都满足此递推式0rn,n0rC(n,r)=1,r=00,0nr,r0nn0且r0C(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),(-1)(),|r|-1|n|-1,n+r,nrr!,-,98,1.8若干等式及其组合意义,3.()+()+()+()=()(1.7.3)1可从(7.2)推论，也可做一下组合证明从1,n+r+1取a1a2anan+1，设a1a2anan+1，可按a1的取值分类：a1=1,2,3,r,r+1.a1=1,a2an+1取自2,n+r+1有()种取法,nn+1n+2n+rn+r+1nnnnn,n+rn,a1=2,a2an+1取自3,n+r+1有()种取法,n+r-1n,a1=r,a2an+1取自r+1,n+r+1有()种取法,n+1n,a1=r+1,a2an+1取自r+2,n+r+1有()种取法,nn,也可看做按含1不含1，含2不含2,含r不含r的不断分类,-,99,1.8若干等式及其组合意义,2从(0,0)到(n+1,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上)(),(),()故有.()+()+()+()=(),nn+1n+rnnn,nn+1n+2n+rn+r+1nnnnn,r(n+1,r).(0,0)nn+1,-,100,1.8若干等式及其组合意义,3可重组合.1,n+2的C(n+2,r)模型()不含1,含1个1,含2个1,含r个1C(),C(),C(),C()(),(),(),(),n+r+1r,n+1n+1n+1n+1rr-1r-20,n+rn+r-1n+r-2nrr-1r-20,-,101,1.8若干等式及其组合意义,4.()()=()()(1.7.4)选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委选常委,再选非常委政治局委员两种选法都无遗漏,无重复地给出可能的方案，应该相等。,nlnn-rlrrl-r,-,102,1.8若干等式及其组合意义,5.()+()+()=2,m0,(1.7.5)证1(x+y)=()xy,令x=y=1,得(1.7.5)组合证11,m的所有方案.每一子集都可取k1,m或不取.这样有2个方案.另可有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)各点的走法各有(),(),(),(),(),()种,mmmm01m,mkm-k,mmkk=0,m,m,mmmmmm012m-2m-1m,-,103,1.8若干等式及其组合意义,6.()-()+()-()=0(1.7.6)证1在(x+y)=()xy中令x=1,y=-1即得.,nnnn012n,nn-kk,nk,nk=0,-,104,1.8若干等式及其组合意义,证2在1,n的所有组合中,含1的组合不含1的组合.有11对应关系。在任一含1组合及与之对应的不含1组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集，将含偶数阁元的组合做成另一集。此二集的元数相等。()=(),nnii,i奇i偶,-,105,1.8若干等式及其组合意义,7.()=()()+()()+()()(1.7.7)即Vandermonde恒等式证1从m个互异红球和n个互异蓝球中取r个球,按r个球中红球的个数分类.组合证法:(0,0)到(m+n-r)点的路径.(0,0)(m-r+l,r-l)(m+n-r,r)()()()=()(),m+nmnmnmnr0r1r-1r0,mnr-ll,m+nmnrr-ll,P(m-r,r)(m+n-r,r)(m-r+l,r-l)l=0,1,2,rQ(m,0),rl=0,-,106,1.8若干等式及其组合意义,李善兰(18111882），清代数学家李善兰恒等式：()()()=()(),kln+k+l-jn+kn+ljjk+lkl,j0,证：利用Vandermonde恒等式及()()=()()=()()(接下页),nvnn-pnn-pvppn-vpv-p,-,107,1.8若干等式及其组合意义,有()()()=()()()()=()()()()=()()()()=()()()=()()()=()()()=()(),kln+k+l-jjjk+l,kln+kl-jjjk+vl-v,n+kkll-jk+vjjl-v,n+kklvk+vjvl,n+klk+vk+vvk,n+knlkn-vv,n+knlkn-vv,n+kn+lkl,j0j0vjv0j0v0j0v0v0v0,-,108,1.8若干等式及其组合意义,8.在7.中令r=mn,再将()换成()得()=()()+()()+()(),mmkm-k,m+nmnmnmnm0011mm,-,109,1.9应用举例,例某保密装置须同时使用若干把不同的钥匙才能打开。现有人，每人持若干钥匙。须人到场，所备钥匙才能开锁。问至少有多少把不同的钥匙？每人至少持几把钥匙？解每人至少缺把钥匙，且每人所缺钥匙不同。故至少共有()=35把不同的钥匙。,73,-,110,1.9应用举例,任一人对于其他人中的每人，都至少有把钥匙与之相配才能开锁。故每人至少持()20把不同的钥匙。为加深理解，举一个较简单的例子：人中人到场，所求如上。共有()=6把不同的钥匙。每人有()=3把钥匙。（见下页图）,-,111,1.9应用举例,钥匙A人BCD,-,112,1.9应用举例,例有4个相同质点,总能量为4E0,E0是常数。每个质点所具能量为kE0,k=0,1,2,3,4.A)若能级为kE0的质点可有k+1种状态，而且服从Bose-Einstein分布，即同能级的质点可以处于相同的状态，问系统有几种不同的状态？（或图像）B)若能级为kE0的质点可有2(k+1)种状态，而且服从Fermi-Dirac分布，即不允许同能级的两个质点有相同状态，问系统有几种不同状态？（或图像）,2,2,-,113,1.9应用举例,解,能级k01234A)k+11251017状B)2(k+1)24102034态,2,2,能量分布0,0,0,40,0,1,30,0,2,2A)111171121011C(5,2)B)C(2,3)34C(2,2)420C(2,2)C(10,2)能量分布0,1,1,21,1,1,1A)1C(2,2)5C(2,4)72B)2C(4,2)10C(4,4)246,-,114,1.9应用举例,例,3个相同的质点分布在2个相同的势阱里，这3个质点的总能量为3E0,