版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1《图论与组合优化》第三讲
可重组合与组合恒等式一.可重组合与可重排列允许重复的组合---多重集的组合多重集—元素可以多次出现的集合,即元素可以重复。我们把某个元素ai出现的次数ni(ni=0,1,2,…)叫做该元素的重复数,通常把含有k种不同元素的多重集S记作4允许重复的组合----可重组合允许重复(可重)的组合是指从
中取r个元素
,
允许重复,即允许
的数同时出现于一个组合中的组合,其全体记为C(n,r),其个数记为C(n,r)定理1.2从
中取r个作可重的组合,其个数为C(n+r-1,r)5设a1a2…ar∈C(n,r)
1≤a1≤a2≤…≤
ai
≤…≤ar≤n,与下面的数列对应相加0<1<2<…<i-1<…<r-1即bi=ai+i-1,i=1,2,…,r.则b1b2…br满足1≤b1<b2<…<br≤n+r-1
b1b2…br∈C(n+r-1,r)f:a1a2…ar→b1b2…br显然f是双射所以C(n,r)=C(n+r-1,r)-定理1.2证明-6定理1.2证明C(n,r)的计数问题相当于r相同的球放入n个互异的盒子,每个盒子中球数不加限制的方案的计数。而后一问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。易知所求计数为=C(n+r-1,r)(n-1+r)!————r!(n-1)!
r个相同的球
/\———————
————————/\0…010…01…10…0
\/————————
\/
n-1个相同的盒壁7允许重复的组合----可重组合定理1.2从
中取r个作可重的组合,其个数为C(n+r-1,r)可重组合的应用例:线性方程有多少个非负解?解:等同于把100个没有区别的球,放入n个不同的盒子,100个1n-1个盒子壁方程解的个数是解:等同于线性方程有多少个正整数解例:给三个孩子发12个一样的水果,每个孩子至少有一个水果,有多少种不同的分发?令
等同于线性方程有多少个非负解方程解的个数是例:11
不相邻的组合
不相邻的组合是指从序列{1,2,…,n}中取r个,不允许重复且不存在i,i+1两个相邻的数同时出现于一个组合中的组合定理1.4
从A={1,2,…,n}中取r个作不相邻的组合,其个数为C(n-r+1,r)12任给a1a2…ar∈C’(n,r),
a1<
a2<
…<
ar≤n且
ai+1-ai≥2,i=1,2,…,r-1与下面的数列对应相减0<1<2<…<i-1<…<r-1得1≤b1<
b2<
…<
br
≤
n-r+1,其中
bi=ai-i+1,i=1,2,…,rbi+1-bi≥1.b1b2…br∈C(n-r+1,r)令f:a1a2…ar→b1b2…br
C’(n,r)=C(n-r+1,r)定理1.4的证明13
可重排列定义从一个多重集中有序选取的r个元素叫做S的一个r-(可重)排列。当时也叫做S的一个排列.14定理:设多重集则的r-(可重)排列数是rk15例求4位数的二进制数的个数解:所求的标志数是多重集{2红旗,3黄旗}的排列数,故N=5!/(2!*3!)=10例用两面红旗,三面黄旗依次悬挂在一根旗杆上,问可以组成多少种不同的标志?16格路模型
如图,求从(0,0)点到(m,n)点、沿格子线走的最短路径数N。
一条到达点(m,n)的路径对应一个由m个x,n个y组成的排列xxxyyxyxxyyxxyyxxxy18二.若干组合等式(1)C(n,r)=C(n,n-r)
(2)C(n,k)=C(n-1,k)+C(n-1,k-1)
证明1:从{1,2,…,n}中取k个组合的全体可以分为两组:
A1组:含有元素n,|A1|=C(n-1,k-1)A2组:不含元素n,|A2|=C(n-1,k)19(2)C(n,k)=C(n-1,k)+C(n-1,k-1)
证明2:考虑如图棋盘从(0,0)到(k,n-k)的最短路条数为C(n,k),其中经过P1点的有C(n-1,k),经过P2点的有C(n-1,k-1)。20(2)C(n,k)=C(n-1,k)+C(n-1,k-1)
证明3:杨辉三角形21(2)C(n,r)=C(n-1,r)+C(n-1,r-1)
(3)C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2)+…+C(n+1,1)+C(n,0).证明1:由(2)可得。22(3)C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+r-2,r-2)+…+C(n+1,1)+C(n,0).证明2:从{1,2,…,n+r+1}中取r个组合的全体可以分为r+1组:A1:不含1,|A1|=C(n+r,r)A2:含1但不含2,|A2|=C(n+r-1,r-1)A3:含1,2,但不含3,|A3|=C(n+r-2,r-2)………Ar:含1,2,…,r-1,但不含r,|Ar|=C(n+1,1)Ar+1:由12…r组成的组合,|Ar+1|=C(n,0)23(4)C(n,k)C(k,r)=C(n,r)C(n-r,k-r),(k≥r).证明:考虑如下问题,把Nn={1,2,…,n}分为甲、乙、丙三组,使得甲组恰有r个,乙组恰有k-r个,丙组恰有n-k个,其分法种数可以用两种方法计算。方法1:从Nn中取k个,余下的n-k个放在丙组;再从取出的k个中拨出r个分在甲组,余下的k-r个分在乙组,分法种数有C(n,k)C(k,r)。方法2:从Nn中取r个分在甲组,再从余下的n-r个中取出k-r个分在乙组,最后剩下的n-k个分在丙组,分法种数有C(n,r)C(n-r,k-r)。24(5)C(m,0)+C(m,1)+…+C(m,m)=2m.
(6)C(n,0)-C(n,1)+C(n,2)-…C(n,n)=0.(x+y)m=xm+C(m,1)xm-1y+C(m,2)xm-2y2+…+ym(x-y)m=xm+C(m,1)xm-1(-y)+C(m,2)xm-2(-y)2+…+(-y)m=xm-C(m,1)xm-1y+C(m,2)xm-2y2+…+(-1)mym25(7)C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+…+C(m,r)C(n,0),r≤min(m,n).26(7)C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+…+C(m,r)C(n,0),r≤min(m,n).甲乙丙丁1
1
2
233
4
4
55
6629三.与路径有关的问题例1
设某地的街道把城市分割成矩形方格,每个方格称为块.某甲从家里出发上班,向东要走m块,向北要走n块.问某甲上班的路径有多少种?(0,0)(m,n)图4.1某甲上班路径数等于从原点到(m,n)点的总路径数:30例2
从(0,0)点到达(m,n)点,其中m<n.要求中间所经过的路径上的点(a,b)恒满足a<b,问有多少不同的路径?(0,0)
(m,n)
图4.2(1,0)(0,1)解
与例1不同,现在要求路径不经过y=x上的点.这样,从(0,0)点第1步必须到(0,1)点,而不允许到(1,0)点.
31问题也可以提为:求从(0,1)点到(m,n)点并且所经过的点(a,b)均满足条件a<b的路径数.由于m<n,显然从(1,0)点到(m,n)点的每一条路径,必然穿过y=x上的点.从(0,0)到(m,n)的路径可以分成两类:
第一类:经过(1,0)点.这类路径至少要穿过一次y=x上的点.
第二类:经过(0,1)点.这类路径可以分成两部分.
32第一部分:
不经过y=x上任何的点.这正是题目中要求的路径.第二部分:
至少经过一次y=x上的点.下面我们说明:第一类路径数目正好等于第二类中第二部分的路径数目.这可以通过建立起从(1,0)到(m,n)点的路径与从(0,1)到(m,n)点但经过y=x线上点的路径间之间一一对应关系来加以证明.
33设从(1,0)到(m,n)点的某一路径与y=x的交点从左到右依次为P1,P2,…,Pk.可以如下构造出(0,1)到(m,n)的一条路径,而且经过y=x上的点同样的点P1,P2,
….,Pk.构造方法:
把该路径(0,0)到Pk点之间部分的路径对y=x取对称.如图:绿线是过(1,0)的一条路径,红线是通过对y=x取对称所得的从(0,0)
经过(0,1)并经过y=x上的点同样的点P1,P2,
…,Pk的路径.34(0,0)(1,0)(0,1)(m,n)P1P2Pk图4.235这样建立了从(1,0)点到(m,n)点的一条路径与从(0,1)到(m,n)点且过y=x上点的路径之间的一一对应关系.利用以上结论,可以用两种方式得到题目中要求的路径数目N:N=从(0,0)点到(m,n)点的总路径数
-2×从(1,0)点到(m,n)点的路径数
N=C(m+n,m)-2C(m+n-1,m-1)=C(m+n-1,m)-C(m+n-1,m-1).36(2)
N=从(0,1)点到(m,n)点的路径数
-从(1,0)点到(m,n)点的路径数
N=C(m+n-1,m)-C(m+n-1,m-1).37例3音乐会票价为50元一张,排队买票的顾客中有n位持50元的钞票,m位持100元的钞票.售票处没有50元的零钱.问有多少种排队的办法使购票能顺利进行,不出现找不出钱的状态,假定每位顾客只买一张票,而且m≥n.分析:
可以用m+n维0,1向量来表示一种排队状态,令该向量为:(a1,a2,…,am+n),
其中ai=0或1,i=1,2,…,m+n.
ai=0表示第i个顾客持50元的票款;
ai=1表示第i个顾客持100元的票款.38这样的向量有n个0元素,m个1元素,共有C(m+n,m)个.可以建立(m+n)维0,1向量与从(0,0)点到达(m,n)点路径间一一对应:从(0,0)点出发,第i步:若ai=0沿x轴方向走一个单位,若ai=1沿y轴方向走一个单位,i=1,…,m+n.要保证顾客能顺利地买到票相当于要求路径上各点(x,y)必须满足y≥x.
39我们的问题相当于求从(0,0)点到(m,n)点的路径中,不穿越过y=x线上点的路径数(可以经过),
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 孔乙己学习课件
- 第17课《昆明的雨》八年级语文上册精讲同步课堂(统编版)
- 爱车讲堂 课件
- 西南林业大学《材料化学》2022-2023学年第一学期期末试卷
- 西南林业大学《地理信息系统原理》2023-2024学年第一学期期末试卷
- 应对挫折课件
- 西京学院《机械制造工艺》2023-2024学年第一学期期末试卷
- 幼儿园小班儿歌《铃儿响叮当》课件
- 西京学院《电机学》2021-2022学年期末试卷
- 医保课件 模板
- 2023年8月26日事业单位联考C类《职业能力倾向测验》试题
- 2023年天津公务员已出天津公务员考试真题
- 施工现场临水施工方案
- 2022年公务员多省联考《申论》真题(四川县乡卷)及答案解析
- 艾滋病职业防护培训
- 2025年高考数学专项题型点拨训练之初等数论
- 上海市浦东新区2024-2025学年六年级上学期11月期中数学试题(无答案)
- 教科版三年级科学上册《第1单元第1课时 水到哪里去了》教学课件
- 通信技术工程师招聘笔试题与参考答案(某世界500强集团)2024年
- 国际贸易术语2020
- 国网新安规培训考试题及答案
评论
0/150
提交评论