组合意义的解释与应用举例教学文案.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.3,组合意义的解释与应用举例,非降路径问题,组合意义的解释,应用举例,从(0,0)点出发沿,x,轴或,y,轴的,正,方向每步走一个单位，最终走到(,m,n,)点，有多少条路径？,y,x,(,m,n,),.,.,.,.,0,1.,非降路径问题,因此若记所求方案数为,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,。,(,c,d,),(,a,b,),或记为,设,c,a,d,b,则由(,a,b,)到(,c,d,)的非降路径数为：,故所求非降路径数为,容易看出从(0,1)到(,m,n,)接触,x=y,的非降路径与(1,0)到(,m,n,)的非降路径(必穿过,x=y,),一一对应,。,所求非降路径数为,若条件进一步改为可接触但不可穿过，则限制线要向下或向右移一格，得,x-y,=1,(0,0)关于,x-y,=1的对称点为(1,-1).,y,x-y,=1,(,m,n,),x,(0,1),.,.,.,.,.,(2,-1),假设一场音乐会的票价为50元，排队买票的顾客中有,n,位只有50元的钞票，,m,位只有100元的钞票。售票处没有准备50元的零钱。试问有多少种排队的方法使得购票能顺利进行，即不会出现找不出钱的状态。假定每位顾客只买一张票，且,n,m,。,用一个,m,+,n,维的向量来表示一个排队状态，其中每个分量只能取,x,或,y,，这里取值,y,表示这个位置的顾客持有50元的钞票，取值,x,表示只有100元的钞票。,因此这等价于一个从(0,0)到(,m,n,)点的非降路径，且满足,y,x,，即可以接触但不能穿过对角线。,因此所求排队方法即为上页讨论的答案结果。,2.,组合意义的解释,它主要有以下三个重要意义：,(1)组合意义：,n,元集中,k,元子集的个数;,(2)显式表示：,C,(,n,k,)=,n,(,n,-1)(,n-k,+1)/,k,!;,(3)二项展开式的系数：即有恒等式,二项式系数,C,(,n,k,)是组合数学中无处不在的一个角色。,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)种方案。,a,1,=1,有,C,(,n,-1,r,-1)种方案；,a,1,1,有,C,(,n,-1,r,)种方案。,解释1：从1,n,取,a,1,a,2,a,r,。设,1,a,1,a,2,a,r,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),也可看做按含1不含1，含2不含2,含,r,不含,r,的不断分类。,解释1：可从上个结论推论,也可做一下组合证明。从,1,n+r,+1取,a,1,a,2,a,n,a,n,+1,设,a,1,a,2,a,n,a,n,+1,可按,a,1,的取值分类：,a,1,=1,2,3,r,r,+1.,若,a,1,=,k,则,a,2,a,n,+1,取自,k,+1,n,+,r,+1，有,C,(,n,+,r,+1,-k,n,)种取法。这里,k,从1变到,r,+1。,r,(,n,+1,r,),.,.,.,(0,0),n,n,+1,故有,解释2：右边表示从(0,0)到(,n,+1,r,)的非降路径数。,这些路径一定过且仅过一条带箭头的边。而过这些边的路径有(从下到上),按不含1,含1个1,含2个1,含,r,个1分类，,其个数相应为,从1,n,+2中取,r,个的可重组合模型,解释3：利用可重组合.,其个数为,两种选法都,无遗漏,无重复,地给出可能的方案，应该相等。,左边是从,n,个元素中取,k,个组合，再从这,k,个取,r,个的组合数。,这相当于直接从,n,个元素中取,r,个，但是要计算重数,C,(,n-r,k-r,)，因为这相当于取定,r,个后，再从剩下,n-r,个元素中取,k-r,个与之前的,r,个组合。,5.,C,(,m+n,2)-,C,(,m,2)-,C,(,n,2)=,mn,;,等式右边可以看作是,m,个男生,n,个女生，一男一女,的组合数，易知为,mn,。,等式左端是从,m+n,个人中取2人的组合减去纯从男生中取2人的组合和纯从女生中取2人的组合，余下的即为一男一女的组合。,在 中令,x,=,y,=1即得。,左边表示可以有0-子集(空集),1-子集,m,-子集。,解释1：,右边即,m,个元素的所有选取方案，每一子集都可取或不取。,这样有 2,m,种方案。,解释2：从(0,0)走,m,步有2,m,种走法，都落在直线,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,)种。,7.,C,(,m,0)-,C,(,m,1)+,+(-1),m,C,(,m,m,)=0；,在 中令,x,=-,y,=1即得。,在任一含1组合及与之对应的不含1组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集合，将含偶数个元的组合做成另一集合。这两个集合的元素个数相等。,在所有组合中，含1的组合不含1的组合。,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,),在8.中令,r=mn,再将,换成,即得。,例1,从号码1,2,N,中每次取出一个并登记，然后放回，连取,n,次，得到一个由,n,个数字组成的数列，问按这种方式能得到,(1)多少个严格递增数列(,nN,);,(2)多少个不减数列？,(2)可重组合,C,(,N+n-,1,n,)。,3.,应用举例,无重组合,C,(,N,n,),；,(1)每人至少缺把钥匙，且每人所缺钥匙,不同。故至少共有,C,(7,3)=35把不同的钥匙。,(2)任一人对于其他人中的每人,都至少有把,钥匙与之相配才能开锁.故每人至少持,C,(6,3)20,把不同的钥匙。,例2,某保密装置须同时使用若干把不同的钥匙才能打开。现有个人，每人持若干把钥匙。须人到场，所备钥匙才能开锁。问：,(1)至少有多少把不同的钥匙？,(2)每人至少持几把钥匙？,(2)若能级为,kE,0,的质点可有2(,k,2,+1)种状态，而且服从Fermi-Dirac分布，即不允许同能级的两个质点有相同状态,问系统有几种不同状态?(或图像),例3,有4个相同质点,总能量为4,E,0,，,E,0,是常数。每个质点所具能量为,kE,0,k,=0,1,2,3,4.,(1)若能级为,kE,0,的质点可有,k,2,+1种状态，而且服从Bose-Einstein分布，即同能级的质点可以处于相同的状态，问系统有几种不同的状态?(或图像),能量分布 0,0,0,4 0,0,1,3 0,0,2,2,(1)11117 11210 11,C,(5,2),(2),C,(2,3)34,C,(2,2)420,C,(2,2),C,(10,2),能量分布0,1,1,2 1,1,1,1,(1)1,C,(2,2)5,C,(2,4)72,(2)2,C,(4,2)10,C,(4,4)246,能级,k,0 1 2 3 4,(1),k,2,[phone],(2)2(,k,2,[phone] 状态数,例4,设,n,位长能纠,r,个错的码字的个数为,M,，则,n,位长的0-1字符串共有2,n,个。但不能每个串都设为码字，否则失去纠错能力。,设,a,=,a,1,a,2,a,n,，,b,=,b,1,b,2,b,n,是,n,位数串。则,a,b,的,Hamming距离定义为,即对应位不同的位的个数。,Hamming距离满足三角不等式：,a,r,右图表示以,a,为球心,r,为半径的,球体中的串都作为,a,处理。,由汉明不等式,只要两个码字,a,b,满足,d,(,a,b,)2,r,+1,则不至于产生一个码字,c,，使得它与,ab,的汉明距离,都小于,r,，而无法判定是,a,还是,b,的错。,纠错处理：能纠正传输过程中产生的,r,个错是指，,若规定,a,是码字，收到,a,有,d,(,a,a,),r,则将,a,当作,a,处理(发生最多,r,个错误),每一码字,r,邻域内的,n,位二进制数串的数目为：,于是,因此各码字的,r,-邻域必须互不相交。,综合上两式，有,另一方面任一串与最近的码字的距离不大于2,r,，否则这个串本身可作为一新的码字。,这表明在以所有码字为球心以2,r,为半径的球中，应当使任一串落入某球内。故,例5,凸,n,边形没有3条对角线交于一点，计算各边及各对角线所组成的互不重叠的多边形区域的个数。,首先可以如下计算：,另一方面，每两条对角线决定一个内部多边形的顶点，因此内部的各多边形区域顶点总数应该是4,C,(,n,4)(每个内部顶点在(1)式中重复计算4次，因为总是4个区域共一个顶点)：,令,N,k,为区域中,k,边形的个数。,从两种角度计算各区域的顶点数(包含重复计)。,而凸多边形的每个顶点重复计数,n,-2次，故,首先，它显然是,再从两个角度来计算所有区域的内角的总和。,其次可以按各顶点对内角和的贡献来计算内角总和为：,因此所有多边形区域的总和为：,