加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 组合数学

组合数学

组合数学

aswjty
2008-09-12 0人阅读 举报 0 0 暂无简介

简介:本文档为《组合数学pdf》,可适用于自然科学领域

组合数学清华大学计算机黄连生年月前言组合数学是一个古老而又年轻的数学分支。据传说大禹在多年前就观察到神龟背上的幻方…前言幻方可以看作是一个阶方阵其元素是到的正整数每行、每列以及两条对角线的和都是。前言贾宪北宋数学家(约世纪)著有《黄帝九章细草》、《算法斅古集》斅音“笑(“古算法导引”)都已失传。杨辉著《详解九章算法》(年)中曾引贾宪的“开方作法本源”图(即指数为正整数的二项式展开系数表现称“杨辉三角形”)和“增乘开方法”(求高次幂的正根法)。前者比帕斯卡三角形早年后者比霍纳(WilliamGeogeHorner)的方法(年)早年。前言年莱布尼兹所著《组合学论文》一书问世这是组合数学的第一部专著。书中首次使用了组合论(Combinatorics)一词。前言组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广内容庞杂并且仍在很快地发展着因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。前言•本学期主要讲组合分析(计数和枚举)以及组合优化的一部分(线性规划的单纯形解法)。•组合分析是组合算法的基础。前言组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是要学好组合数学并非易事既需要一定的数学修养也要进行相当的训练。第一章排列组合加法法则与乘法法则加法法则与乘法法则加法法则设事件A有m种产生方式事件B有n种产生方式则事件A或B之一有mn种产生方式。集合论语言:若|A|=m,|B|=n,A∩B=∅,则|A∪B|=mn。加法法则与乘法法则例某班选修企业管理的有人不选的有人则该班共有=人。例北京每天直达上海的客车有次客机有次则每天由北京直达上海的旅行方式有=种。加法法则与乘法法则乘法法则设事件A有m种产生式事件B有n种产生方式则事件A与B有m·n种产生方式。集合论语言:若|A|=m,|B|=n,A×B={(a,b)|a∈A,b∈B},则|A×B|=m·n。加法法则与乘法法则例某种字符串由两个字符组成第一个字符可选自{abcde}第二个字符可选自{}则这种字符串共有×=个。例从A到B有三条道路从B到C有两条道路则从A经B到C有×=条道路。加法法则与乘法法则•例某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄条纹色可选黑、白则共有×=种着色方案。•若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话则方案数就不是×=而只有×=种。•在乘法法则中要注意事件A和事件B的相互独立性。加法法则与乘法法则例)求小于的含的正整数的个数)求小于的含的正整数的个数)小于的不含的正整数可看做位数,但除外故有×××-=个含的有:-=个另:全部位数有个,不含的四位数有个,含的位数为两个的差:-=个)“含”和“含”不可直接套用。含但不含。在组合的习题中有许多类似的隐含的规定要特别留神。不含的位数有个位数有个位数有个位数有个不含小于的正整数有=(-)(-)=个含小于的正整数有-=个排列与组合定义从n个不同的元素中取r个不重复的元素按次序排列称为从n个中取r个的无重排列。排列的全体组成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。一般不说可重即无重。可重排列的相应记号为P(n,r),P(n,r)。排列与组合定义从n个不同元素中取r个不重复的元素组成一个子集而不考虑其元素的顺序称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示组合的个数用C(n,r)表示对应于可重组合有记号C(n,r),C(n,r)。排列与组合从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒个。第个盒子有n种选择第个有n种选择······第r个有nr种选择。故有P(n,r)=n(n)······(nr)有时也用nr记n(n)······(nr)排列与组合若球不同盒子相同则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)·r!=P(n,r),C(n,r)=P(n,r)r!=nrr!=()=易见P(n,r)=nnrrn!r!(nr)!若球不同盒子相同则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)·r!=P(n,r),C(n,r)=P(n,r)r!=nrr!=()=易见P(n,r)=n排列与组合例有本不同的日文书本不同的英文书本不同的中文书。)取本不同文字的书)取本相同文字的书)任取两本书排列与组合解)×××=)C(,)C(,)C(,)==)==()排列与组合•求r个r个…rt个t的排列数设rr…rt=n,设此排列数为P(nr,r,…,rt),对…t分别加下标得到P(nr,r,…,rt)·r!·r!·…·rt!=n!•∴P(nr,r,…,rt)==()n!r!r!…rt!nrr…rt排列与组合•从n个中取r个的圆排列的排列数为P(n,r)r,≤r≤n•以个元素为例排列与组合•从n个中取r个的项链排列的排列数为P(n,r)r,≤r≤n•项链排列就是说排列的方法和项链一样,在圆排列的基础上正面向上和反面向上两种方式放置各个数是同一个排列。•例下面两种方式实际上表示的都是个元素的同一种排列。排列与组合例从,中取个不同的数使这个数的和能被整除有多少种方案?解将,分成类:A={i|i≡(mod)}={,,,…,},B={i|i≡(mod)}={,,,…,},C={i|i≡(mod)}={,,,…,}要满足条件有四种解法:)个数同属于A)个数同属于B)个数同属于C)A,B,C各取一数故共有C(,)==排列与组合例某车站有个入口处每个入口处每次只能进一人一组个人进站的方案有多少?解一进站方案表示成:其中“”表示人“”表示门框其中“”是不同元“”是相同元。给“”n个门只用n个门框。任意进站方案可表示成上面个元素的一个排列。排列与组合解法标号可产生!个个元的全排列。故若设x为所求方案则x·!=!∴x=!!=排列与组合解法在个元的排列中先确定“”的位置有C(,)种选择在确定人的位置有!种选择。故C(,)·!即所求排列与组合解法把全部选择分解成若干步使每步宜于计算。不妨设个人编成至号。号有种选择号除可有号的所有选择外还可(也必须)选择当与号同一门时在号的前面还是后面故号有种选择号的选择方法同号故共有种。以此类推号有种选择。故所求方案为Stirling近似公式•组合计数的渐进值问题是组合论的一个研究方向。•Stirling公式给出一个求n!的近似公式它对从事计算和理论分析都是有意义的。Stirling近似公式•)Wallis公式令Ik=∫sinxdx显然I=,I=k≥时Ik=-cosxsinx|∫(k-)cosxsinxdx=(k-)∫(-sinx)sinxdx=(k-)(Ik--Ik)kπ-kπ-π-π-π-kk故Ik=Ik()kkStirling近似公式令n!!=···…·(n)·nn是奇数。···…·(n)·nn是偶数。()由()I,k是奇数Ik=I,k是偶数(k)!!k!!(k)!!k!!当x∈(,π)时sinx<sinx因而Ik<Ik<Ik,k=,,…。kkStirling近似公式•由()<·<(k)!!(k)!!π(k)!!(k)!!(k)!!(k)!!<<π(k)!!(k)!!·kkkk→∞Stirling近似公式•所以lim=,(k)!!(k)!!·kπk→∞lim=,(k)!!(k)!!(k)!·kπk→∞lim=。()(k!)(k)!·kπk→∞kStirling近似公式•)stirling公式yy=lnxnnxStirling近似公式•令An=∫lnxdx=xlnx|-∫dx=nlnn-n()•tn=-lnln…ln(n-)-lnn=ln(n!)--lnn()•tn的几何意义是由x轴,x=n,以及连接(,),(,ln),…,(n-,ln(n-)),(n,lnn)诸点而成的折线围成的面积。nnnStirling近似公式•Tn=-ln…ln(n-)-lnn()Tn是由三部分面积之和构成的。一是曲线y=lnx在x=k点的切线和x轴以及x=k--,x=k--包围的梯形当k分别为,,…,n时的面积之和一是由y=lnx在x=点的切线x=线以及x轴围城的梯形另一是由y=lnn,x=n--,x=n及x轴包围的矩形面积。因而有tn<An<Tn()Stirling近似公式•令bn=An-tn序列b,b,…是单调增而且有上界故有极限令limbn=b•由(),()得bn=nlnn-n-ln(n!)-lnn=lnn-n-ln(n!)-lnn•ln(n!)=-bnlnn-lnn-lne•∴n!=en(-)()<An-tn<Tn-tn=-n→∞n√√nnbn√nenStirling近似公式•令βn=e,limβn=β•将()代入(),整理得β=π•所以n!~πn(-)n→∞bn√√nen模型转换•“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。•如我们说A集合有n个元素|A|=n无非是建立了将A中元与,n元一一对应的关系。•在组合计数时往往借助于一一对应实现模型转换。•比如要对A集合计数但直接计数有困难于是可设法构造一易于计数的B使得A与B一一对应。模型转换•例简单格路问题|(,)→(m,n)|=()从(,)点出发沿x轴或y轴的正方向每步走一个单位最终走到(m,n)点有多少条路径?mnmy(m,n)x模型转换•无论怎样走法在x方向上总共走m步在y方向上总共走n步。若用一个x表示x方向上的一步一个字母y表示y方向上的一步。•则(,)→(m,n)的每一条路径可表示为m个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号可得m!n!个mn元的无重全排列。模型转换•设所求方案数为p(mnmn)•则P(mnmn)·m!·n!=(mn)!•故P(mnm,n)==()=()=C(mn,m)•设c≥a,d≥b,则由(a,b)到(c,d)的简单格路数为|(a,b)(c,d)|=()(mn)!mnmnm!n!mn(ca)(db)ca(c,d)(a,b)模型转换•例在上例的基础上若设m<n求(,)点到(m,n)点不接触对角线x=y的格路的数目(“接触”包括“穿过”)•从(,)点到(m,n)点的格路有的接触x=y有的不接触。•对每一条接触x=y的格路做(,)点到第一个接触点部分关于x=y的对称格路这样得到一条从(,)到(m,n)的格路。模型转换•容易看出从(,)到(m,n)接触x=y的格路与(,)到(m,n)的格路(必穿过x=y)一一对应yy=x(m,n)(,)x(,)yxy=(m,n)x(,)(,)模型转换•故所求格路数为()-()=-=(-)=()=(-)()=()mnmnmm(mn)!(mn)!(mn)!m!(n)!(m)!n!(m)!(n)!mnmnmnmmnmmnnmnmnmn模型转换•若条件改为可接触但不可穿过则限制线要向下或向右移一格得x-y=(,)关于x-y=的对称点为(,)•所求格路数为()-()=-=()mnmnmm(mn)!(mn)!nmm!n!(m)!(n)!nmnm格路也是一种常用模型模型转换•例CnHn是碳氢化合物,随着n的不同有下列不同的枝链:H|HCH|HH|HCH|HCH|HH|HCH|HCH|HCH|Hn=甲烷n=乙烷n=丙烷模型转换H|HCH|HCH|HCH|HCH|HH|HHCH||HCCH||HCH|HHn=丁烷n=异丁烷这说明对应CnHn的枝链是有n个顶点的一棵树其中n个顶点与之关联的边数为其它n个顶点是叶子。对于这样结构的每一棵树就对应有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnHn模型转换•例在名选手之间进行淘汰赛(即一场的比赛结果失败者退出比赛),最后产生一名冠军问要举行几场比赛?•解一种常见的思路是按轮计场费事。另一种思路是淘汰的选手与比赛(按场计)集一一对应。场比赛。模型转换•例(Cayley定理)n个有标号的顶点的树的数目等于n。n生长点不是叶子,每个生长点是,n中的任一元有n种选择。两个顶点的树是唯一的。模型转换⑦⑥||②③①⑤④逐个摘去标号最小的叶子叶子的相邻顶点(不是叶子是内点)形成一个序列序列的长度为n例给定一棵有标号的树边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边)第一次摘掉②③为②相邻的顶点得到序列的第一个数以此类推得到序列,长度为-=这是由树形成序列的过程。模型转换•由序列形成树的过程:由序列得到一个新序列生成的过程是首先将排序得到因为序列的长度为得到按升序排序的序列序列的长度为(即n)然后将按照大小插入到序列中得到然后将两个序列排在一起模型转换②③①③④⑤⑤⑥①⑤第一步推导:将上下两个序列同时去掉上行序列的第一个元素(用黄色表示)去掉下行序列的第一个无重复的元素(用红色表示)。生成一条边(②③)。依此类推减到下面剩最后两个元素这两个元素形成最后一条边。最后形成树。模型转换•上述算法描述:给定序列b=(bb…bn)设a=(…nn)将b的各位插入a,得a’,对()做操作。a’是n个元的可重非减序列。ba’操作是从a’中去掉最小无重元设为a,再从b和a’中各去掉一个b中的第一个元素设为b则无序对(a,b)是一条边。重复这一操作得n条边最后a’中还剩一条边共n条边正好构成一个树。b中每去掉一个元a’中去掉个元。模型转换•由算法知由树T得b=(bb…bn)反之由b可得T。即f:T→b是一一对应。•由序列确定的长边过程是不会形成回路的。因任意长出的边(u,v)若属于某回路此回路中必有一条最早生成的边不妨就设为(u,v)必须使u,v都在长出的边中重复出现但照算法u,v之一从下行消失不妨设为u从而不可能再生成与u有关的边了故由()得到的边必构成一个n个顶点的树。ba’模型转换•证由一棵n个顶点的树可得到一个长度为n-的序列且不同的树对应的序列不同*因此|T|≤n。•*对n用归纳法可证•反之由一个长度为n-的序列(每个元素为~n的一个整数)可得到一棵树且不同的序列对应的树是不同的因此n≤|T|•|T|=n#nnn全排列的生成算法就是对于给定的字符集用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。全排列的生成算法全排列的生成算法这里介绍全排列算法四种:(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法字典序法对给定的字符集中的字符规定了一个先后关系在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。字典序法例字符集{,,},较小的数字较先,这样按字典序生成的全排列是:,,,,,。※※一个全排列可看做一个字符串字符串可有前缀、后缀。字典序法)生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀也即变化限制在尽可能短的后缀上。字典序法例是的排列。的排列最前面的是最后面的是从右向左扫描若都是增的就到了也就没有下一个了。否则找出第一次出现下降的位置。字典序法求的下一个排列<<>>在后缀中找出比大的数找出其中比大的最小数、对换后缀变为将此后缀翻转接上前缀得到即的下一个。例为后缀大于的用橙色表示小于的用绿色表示找出比右边数字小的第一个数字典序法在,n的全排列中,nn…是最后一个排列,其中介数是(n,n,,,,)其序号为n∑k×k!k=另一方面可直接看出其序号为n!nn于是n!=∑k×k!即n!=∑k×k!k=k=字典序法一般而言设P是,n的一个全排列。P=PP…Pn=PP…PjPjPj…PkPkPk…Pnj=max{i|Pi<Pi},k=max{i|Pi>Pj}对换PjPk将Pj…PkPjPk…Pn翻转P’=PP…PjPkPn…PkPjPk…Pj即P的下一个字典序法)计算给定排列的序号的序号即先于此排列的排列的个数。将先于此排列的排列按前缀分类。前缀先于的排列的个数:×!第一位是,先于得的排列的个数:×!前位是,先于得的排列的个数:×!先于此排列的的排列的个数:×!×!×!前位是,先于得的排列的个数:×!×!前位是,先于得的排列的个数:×!×!前位是,先于得的排列的个数:×!×!前位是,先于得的排列的个数:×!×!前位是,先于得的排列的个数:×!×!前位固定则最后一位也随之固定将!,!,…,!前面的系数抽出放在一起得到此数的特点::的右边比小的数的个数:的右边比小的数的个数:的右边比小的数的个数:的右边比小的数的个数:的右边比小的数的个数:的右边比小的数的个数:的右边比小的数的个数:的右边比小的数的个数是计算排列的序号的中间环节我们称之为中介数。※这是一个很有用的概念。字典序法一般而言,对于,的全排列中介数首位的取值为第位的取值为以此类推第位的取值为、。从而序号可表示为:n∑ki(ni)!i=ki:Pi的右边比Pi小的数的个数i=,,…,n字典序法由中介数推出排列的算法例由推算出方法:PPPPPPPPPP=→==→P==但已在P左边出现↑=但已在P左边出现↑=→P==但已经在P左边出现=→P=↑=但已经在P左边出现=→P==但,已经在P左边出现=但已经在P左边出现=→P==但已经在P左边出现=但已经在P左边出现=→P==→P=→P=这个过程比较麻烦(这酝酿着改进的可能)该算法从左到右依次推出P,P,…,P。下述算法依次定出,,,…,的位置。字典序法方法:中未出现在最右边中介数右端加一个扩成位先定每定一位其左边未定位下加一点从(位-位下点数=)的位中选最左的。定的位置●●●●●●●●●●●●●●●●●●●●●●●●●●●由推算出字典序法方法:已定出上标‘●’找左起第一个下标‘’由推算出●=●●●●=●●●●=●●●●●=●●●●●●●●=●●●●●●●●●●=●●●●●●●●●●●●=●●●●●●●以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数→进位链(中介数的后继)→递增进位制数递增进位制数法)由排列求中介数在字典序法中中介数的各位是由排列数的位决定的中介数位的下标与排列的位的下标一致。在递增进位制数法中中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(n)一致。递增进位制数法可看出n位的进位链。右端位逢进右起第位逢进…右起第i位逢i进i=,,…,n这样的中介数我们称为递增进位制数。上面是由中介数求排列。递增进位制数法由序号(十进制数)求中介数(递增进位制数)如下:m=m,≤m≤n!m=mkn,≤kn≤m=mkn,≤kn≤……………mn=(n)mnk,≤k≤nmn=k,≤k≤npp…pn←→(kk…kn)↑←→m递增进位制数法在字典序法中由中介数求排列比较麻烦我们可以通过另外定义递增进位制数加以改进。为方便起见令ai=knIi=,,…,n(kk…kn)↑=(anan…a)↑ai:i的右边比i小的数字的个数递增进位制数法在这样的定义下有←→()↑()↑=()↑←→×)×)×)×)×)×)×=递增进位制数法由(anan…a)↑求pp…pn。从大到小求出n,n,…,,的位置n…an个空格n的右边有an个空格。n的右边有an个空格。…………的右边有a个空格。最后一个空格就是的位置。V递增进位制数法↓↓↓↓↓↓↓↓aaaaaaaa★V个空格★V个空格★★★★★★V个空格V个空格V个空格个空格序号nm=∑ak(k)!k=递减进位制数法在递增进位制数法中中介数的最低位是逢进进位频繁这是一个缺点。把递增进位制数翻转,就得到递减进位制数。(anan…a)↑→(aa…anan)↓→()↓nnm=∑akn!k!=n!∑akk!k=k=()↓=×)×)×)×)×)×)×=※※求下一个排列十分容易邻位对换法递减进位制数法的中介数进位不频繁求下一个排列在不进位的情况下很容易。这就启发我们能不能设计一种算法下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的从右向左而邻位对换法的换位是双向的。邻位对换法这个算法可描述如下:对n的每一个偶排列n从右到左插入n个空档(包括两端)生成n的n个排列。对n的每一个奇排列n从左到右插入n个空档生成n的n个排列。对,n的每个数字都是如此。邻位对换法例→●→解的右边有个数字(奇数)比小,上加一个点。●●的右边有个数字(偶数)比小,上不加点。的右边有个数字(偶数)比小,上不加点。的右边有个数字(偶数)比小,上不加点。的右边有个数字(偶数)比小,上不加点。的右边有个数字(奇数)比小,上加一个点。的右边有个数字(奇数)比小,上加一个点。上共有个(奇数)点上箭头向右。P=→()↓bbbbbbbb上箭头向左右边有个数字比小b=上箭头向右左边有个数字比小b=上箭头向右左边有个数字比小b=上箭头向右左边有个数字比小b=上箭头向右左边有个数字比小b=上箭头向左右边有个数字比小b=上箭头向左右边有个数字比小b=上箭头向右左边有个数字比小b=的中介数为←→→→→→→←邻位对换法ak(p):p中k排列的序号ak(p)的奇偶性与k排列的奇偶性相同。a(p)=×a(p)b(p)=×(×a(p)b(p))b(p)※※an(p)bn(p)简写成anbn邻位对换法已知()↓求排列。的位置由b和a的奇偶性决定。a的奇偶性同b的奇偶性。a的奇偶性同bb的奇偶性。b=,。→←→b奇→bb偶→b奇→→→bb奇→b奇→邻位对换法序号=·)·)·)·)·)·)·=←→()↓邻位对换法字典序法递增进位制法递减进位制法邻位对换法下一个中介数↑↑↓↓序号组合的生成•设从,n中取r元的组合全体为C(n,r)•CC…Cr∈C(n,r)不妨设C<C<…<Cr•i≤Ci≤(n-ri),i=,,…,r•令j=max{i|Ci<n-ri}•则CC…Cr的下一个组合为CC…Cj(Cj)(Cj)…(Cjr-j)•这等于给C(n,r)的元素建立了字典序。•…r的序号为nrnr…n的序号为()-nr组合的生成•例在C(,)中的序号是•首位小于的组合的个数首位是第位小于的组合的个数前位是第位小于的组合的个数前位是第位小于的组合的个数之和。•反之也可以由序号求组合。组合的生成•A(m,l):,m的l组合(或l子集)。第个组合:{,,…,l,l}最后个组合:{,,…,l,m}•A(n,k)=A(n,k)A(n,k)○{n}•A:将有序集A(或线性表)的顺序逆转的有序集。•A○n:将A中每个元素(是集合)都与{n}求并的有序集××组合的生成•例用两种方法计算,n的无重不相邻组合C’(n,r)的计数问题•解法•……………•其中不可含共n位r个①以结尾:r个与n(r)个的排列rn(r)=nr这样的排列有(nr)!=(r)!(nr)!()nrr组合的生成•②以结尾:r个与nr个的排列rnr=nr•这样的排列有()个•()()=()f(aa…ar)=bb…brnrrnrnrnrrrr组合的生成•解法2•任给aa…ar∈C’(n,r),a<a<…<ar•令f:aa…ar→bb…br•bi=aii,i=,,…,r•≤b<b<…<br≤nr,bb…br∈C(nr,r)•C’(n,r)=C(nr,r)可重组合•C(n,r)的计数问题相当于r相同的球放入n个互异的盒子每盒球的数目不同的方案的计数。而后一问题又可转换为r个相同的球与n个相同的盒壁的排列的问题。•易知所求计数为=C(nr,r)•即C(n,r)=()=C(n,r)C(n,r)不含“1”至少含一个“1”(nr)!r!(n)!nrrr个相同的球/…………n个相同的盒壁可重组合•另证设aa…ar∈C(n,r)≤a≤a≤…≤ar≤n,•令C(n,r)上的f使得bi=aii,i=,,…,r•则bb…br满足≤b<b<…<br≤nrbb…br∈C(nr,r)•f:aa…ar→bb…br•显然f是单射f:bb…br→aa…ar--可重组合•ai=bii,i=,,…,r•aa…ar∈C(n,r)•f是单射C(n,r)≤C(nr,r)•f是单射C(n,r)≥C(nr,r)•∴C(n,r)=C(nr,r)•第二个证明可说一种“拉伸压缩”技巧。不可谓不巧妙。但仍不如第一证明来的明快由此可见组合证明的功效。若干等式及其组合意义•组合意义或组合证明含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。若干等式及其组合意义•C(n,r)=C(n,nr)()•从,n去掉一个r子集剩下一个(nr)子集。由此建立C(n,r)与C(n,nr)的一个一一对应。•故C(n,r)=C(n,nr)若干等式及其组合意义•C(n,r)=C(n,r)C(n,r)()•从,n取a,a,…,ar设≤a<a<…<ar≤n,对取法分类:a=,有C(n,r)种方案a>,有C(n,r)种方案•共有C(n,r)C(n,r)中方案故C(n,r)=C(n,r)C(n,r)若干等式及其组合意义•杨辉三角除了(,)点都满足此递推式•<r≤n,n<<rC(n,r)=,r=,≤n<r,r<≤nn<且r<•C(mn,m)=C(mn,m)C(mn,m)•{(,)→(m,n)}={(,)→(m,n)}∪{(,)→(m,n)}()()|r||n|nrnrr!若干等式及其组合意义•()()()…()=()()•可从()推论也可做一下组合证明从,nr取aa…anan设a<a<…<an<an可按a的取值分类:a=,,,…r,r•a=,a…an取自,nr有()种取法nnnnrnrnnnnnnrna=,a…an取自,nr有()种取法nrn………a=r,a…an取自r,nr有()种取法nna=r,a…an取自r,nr有()种取法nn也可看做按含不含含不含,…,含r不含r的不断分类若干等式及其组合意义•从(,)到(n,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上)(),(),…,()•故有()()()…()=()nnnrnnnnnnnrnrnnnnnr(n,r)(,)nn若干等式及其组合意义•可重组合,n的C(n,r)模型()•不含,含个,含个,…,含r个•C(),C(),C(),…,C()•(),(),(),…,()nrrnnnnrrrnrnrnrnrrr若干等式及其组合意义•()()=()()()•①选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委•②选常委,再选非常委政治局委员•两种选法都无遗漏,无重复地给出可能的方案应该相等。nlnnr

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/49

组合数学

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利