组合数学：1-3 组合意义的解释与应用举例

1、1.3 组合意义的解释与应用举例组合意义的解释与应用举例1. 非降路径问题非降路径问题2. 组合意义的解释组合意义的解释3. 应用举例应用举例从从(0,0)点出发沿点出发沿x轴或轴或y轴的轴的正正方向每步走一个单方向每步走一个单位，最终走到位，最终走到(m,n)点，有多少条路径？点，有多少条路径？y x(m,n). . .01. 非降路径问题非降路径问题因此若记所求方案数为因此若记所求方案数为 P(m+n; m, n)，则，则()!(;, ).! !mnmnmnP mn m nmnm n 无论怎样走法无论怎样走法,总有：在总有：在x方向上总共走方向上总共走m 步，在步，在y方向上总共走方向上总

2、共走n步。步。若用一个若用一个x表示表示x方向上的一步，一个字母方向上的一步，一个字母y表示表示y方方向上的一步，则向上的一步，则(0,0)(m,n)的每一条路径可表示为的每一条路径可表示为m 个相同的个相同的x与与n个相同的个相同的y的一个排列。的一个排列。这相当于从这相当于从m+n个位置中选出个位置中选出m个位置放个位置放x，剩下的，剩下的位置自然放置位置自然放置y。 (c,d)(a,b)( , )(, ).0 0mnm nm 或记为或记为设设ca,db,则由则由(a,b)到到(c,d)的的非降路径数为：非降路径数为：()()( , )( , ).cadba bc dca 对每一条接触对每

3、一条接触x=y 的非降的非降路径，做路径，做(0,1)点到第一个点到第一个接触点部分关于接触点部分关于x=y的对的对称非降路径，这样得到一称非降路径，这样得到一条从条从(1,0)到到(m,n)的非降路的非降路径。径。从从(0,1)点到点到(m,n)点的非降路径，有的接触点的非降路径，有的接触x=y，有，有的不接触。的不接触。在原模型的基础上若设在原模型的基础上若设mm。用一个用一个m+n维的向量来表示一个排队状态，其中每维的向量来表示一个排队状态，其中每个分量只能取个分量只能取x或或y，这里取值，这里取值y表示这个位置的顾表示这个位置的顾客持有客持有50元的钞票，取值元的钞票，取值x表示只有表

4、示只有100元的钞票。元的钞票。因此这等价于一个从因此这等价于一个从(0,0)到到(m,n)点的非降路径，且点的非降路径，且满足满足yx，即可以接触但不能穿过对角线。，即可以接触但不能穿过对角线。因此所求排队方法即为上页讨论的答案结果。因此所求排队方法即为上页讨论的答案结果。()( , ).0nnkn kkxyC n k x y 2. 组合意义的解释组合意义的解释它主要有以下三个重要意义：它主要有以下三个重要意义：(1) 组合意义：组合意义：n元集中元集中k元子集的个数元子集的个数;(2) 显式表示：显式表示：C(n,k)=n(n-1)(n-k+1)/k!;(3) 二项展开式的系数：即有恒等式

5、二项展开式的系数：即有恒等式二项式系数二项式系数 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：从：从

6、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的的不断分类。不断分类。.;12131nnnnrnrnnnnn 解释解释1：可从上个结论推论：可从上个结论推论,也可做一下组合证明。也可做一下组合证明。从从1,n+r+1取取a1a2anan+1,设设a1a2an an+1,可按可按a1的取值分类：的取值分类：a1=1

7、,2,3,r,r+1.若若a1=k, 则则a2an+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,.,.1nnnrnnn .11nnnrnnnnrn 故有故有解释解释2：右边表示从：右边表示从(0,0)到到(n+1,r)的非降路径数。的非降路径数。这些路径一定过且仅过一条带箭头的边。而过这这些路径一定过且仅过一条带箭头的边。而过这些边的路径有些边的路径有(从下到上从下到上)(, );12nrC nrr按不含按不含1,含含1个个1,含含2个个1,含含r个个1分类，分类，其个数相应为

8、其个数相应为,.,.12120nrnrnrnrrr 从从1,n+2中取中取r个的可重组合模型个的可重组合模型,解释解释3：利用可重组合：利用可重组合.其个数为其个数为 两种选法都两种选法都无遗漏无遗漏,无重复无重复地给出可能的方案，应地给出可能的方案，应该相等。该相等。nknnrkrrkr4. ; 左边是从左边是从n个元素中取个元素中取k个组合，再从这个组合，再从这k个取个取r个个的组合数。的组合数。这相当于直接从这相当于直接从n个元素中取个元素中取r个，但是要计算重个，但是要计算重数数C(n-r,k-r)，因为这相当于取定，因为这相当于取定r个后，再从剩下个后，再从剩下n-r个元素中取个元素

9、中取k-r个与之前的个与之前的r个组合。个组合。5. C(m+n,2)-C(m,2)-C(n,2)=mn;等式右边可以看作是等式右边可以看作是m个男生个男生n个女生，一男一女个女生，一男一女的组合数，易知为的组合数，易知为mn。等式左端是从等式左端是从m+n个人中取个人中取2人的组合减去纯从男人的组合减去纯从男生中取生中取2人的组合和纯从女生中取人的组合和纯从女生中取2人的组合，余人的组合，余下的即为一男一女的组合。下的即为一男一女的组合。0()(, )mmkm kkxyC m k x y在在 中令中令x=y=1即得。即得。 左边表示可以有左边表示可以有0-子集子集(空集空集),1-子集子集,

