组合数学：1-3-组合意义的解释与应用举例省名师优质课赛课获奖课件市赛课一等奖课件

1.3组合意义解释与应用举例

非降路径问题

组合意义解释

应用举例第1页从(0,0)点出发沿x轴或y轴正方向每步走一个单位，最终走到(m,n)点，有多少条路径？y

x(m,n)......01.非降路径问题第2页所以若记所求方案数为P(m+n;m,n)，则不论怎样走法,总有：在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上一步，一个字母y表示y方向上一步，则(0,0)→(m,n)每一条路径可表示为m个相同x与n个相同y一个排列。这相当于从m+n个位置中选出m个位置放x，剩下位置自然放置y。第3页(c,d)(a,b)或记为设c≥a,d≥b,则由(a,b)到(c,d)非降路径数为：第4页对每一条接触x=y非降路径，做(0,1)点到第一个接触点部分关于x=y对称非降路径，这么得到一条从(1,0)到(m,n)非降路径。从(0,1)点到(m,n)点非降路径，有接触x=y，有不接触。在原模型基础上若设m<n，求(0,1)点到(m,n)点不接触对角线x=y非降路径数目(“接触”包含“穿过”)?y

y=x(m,n)0(1,0)x(0,1)..第5页故所求非降路径数为轻易看出从(0,1)到(m,n)接触x=y非降路径与(1,0)到(m,n)非降路径(必穿过x=y)一一对应。第6页所求非降路径数为若条件深入改为可接触但不可穿过，则限制线要向下或向右移一格，得x-y=1,(0,0)关于x-y=1对称点为(1,-1).y

x-y=1(m,n)

x(0,1).........(2,-1)第7页假设一场音乐会票价为50元，排队买票用户中有n位只有50元现金，m位只有100元现金。售票处没有准备50元零钱。试问有多少种排队方法使得购票能顺利进行，即不会出现找不出钱状态。假定每位用户只买一张票，且n>m。用一个m+n维向量来表示一个排队状态，其中每个分量只能取x或y，这里取值y表示这个位置用户持有50元现金，取值x表示只有100元现金。所以这等价于一个从(0,0)到(m,n)点非降路径，且满足y≥x，即能够接触但不能穿过对角线。所以所求排队方法即为上页讨论答案结果。第8页2.组合意义解释它主要有以下三个主要意义：(1)组合意义：n元集中k元子集个数;(2)显式表示：C(n,k)=n(n-1)…(n-k+1)/k!;(3)二项展开式系数：即有恒等式二项式系数C(n,k)是组合数学中无处不在一个角色。第9页1.(对称性)C(n,r)=C(n,n-r)；2.(递推关系)C(n,r)=C(n-1,r)+C(n-1,r-1)；从[1,n]去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)一个一一对应。共有C(n-1,r)+C(n-1,r-1)种方案。a1=1,有C(n-1,r-1)种方案；a1>1,有C(n-1,r)种方案。解释1：从[1,n]取a1,a2,…,ar。设1≤a1＜a2＜…＜ar≤n,对取法分类：{(0,0)→(m,n)}={(0,0)→(m,n-1)}∪{(0,0)→(m-1,n)}解释2：利用非降路径C(m+n,m)=C(m+n-1,m)+C(m+n-1,m-1)第10页也可看做按含1不含1，含2不含2,…,含r不含r不停分类。解释1：可从上个结论推论,也可做一下组合证实。从[1,n+r+1]取a1a2…anan+1,设a1＜a2＜…＜an＜an+1,可按a1取值分类：a1=1,2,3,…r,r+1.若a1=k,则a2…an+1取自[k+1,n+r+1]，有C(n+r+1-k,n)种取法。这里k从1变到r+1。第11页r(n+1,r)

...(0,0)n

