组合数学第一章

第一章排列组合,1.1加法法则与乘法法则,1.1加法法则与乘法法则,加法法则设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。,集合论语言：若|A|=m,|B|=n,AB=,则|AB|=m+n。,1.1加法法则与乘法法则,例某班选修企业管理的有18人，不选的有10人，则该班共有18+10=28人。,例北京每天直达上海的客车有5次，客机有3次，则每天由北京直达上海的旅行方式有5+3=8种。,1.1加法法则与乘法法则,乘法法则设事件A有m种产生式，事件B有n种产生方式，则事件A与B有mn种产生方式。,集合论语言：若|A|=m,|B|=n,AB=(a,b)|aA,bB,则|AB|=mn。,1.1加法法则与乘法法则,例某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则这种字符串共有53=15个。,例从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6条道路。,1.1加法法则与乘法法则,例某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是44=16，而只有43=12种。在乘法法则中要注意事件A和事件B的相互独立性。,1.1加法法则与乘法法则,例1)求小于10000的含1的正整数的个数2)求小于10000的含0的正整数的个数,1)小于10000的不含1的正整数可看做4位数,但0000除外.故有999916560个.含1的有：99996560=3439个,另:全部4位数有10个,不含1的四位数有9个,含1的4位数为两个的差:109=3439个,44,44,2)“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。,不含0的1位数有9个，2位数有9个，3位数有9个，4位数有9个,不含0小于10000的正整数有9+9+9+9=(91)/(91)=7380个,含0小于10000的正整数有99997380=2619个,2,3,4,2,3,4,5,1.2排列与组合,定义从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。一般不说可重即无重。可重排列的相应记号为-P(n,r),P(n,r)。,1.2排列与组合,定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)表示，对应于可重组合-有记号C(n,r),C(n,r)。,1.2排列与组合,从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，第r个有n-r+1种选择。故有P(n,r)=n(n-1)(n-r+1)有时也用nr记n(n-1)(n-r+1),1.2排列与组合,若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)r!=P(n,r),C(n,r)=P(n,r)/r!=nr/r!=()=易见P(n,r)=n,nr,r,n!r!(n-r)!,若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)r!=P(n,r),C(n,r)=P(n,r)/r!=nr/r!=()=易见P(n,r)=n,1.2排列与组合,例有5本不同的日文书，7本不同的英文书，10本不同的中文书。1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书,1.2排列与组合,5+7+102,解1)57+510+710=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=(),1.2排列与组合,求r1个1，r2个2，rt个t的排列数，设r1+r2+rt=n,设此排列数为P(n;r1,r2,rt),对1，2，t分别加下标，得到P(n；r1,r2,rt)r1!r2!rt!=n!P(n；r1,r2,rt)=(),n!r1!r2!rt!,nr1r2rt,1.2排列与组合,从n个中取r个的圆排列的排列数为P(n,r)/r,2rn以4个元素为例,12431234,12432341,12433412,12434123,1.2排列与组合,从n个中取r个的项链排列的排列数为P(n,r)/2r,3rn项链排列就是说排列的方法和项链一样,在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。例下面两种方式实际上表示的都是3个元素的同一种排列。,112332,1.2排列与组合,例从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？,解将1,300分成3类：A=i|i1(mod3)=1,4,7,298,B=i|i2(mod3)=2,5,8,299,C=i|i3(mod3)=3,6,9,300.要满足条件，有四种解法：1)3个数同属于A;2)3个数同属于B3)3个数同属于C;4)A,B,C各取一数.,故共有3C(100,3)+100=485100+1000000=1485100,3,1.2排列与组合,例排列26个字母，使得在a和b5之间正好有7个字，问有多少种排法?解以a排头、b结尾、中间恰含7个字母的排列有P(24，7)种，同理，以b排头、a结尾、中间恰含7个字母的排列也有P(24，7)种由加法法则以a，b为端点的9个字母的排列有2P(24，7)种把一个这样的排列看成一个整体再与剩下的17个字母进行全排列就得到所求的排列全排列的方法有18!种，根据乘法法则，所求的排列数是N2P(24，7)18!=3624!,1.2排列与组合,例(1)10个男孩和5个女孩站成一排如果没有两个女孩相邻，问有多少种排法?(2)10个男孩和5个女孩站成一个圆圈如果没有两个女孩相邻，问有多少种排法?解把男孩看成格子的分界，每两个男孩之间看成一个空格，把女该安排在空格中(1)男孩组成格子的方法是P(10，10)种对于任何一种组法，有11个位置可以放女孩，故女孩排法数为P(11，5)，根据乘法法则所求的排法数为NP(10，10)P(11，5),1.2排列与组合,(2)男孩组成格子的方法数是10个元素的环排列数为P(10，10)10，而女孩放入10个格子的方法数是P(10,5)由乘法法则总的排列数是N=P(10，10)10P(10,5),1.2排列与组合,例某车站有6个入口处，每个入口处每次只能进一人，一组9个人进站的方案有多少？,解一进站方案表示成：00011001010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。,1.2排列与组合,解法1标号可产生5!个14个元的全排列。故若设x为所求方案，则x5!=14!x=14!/5!=726485760,1.2排列与组合,解法2在14个元的排列中先确定“1”的位置，有C(14,5)种选择，在确定人的位置，有9！种选择。故C(14,5)9!即所求,1.2排列与组合,解法3把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种以此类推，9号有14种选择。故所求方案为67814,1.3模型转换,“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。如我们说A集合有n个元素|A|=n，无非是建立了将A中元与1,n元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换。比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。,1.3模型转换,例,简单格路问题|(0,0)(m,n)|=()从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？,m+nm,y(m,n).0.x,1.3模型转换,无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。则(0,0)(m,n)的每一条路径可表示为m个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。,1.3模型转换,设所求方案数为p(m+n；m，n)则P(m+n；m，n)m!n!=(m+n)!故P(m+n;m,n)=()=()=C(m+n,m)设ca,db,则由(a,b)到(c,d)的简单格路数为|(a,b)(c,d)|=(),(m+n)!m+nm+nm!n!mn,(c-a)+(d-b)c-a,(c,d)(a,b),1.3模型转换,例CnH2n+2是碳氢化合物,随着n的不同有下列不同的枝链：,H|HCH|H,H|HCH|HCH|H,H|HCH|HCH|HCH|H,n=1甲烷n=2乙烷n=3丙烷,1.3模型转换,H|HCH|HCH|HCH|HCH|H,H|HHCH|HCCH|HCH|HH,n=4丁烷n=4异丁烷,这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化,合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.,1.4可重排列与可重组合,多重集是元素可以多次出现的集合，某个元素ai出现的次数ni(ni=0,1,)称为该元素的重复数。一般把含有k种不同元素的多重集S记作n1a1,n2a2,nkak定理1若多重集S=n1a1,n2a2,nkak,且nir，则S的r-排列数为k例求不多于4位的二进制数的个数解该问题相当于多重集S=0,1的4排列问题,故所求的个数为2=16,r,4,1.4可重排列与可重组合,定理2若多重集S=n1a1,n2a2,nkak,且n=n1+n2+nk,则S的排列数为（）定理1若多重集S=n1a1,n2a2,nkak,且nir，i=1,2,k,则S的r-组合数为C(k+r-1,r),nn1n2nk,1.4可重排列与可重组合,S的任一r-组合都具有以下形式x1a1,x2a2,xkak其中x1,x2,xk是非负整数，且满足x1+x2+xk=r反之，对于每一组满足方程x1+x2+xk=r的非负整数解x1,x2,xk，x1a1,x2a2,xkak就是S的一个r-组合,1.4可重排列与可重组合,例从为数众多的一分币、贰分币、一角币和二角币中可以有多少种方法选出六枚？解这是从多重集S=一分币，二分币，一角币，二角币中重复选取6枚硬币的6-组合数，故为C(4+6-1,6)=C(9,6)=84例数1400有多少个正因数？,1.5若干等式及其组合意义,组合意义或组合证明，含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。,1.5若干等式及其组合意义,1.C(n,r)=C(n,n-r)从1,n去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。故C(n,r)=C(n,n-r),1.5若干等式及其组合意义,2.C(n,r)=C(n-1,r)+C(n-1,r-1)从1,n取a1,a2,ar.设1a1a2arn,对取法分类：a1=1,有C(n-1,r-1)种方案a11,有C(n-1,r-1)种方案共有C(n-1,r)+C(n-1,r-1)中方案，故C(n,r)=C(n-1,r)+C(n-1,r-1),1.5若干等式及其组合意义,3.()+()+()+()=()1组合证明从1,n+r+1取a1a2anan+1，设a1a2anan+1，可按a1的取值分类：a1=1,2,3,r,r+1.a1=1,a2an+1取自2,n+r+1有()种取法,nn+1n+2n+rn+r+1nnnnn,n+rn,a1=2,a2an+1取自3,n+r+1有()种取法,n+r-1n,a1=r,a2an+1取自r+1,n+r+1有()种取法,n+1n,a1=r+1,a2an+1取自r+2,n+r+1有()种取法,nn,也可看做按含1不含1，含2不含2,含r不含r的不断分类,1.5若干等式及其组合意义,2从(0,0)到(n+1,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上)(),(),()故有.()+()+()+()=(),nn+1n+rnnn,nn+1n+2n+rn+r+1nnnnn,r(n+1,r).(0,0)nn+1,1.5若干等式及其组合意义,4.()()=()()选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委选常委,再选非常委政治局委员两种选法都无遗漏,无重复地给出可能的方案，应该相等。,nlnn-rlrrl-r,1.5若干等式及其组合意义,5.()+()+()=2,m0,(1.7.5)证1(x+y)=()xy,令x=y=1,得(1.7.5)组合证11,m的所有方案.每一子集都可取k1,m或不取.这样有2个方案.另可有0-子集(