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

《组合数学：1-3-组合意义的解释与应用举例.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.3组合意义的解释与应用举例非降路径问题组合意义的解释应用举例从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？yx(m,n)......01.非降路径问题因此若记所求方案数为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

2、,则由(a,b)到(c,d)的非降路径数为：对每一条接触x=y的非降路径，做(0,1)点到第一个接触点部分关于x=y的对称非降路径，这样得到一条从(1,0)到(m,n)的非降路径。从(0,1)点到(m,n)点的非降路径，有的接触x=y，有的不接触。在原模型的基础上若设m

3、为若条件进一步改为可接触但不可穿过，则限制线要向下或向右移一格，得x-y=1,(0,0)关于x-y=1的对称点为(1,-1).yx-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元的钞票

4、。因此这等价于一个从(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

5、(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)也可看做按含1不含1，含2不含2,…,含r不含r的不断分类。解释1：可从上个结论推论,也可做一下组合证明。从[1,n+r+

6、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。r(n+1,r)...(0,0)nn+1故有解释2：右边表示从(0,0)到(n+1,r)的非降路径数。这些路径一定过且仅过一条带箭头的边。而过这些边的路径有(从下到上)按不含1,含1个1,含2个1,…,含r个1分类，其个数相应为从[1,…,n+2]中取r个的可重组合模型,解释3：利用可重组合.其个数为两种选法都无遗漏,无重复

7、地给出可能的方案，应该相等。左边是从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：右边即

8、m个元素的所有选取方案，每一子集都可取或不取。这样有2m种方案。解释2：从(0,0)走m步有2m种走法，都落在直线x+y=