n+1故有解释2：右边表示从(0,0)到(n+1,r)非降路径数。这些路径一定过且仅过一条带箭头边。而过这些边路径有(从下到上)第12页按不含1,含1个1,含2个1,…,含r个1分类，其个数对应为从[1,…,n+2]中取r个可重组合模型,解释3：利用可重组合. 其个数为第13页两种选法都无遗漏,无重复地给出可能方案，应该相等。左边是从n个元素中取k个组合，再从这k个取r个组合数。这相当于直接从n个元素中取r个，不过要计算重数C(n-r,k-r)，因为这相当于取定r个后，再从剩下n-r个元素中取k-r个与之前r个组合。第14页5.C(m+n,2)-C(m,2)-C(n,2)=mn;等式右边能够看作是m个男生n个女生，一男一女组合数，易知为mn。等式左端是从m+n个人中取2人组合减去纯从男生中取2人组合和纯从女生中取2人组合，余下即为一男一女组合。第15页在中令x=y=1即得。左边表示能够有0-子集(空集),1-子集,…,m-子集。解释1：右边即m个元素全部选取方案，每一子集都可取或不取。这么有2m种方案。解释2：从(0,0)走m步有2m种走法，都落在直线x+y=m上。而到(m,0),(m-1,1),(m-2,2),…,(2,m-2),(1,m-1),(0,m)各点走法各有C(m,0),C(m,1),C(m,2),…,C(m,m-2),C(m,m-1),C(m,m)种。第16页7.C(m,0)-C(m,1)+…+(-1)mC(m,m)=0；在中令x=-y=1即得。在任一含1组合及与之对应不含1组合中，必有一奇数个元组合与一偶数个元组合。将含奇数个元组合做成集合，将含偶数个元组合做成另一集合。这两个集合元素个数相等。 在全部组合中，含1组合←→不含1组合。第17页P(m-r,r)(m+n-r,r)(m-r+k,r-k)k=0,1,2,…,r

Q(m,0)解释1：从m个互异红球和n个互异蓝球中取r个球，按r个球中红球个数分类。解释2：(0,0)到(m+n-r,r)点路径：C(m,r-k)C(n,k)(0,0)→(m-r+k,r-k)→(m+n-r,r)第18页在8.中令r=m≤n,再将换成即得。第19页例1从号码1,2,…N中每次取出一个并登记，然后放回，连取n次，得到一个由n个数字组成数列，问按这种方式能得到(1)多少个严格递增数列(n≤N);(2)多少个不减数列？(2)可重组合C(N+n-1,n)。3.应用举例无重组合C(N,n)；第20页(1)每３人最少缺１把钥匙，且每３人所缺钥匙不一样。故最少共有C(7,3)=35把不一样钥匙。(2)任一人对于其它６人中每３人,都最少有１把钥匙与之相配才能开锁.故每人最少持C(6,3)＝20把不一样钥匙。例2某保密装置须同时使用若干把不一样钥匙才能打开。现有７个人，每人持若干把钥匙。须４人到场，所备钥匙才能开锁。问：(1)最少有多少把不一样钥匙？(2)每人最少持几把钥匙？第21页(2)若能级为kE0质点可有2(k2+1)种状态，而且服从Fermi-Dirac分布，即不允许同能级两个质点有相同状态,问系统有几个不一样状态?(或图像)例3有4个相同质点,总能量为4E0，E0是常数。每个质点所具能量为kE0,k=0,1,2,3,4.(1)若能级为kE0质点可有k2+1种状态，而且服从Bose-Einstein分布，即同能级质点能够处于相同状态，问系统有几个不一样状态?(或图像)第22页能量分布0,0,0,40,0,1,30,0,2,2(1)1·1·1·171·1·2·101·1·C(5,2)(2)C(2,3)·34C(2,2)·4·20C(2,2)·C(10,2)能量分布0,1,1,21,1,1,1(1)1·C(2,2)·5C(2,4)72(2)2·C(4,2)·10C(4,4)246———能级k01234(1)k2+11251017(2)2(k2+1)24102034状态数第23页例4设n位长能纠r个错码字个数为M，则n位长0-1字符串共有2n个。但不能每个串都设为码字，不然失去纠错能力。设a=a1a2…an，b=b1b2…bn是n位数串。则a,bHamming距离定义为即对应位不一样位个数。第24页Hamming距离满足三角不等式：第25页ar右图表示以a为球心,r为半径球体中串都作为a处理。由汉明不等式,只要两个码字a,b满足d(a,b)≥2r+1,则不至于产生一个码字c，使得它与ab汉明距离都小于r，而无法判定是a还是b错。纠错处理：能纠正传输过程中产生r个错是指，若要求a是码字，收到a'有d(a,a')≤r 则将a'看成a处理(发生最多r个错误)第26页每一码字r邻域内n位二进制数串数目为：于是所以各码字r-邻域必须互不相交。第27页综合上两式，有另首先任一串与最近码字距离小于2r，不然这个串本身可作为一新码字。这表明在以全部码字为球心以2r为半径球中，应该使任一串落入某球内。故第28页例5凸