组合意义的解释与应用举例.ppt

1.3 组合意义的解释与应用举例,非降路径问题 组合意义的解释 应用举例,从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？,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。,或记为,设ca,db,则由(a,b)到(c,d)的非降路径数为：,对每一条接触x=y 的非降路径，做(0,1)点到第一个 接触点部分关于x=y的对称非降路径，这样得到一 条从(1,0)到(m,n)的非降路径。,从(0,1)点到(m,n)点的非降路径，有的接触x=y，有 的不接触。,在原模型的基础上若设mn，求(0,1)点到(m,n)点不接触对角线x=y的非降路径的数目 (“接触”包括“穿过”)?,故所求非降路径数为,容易看出从(0,1)到(m,n)接触x=y的非降路径与(1,0)到(m,n)的非降路径(必穿过x=y)一一对应。,所求非降路径数为,若条件进一步改为可接触但不可穿过，则限制线要向下或向右移一格，得x-y=1, (0,0)关于x-y=1的对称点为(1,-1).,假设一场音乐会的票价为50元，排队买票的顾客中有n位只有50元的钞票，m位只有100元的钞票。售票处没有准备50元的零钱。试问有多少种排队的方法使得购票能顺利进行，即不会出现找不出钱的状态。假定每位顾客只买一张票，且nm。,用一个m+n维的向量来表示一个排队状态，其中每个分量只能取x或y，这里取值y表示这个位置的顾客持有50元的钞票，取值x表示只有100元的钞票。,因此这等价于一个从(0,0)到(m,n)点的非降路径，且满足yx，即可以接触但不能穿过对角线。,因此所求排队方法即为上页讨论的答案结果。,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)种方案。,a1=1,有C(n-1,r-1)种方案； a11,有C(n-1,r)种方案。,解释1：从1,n取a1,a2,ar。设1a1a2arn,对取法分类：,(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取a1a2anan+1,设a1a2an an+1,可按a1的取值分类：a1=1,2,3,r,r+1.,若a1=k, 则a2an+1取自k+1,n+r+1，有C(n+r+1-k,n)种取法。这里k从1变到r+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个元素的所有选取方案，每一子集都可取或不取。这样有 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)种。,7. C(m,0) -C(m,1) + +(-1)mC(m,m)=0；,在 中令x=-y=1即得。,在任一含1组合及与之对应的不含1组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集合，将含偶数个元的组合做成另一集合。这两个集合的元素个数相等。,在所有组合中，含1的组合不含1的组合。,解释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),例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) 若能级为kE0的质点可有2(k2 +1)种状态，而且服从Fermi-Dirac分布，即不允许同能级的两个质点有相同状态,问系统有几种不同状态?(或图像),例3 有4个相同质点,总能量为4E0，E0是常数。每个质点所具能量为kE0,k=0,1,2,3,4.,(1) 若能级为kE0的质点可有k2 +1种状态，而且服从Bose-Einstein分布，即同能级的质点可以处于相同的状态，问系统有几种不同的状态?(或图像),能级k 0 1 2 3 4 (1) k2+1 1 2 5 10 17 (2) 2(k2+1) 2 4 10 20 34 状态数,例4 设n位长能纠r个错的码字的个数为M，则,n位长的0-1字符串共有2n 个。但不能每个串都设为码字，否则失去纠错能力。,设a=a1a2an，b=b1b2bn是n位数串。则a,b的Hamming距离定义为,即对应位不同的位的个数。,Hamming距离满足三角不等式：,右图表示以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个错误),每一码字r邻域内的n位二进制数串的数目为：,于是,因此各码字的r-邻域必须互不相交。,综合上两式，有,另一方面任一串与最近的码字的距离不大于2r，否则这个串本身可作为一新的码字。,这表明在以所有码字为球心以2r为半径的球中，应当使任一串落入某球内。故,例5 凸n边形没有3条对角线交于一点，计算各边及各对角线所组成的互不重叠的多边形区域的个数。,首先可以如下计算：,另一方面，每两条对角线决定一个内部多边形的顶点，因此内部的各多边形