组合意义的解释与应用举例.ppt
《组合意义的解释与应用举例.ppt》由会员分享,可在线阅读,更多相关《组合意义的解释与应用举例.ppt(31页珍藏版)》请在三一文库上搜索。
1、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=
2、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).,假
3、设一场音乐会的票价为50元,排队买票的顾客中有n位只有50元的钞票,m位只有100元的钞票。售票处没有准备50元的零钱。试问有多少种排队的方法使得购票能顺利进行,即不会出现找不出钱的状态。假定每位顾客只买一张票,且nm。,用一个m+n维的向量来表示一个排队状态,其中每个分量只能取x或y,这里取值y表示这个位置的顾客持有50元的钞票,取值x表示只有100元的钞票。,因此这等价于一个从(0,0)到(m,n)点的非降路径,且满足yx,即可以接触但不能穿过对角线。,因此所求排队方法即为上页讨论的答案结果。,2. 组合意义的解释,它主要有以下三个重要意义:,(1) 组合意义:n元集中k元子集的个数;,(
4、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,对取法分类:,(
5、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)的非降路径数。,这些路径一定过且仅过一条带箭头的边
6、。而过这些边的路径有(从下到上),按不含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人的组合减去纯从男生中
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 意义 解释 应用 举例
链接地址:https://www.31doc.com/p-3393788.html