10、m-子集。子集。mC mC mC m m6. (,0)(,1).(,)2 ;解释解释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) + +(-

11、1)mC(m,m)=0；0()(, )mmkm kkxyC m k x y在在 中令中令x=-y=1即得。即得。 在任一含在任一含1组合及与之对应的不含组合及与之对应的不含1组合中，必有一组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集合，将含偶数个元的组合做成另一元的组合做成集合，将含偶数个元的组合做成另一集合。这两个集合的元素个数相等。集合。这两个集合的元素个数相等。在所有组合中，含在所有组合中，含1的组合的组合不含不含1的组合。的组合。.ijnnij 奇奇偶偶P(m-r,r) (m+n-r,r) (m-r+k,r-k)

12、k=0,1,2,r Q(m,0)rkmnmnrrkk0. mnmnmnmnrrrr8.;0110 解释解释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,再将再将换成换成即得。即得。mkmmk mnmnmnmnmmm9.;0011 例例1 从号码从号码1,2,N中每次取出一个并登记，然后放中每次取出一个并登记，然后放回，连取回，连取n次，得到一个

13、由次，得到一个由n个数字组成的数列，问个数字组成的数列，问按这种方式能得到按这种方式能得到(1) 多少个严格递增数列多少个严格递增数列(nN);(2) 多少个不减数列？多少个不减数列？(2) 可重组合可重组合 C(N+n-1,n)。3. 应用举例应用举例(1) 无重组合无重组合 C(N,n)；(1) 每人至少缺把钥匙，且每人所缺钥匙每人至少缺把钥匙，且每人所缺钥匙不同。故至少共有不同。故至少共有C(7,3)=35把不同的钥匙。把不同的钥匙。(2) 任一人对于其他人中的每人任一人对于其他人中的每人,都至少有把都至少有把钥匙与之相配才能开锁钥匙与之相配才能开锁.故每人至少持故每人至少持C(6,3)

14、20把不同的钥匙。把不同的钥匙。例例2 某保密装置须同时使用若干把不同的钥匙才能某保密装置须同时使用若干把不同的钥匙才能打开。现有个人，每人持若干把钥匙。须人到打开。现有个人，每人持若干把钥匙。须人到场，所备钥匙才能开锁。问：场，所备钥匙才能开锁。问：(1) 至少有多少把不同的钥匙？至少有多少把不同的钥匙？(2) 每人至少持几把钥匙？每人至少持几把钥匙？(2) 若能级为若能级为kE0的质点可有的质点可有2(k2 +1)种状态，而且种状态，而且服从服从Fermi-Dirac分布，即不允许同能级的两个质分布，即不允许同能级的两个质点有相同状态点有相同状态,问系统有几种不同状态问系统有几种不同状态?

15、(或图像或图像)例例3 有有4个相同质点个相同质点,总能量为总能量为4E0，E0是常数。每是常数。每个质点所具能量为个质点所具能量为kE0,k=0,1,2,3,4.(1) 若能级为若能级为kE0的质点可有的质点可有k2 +1种状态，而且服从种状态，而且服从Bose-Einstein分布，即同能级的质点可以处于相同分布，即同能级的质点可以处于相同的状态，问系统有几种不同的状态的状态，问系统有几种不同的状态?(或图像或图像)能量分布能量分布 0,0,0,4 0,0,1,3 0,0,2,2 (1) 11117 11210 11C(5,2) (2) C(2,3)34 C(2,2)420 C(2,2)C

16、(10,2)能量分布能量分布0,1,1,2 1,1,1,1 (1) 1C(2,2)5 C(2,4) 72 (2) 2 C(4,2)10 C(4,4) 246 能级能级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 个。但不能每个串都设为个。但不能每个串都设为码字，否则失去纠错能力。码字，否则失去纠错能力。20022.( , )( , )nnrrkkMC n kC n k设设a=a1a2an，b=

17、b1b2bn是是n位数串。则位数串。则a,b的的Hamming距离定义为距离定义为即对应位不同的位的个数。即对应位不同的位的个数。1( , ),niiid a bab Hamming距离满足三角不等式：距离满足三角不等式：( , )( , )( , ).d a cd a bd b c11( , ), ( , ),nniiiiiid a bab d b cbc11( , )nniiiiiiiid a cacabbc11.nniiiiiiabbcar右图表示以右图表示以a为球心为球心,r为半径为半径的的球体中的串都作为球体中的串都作为a处理。处理。由汉明不等式由汉明不等式,只要两个码字只要两个码字

18、a,b满足满足d(a,b)2r+1,则不至于产生一个码字则不至于产生一个码字c，使得它与，使得它与ab的汉明距离的汉明距离都小于都小于r，而无法判定是，而无法判定是a还是还是b的错。的错。纠错处理：能纠正传输过程中产生的纠错处理：能纠正传输过程中产生的r个错是指，个错是指，若规定若规定a是码字，收到是码字，收到a有有d(a,a)r 则将则将a当作当作a处理处理(发生最多发生最多r个错误个错误)每一码字每一码字r邻域内的邻域内的n位二进制数串的数目为：位二进制数串的数目为：于是于是0( , )2rnkMC n k 02.( , )nrkMC n k 因此各码字的因此各码字的r-邻域必须互不相交。邻域必须互不相交。.,012nnnnr202( , ).rnkMC n k 20022.( , )( , )nnrrkkMC n kC n k综合上两式，有综合上两式，有另一方面任一串与最近的码字的距离不大于另一方面任一串与最近的码字的距离不大于2r，否，否则这个串本身可作为一新的码字。则这个串本身可作为一新的码字。这表明在以所有码字为球心以这表明在以所有码字为球心以2r为半径的球中，应为半径的球中，应当使任一串落入某球内。故当使任一串落入某球内。故例例5 凸凸n边形没有边形没有3条对角线交于一点，计算各边及条对角线交于一点，计算各边及各对角