组合计数.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,组合计数问题的,第六节,基本解决方法,组合计数,就是计算集合元素的个数,它是组合数学的重要组成部分,.,康托对自然数、有理数、无理数、实数集合元素的个数的研究,奠定了计数理论的深远意义,.,组合计数问题 不仅出现在自然科学与社会科学的各个领域,而且在日常生活中也经常遇到,.,由于具体问题中给出的集合各式各样,而且集合中元素的通常是由某些条件确定的,要判断一个元素是否属于集合也已非易事,要确定集合的元素个数就更加困难了,.,这也正是人们长期关心、研究计数问题的重要原因,.,解决这类问题虽然不需要高深的知识,却需要相当的技巧,.,人们经过长期的探索,已经积累了许多行之有效的计数方法与技巧,.,本讲重点介绍常用的组合计数方法与技巧,.,一,.,枚举法与加法原理、乘法原理,所谓,枚举法,就是把集合的元素一一列举出来,从而计算出集合的元素的方法,.,它是最基本、最简单的计数方法,.,在枚举过程中可适时应用排列组合中经常使用的加法原理、乘法原理,.,分类列举时要,有统一的标准,注意,不重不漏,.,例,1,数,1447,、,1005,和,1231,有某些共同点,即每,个数都是首位为,1,的四位数,且每个四位数中恰,有两个数字相同,.,这样的四位数共有多少个,?,(1983,年,第,1,届,AIME),解,符合条件的四位数分两类,:,含,1,个,1,或,2,个,1.,(1),四位数含,2,个,1,时,.,从除,1,外的,9,个数字中任意取,2,个不同的数,再与,1,个,1,组成任意排列的三位数,有 种取法,;,有 种,.,故这样构成的四位数有 个,.,(2),四位数只含,1,个,1,时,.,从除,1,外的,9,个数字中任意取,2,个不同的数,有 种取法,;,其中一数字被重复选取的有 种,这样的,3,个数字组成的三位数共有 种,.,故这样,构成的四位数个数为,综上,符合题意的四位数共有,216+216=432,个,.,例,2,直角三角形的个数为,(),如图,在,的矩形方格纸上,各个小正,方形的顶点称为格点,则以格点为顶点的等腰,(A)24 (B)38 (C)46 (D)50,(2004,年全国初中联赛第,1,试,),分析,分类时要有统一的标准,做到不重不漏,.,分类是计数中最基本的方法,其关键是,解,图中以格点为顶点的线段的长度可取,以直角边长度为标准,等腰直角三角形分为：,(1),直角边长为,1,时,有,6+6+6+6=24,个,;,(2),直角边长为 时,有,(3),直角边长为 时,有,(4),直角边长为 时,有,8+6=14,个,;,2+2+2+2=8,个,;,4,个,.,24+14+8+4=50,个,.,综上,满足条件的等腰直角三角形的个数为,例,3,设集合,选择,的两个非空子集,合,A,和,B,要使,B,中最小的数大于,A,中最大的数,则不同的选择方法种数是,(),(A)50 (B)49 (C)48 (D)47,(2006,年,全国高考卷,),解,先考虑一般情况：,对集合,最大的数为,k,则小于,k,的,k-1,个正整数组成子集,设,A,中,有 个,即所含最大的数为,k,的集合,A,有 个,而满足题设的相应的集合,B,是大于,k,的,n-k,个正,整数组成的集合的真子集,有 个,.,综上,不同的选择方法共有,n=5,时相应结论为,49,故选,(B).,二,.,配对原理,配对原理,:,两个不具有同类元素的有限集合,A,与,B,如果存在从,A,到,B,的一一对应,则,配对原理充分体现了问题转化的解题策略,应用的关键是构造出恰当的配对,.,的计数模型,同时掌握集合之间建立一一对应,应用配对原理,这需要我们多掌握一些典型,的技巧,.,这里提供几个常见的计数模型,.,1.,方程模式：,不定方程,整数解,.,共有,组不同的正,证明,问题等价于在恒等式,的,个“,+”,号在中任选,个“,+”,号,不定方程的一组正整数解,选法与方程的正整,数解之间是一一对应关系,).,(,每种选法对应着,显然,选法总数是,方程模式有着非常广泛的应用,.,举例如下,:,例,4,方程,(1985,年,全国高中,),有多少个非负整数解,?,解一,对非负整数解,由方程知,故,或,(1),当 时,若某个,则其它,这种解有,个,;,若每个,某个,则必有一个,的解有,这样,个,;,若每个,则必有三个,这样的解有,个,.,(2),当,时,仅一个,这样的解,有,个,.,综上,个,.,所求解有,解二,(,用方程模式,),令,则原方程的非负整数解与方程,的正整数解形成一一对应,.,又,由方程模式知,时,时,组正整数解,;,组正整数解,.,有,有,综上,原方程共有,组非负整数解,.,身高不同的男、女学生各名,排成一行,照相,要求男生由高到低、女生由低到高排列,？,问共有多少种不同的排法,例,6,解,先将男女生分别按要求排定后,在男生排成,的间隙间,(,包括两端,),将女生插入即可,.,设在间隙间插入的女生人数分别为,则问题等价于求方程,的非负整数解,.,令,则,由方程模式,它有,组正整数解,.,所以,要求的排法总数为,252.,数后插入一个“板”,例,7,设集合,是,的三元子集,且满足,则称,若,为集合,的“好子集”,.,求,的“好子集”的个数,.,解,在,1,2,3,n,中选三个数,选定一数便在该,三块“板”将,1,2,n,分成四,部分,设从左向右每部分分别有,为使选的数,构成“好子集”,即,必须,且,则,个数,.,的“好子集”的个数就等于该方程的正整数解,的个数,令,例,8,从一、二、三年级选,10,名学生担任学生会干,部,要求二年级不少于,4,名,三年级不多于,5,名,问有多,少种不同的选法,?,解,设一、二、三年级各选,x,、,y,、,z,名学生,.,则,x+y+z,=10,其中,x0,y4,0z5,为约束条件,.,令,a=x+1,b=y-3,c=z+1,则问题转化为,a+b+c,=9,在约束条件,1c6,下的正整数解有多少组,?,注意中,a,b1,时有,c7,的正整数解的组数,.,利用补集的思想,问题,又等价于的所有正整数解的组数减去,c=7,时相应,所有不同选法种数,由方程模式,为,例,9,两相邻男生之间至少有,2,名女生,问共有多少种不同,将,8,名男生与,25,名女生沿圆周围成一圈,任意,的围法,?,解,设两相邻男生之间站位的女生人数依次为,则,女生人数分配方案与方程的满足,的正整数解之间形成一一对应关系,.,令,则,其正整数解有,组,.,由于,25,名女生排成一列的排法有,种,作环状全排列的排法有,8,名男生,种,.,法原理,所求围法共有,男、女生分别排好后,再将女生按的解依次插入即得相应的围法,.,种,.,由,乘,2.,有重复元素的排列组合问题,例,10,的组数,.,求由,1,2,3,n,这,n,个数组成的允许重复的数组,解,任取一个由,1,2,3,n,组成的允许重复的,r,个数的,数组,设集合,则数组与的对应是集合与之间的,由配对原理,因,元素中任意选取,r,个不同的数的无重组合,是从,n+r-1,个不同的,一一对应,因此,所以,现将,得到,r,个不同的数构成的数组,从第个开始,分别加上,0,1,2,r-1,配对原理充分体现了问题转化的解题策略,应用的关键是构造出恰当的配对,.,解,数学奥林匹克评委会由,9,人组成,有关试,题藏在一个保险箱里,要求至少有,6,名评委在场,时才能打开保险箱,.,问保险箱应安装多少把锁,?,配多少把钥匙,?,怎样把钥匙分发给评委们,?,(1960,年,基辅数学竞赛,),例,11,显然应尽可能少安锁,.,设保险箱上所安锁的集合为,A,9,名评委中所,有,5,人小组的集合为,B.,则,对一个,5,人小组,必有唯一的一把锁,使,5,人小组,中没有人能打开,由此建立,B,到,A,的映射,下证,是一一映射,.,设,为另一个与,不同的人小组,则,是与,不同的锁,(,若是同一把锁,则两个,5,人,小组 与,都在场,锁,与 还是打不开,这与题设,矛盾,.).,因此,是单射,.,对于每把锁,必有,5,人小组,他们不能,打开锁,因此,是满射,.,所以 是一一映射,由配对原理,即应安装,126,把锁,.,另外,对于每把锁,a,必有,5,人小组,b,他们都不能,即,打开,a,但,b,之外的每个人都应能打开锁,a.,因此,每把锁,a,应配把钥匙,分发给人小组,b,之外,另外,对于每把锁,a,必有,5,人小组,b,他们都不能,使不同的,4,人小组对应不同的锁,.,并将每把锁的,4,把钥匙分给不同的,4,人小组的,于是总共应配,1264=504,把钥匙,每把锁,a,应配把钥匙,分发给人小组,b,之外,打开,a,但,b,之外的每个人都应能打开锁,a.,因此,的每个人,.,每个人,在给定的圆周上取定,n,个点,n6,每两点间连一线段,其中任意三条线段在圆内都不共点,求这些线段确定的且顶点在圆内的三角形的个数,.,例,12,解,设符合题意的所有三角形的,的三边交圆周于,6,点,A,B,C,D,E,集合为,S,PQRS,时,延长它,F,如图,.,设从,n,点中人任取,6,点的所有取法的集合为,T.,易知,且,6,个点,A,B,C,D,E,F,就确定了一种,取法,建立,S,到,T,的映射,对,PQRS,易见,对不同的,6,点组,A,B,C,D,E,F,也不同,从而,令,PQRS,按上述方法确定的,也不同,即 是单射,.,设取法,则如图可按取法 在圆周上确定,按逆时针方向顺序排列的,6,点,A,B,C,D,E,F,接,AD,BE,CF,得,PQRS,连,圆内,).,(,易知交点,P,Q,R,在,故 是满射,.,综上,由配对原理,是一一映射,三,.,递推法,递推法几乎对所有数学分支都有重要作用,对组合数学问题就更不例外,.,用递推法解决组合计数问题,其解题的一般,步骤,是：,(1),计算初始值；,(2),建立递推关系；,(3),利用初始值与递推关系求解,关键！,共有 个,.,共有 个；,例,13,个位置不全为,1,记,n,位数的个数为,用,1,或,2,两数字写,n,位数,其中任意相邻两,求,(,江苏省第二届数学通讯赛,),解,n3,时,符合条件的,n,位数可分为两类：,首位是,2,的,首位是,1(,则第,2,位是,2),的,因此,由初始值及递推关系可得,思考：,求,引申：,求,过程如下：,先解特征方程,得,故,将,代入,可得,于是,例,14,将圆分为,n(n2),个扇形,每个扇形用红、,白、蓝,3,种颜色之一染色,要求相邻扇形所染颜,色不同,问有多少种不同的染色方法？,解,设圆被分成,n,个扇形：,不同的染色,方法有,种,.,易知,n4,时,有,3,种染法,有,2,种染法,有,2,种染法,;,但由于,与,相邻,应排除,与,同色,情形：,与,同色时,与,为同一扇形,视,n-2,个扇形一起,共,n-1,个扇形,与另,有,种染法,.,故,利用上式重复叠代,得,经检验知,n=2,3,时该式也成立,.,故不同的染色,方法有种,注：,本题在,n=6,时即为,2001,年全国高考题,;,2003,年江苏高考又对它进行了拓扑变形,组合计数不仅仅是数学家关心是事,英,国,物理学家,狄拉克,就曾提出过一个有趣问题,:,五猴分桃问题,有一堆桃子,是五个猴子的共同财产,它们要平均分配,.,第,1,个猴子来了,把桃子平均分成,5,堆,还剩一个,这个猴子把剩下的一个吃了,并拿走其中的一堆,;,第,2,个猴子来了,又把桃子平均分成,5,堆,还剩一个,这个猴子也把剩下的一个吃了,并拿走其中的一堆,;,以后每个猴子都如此办理,.,问原来至少有多少桃子,?,最后至少有多少桃子,?,例,15,解,设原来有,A,个桃子,为,五个猴子拿走的桃子数,则,解得,时,为整数,.,因,有,A,最少应满足,即,A=3121.,此时,最后至少有,4,255=1020,个桃子,原来至少有,3121,个桃子,.,四,.,容斥原理,这是加法原理的一种推广形式,其基本思想,是采取“多退少补”来完成计数,.,的子集合,且,定理,1,(,容斥原理,),设 是有限集合,则,定理,2,(,逐步淘汰原则,),设 是有限集,合,S,的子集合,则,定理,2,(,逐步淘汰原则,),设 是有限集,例,16,由数字,1,2,和,3,组成的,n,位数,要求,n,位数中,1,2,和,3,的每一个至少出现一次,.,求所有这种,n,位,数的个数,.(,匈牙利,),解,记由,1,2,3,组成的,n,位数的全体构成的集合,为,S.,S,中所有不含,k,的,n,位数的集合为,则,为,S,中所有含,k,的,n,位数的集合,同时含有,1,2,3,的,n,位数的集合为,S,中,由逐步淘汰原则,因为,故所求的,n,位数个数为,例,17,(,贝努里错投信笺问题,),今有,6,封信及,6,个,配套信封,现把所有的信一一投到信封中去,求,全部投错的方法总数,.,(19601961,年,波兰,),解,设 为第,i,封信恰好投入第,i,个信封的所有投,法构成的集合,(i=1,2,6).,方法的集合为,则所有全部投错的,易知,故由逐步淘汰原则,全集,而,例,18,4,个,3,个,2,个的全部排列中,求不,出现,图象的排列数,.,解,9,个符号的全排列中,所有出现图,象的排列记为,A,出现图象的排列记为,B,出现图象的排列记为,C.,对,A,视为一个元素,与另,5,个元素,进行排列,考虑到重复,3,次,重复,2,次,可得,类似地,有,因此,所求排列数 为,例,19,求小于,2000,的自然数中不能被,5,、,6,、,7,整除的自然数的个数,.,解,设,为小于,2000,的自然数中不能被 整除,的数组成的集合,.,7,整除的自然数的个数为,则小于,2000,且不能被,5,、,6,、,由于,解,设,为小于,2000,的自然数中不能被 整除,的数组成的集合,.,7,整除的自然数的个数就是,则小于,2000,且不能被,5,、,6,、,由于,由容斥原理,由逐步淘汰原则,五,.,母函数法,母函数法是一种应用很广的非常有用的方法,特别是对组合问题的求解,有一个比较统一的处理方法,.,此方法的系统叙述,最早见于,Laplace1812,年的名著,概率解析理论,中,.,其思想方法十分朴素简单,:,即把离散的数列与幂级数一一对应起来,将数列间的相互结合关系对应成幂级数间的运算关系,最后由幂级数形式来确定数列的构造,.,这就将初等数学与高等数学的密切联系充分展现出来,.,例,20,从一、二、三年级选,10,名学生担任学生,会干部,要求二年级不少于,4,名,三年级不多于,5,名,问有多少种不同的选法,?,解,设从三个年级选,r,个学生的不同选法有,种,则数列,的母函数为,所求的不同选法总数,就是,系数,.,展开式中,的,由于,即,利用幂级数知识,求导得,再求导得,即,所以,由此易知 展式,中,的系数为,作业,谢谢!,