1-1 排列与组合

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,组合数学,钱 江,jqian104,北邮理学院,组合数学就是按照一定的规则来安排一些离散个体的有关问题。其内容包括：,1,、,计数与枚举,2,、,容斥原理和鸽巢原理,3,、,组合设计,4,、,组合算法和组合优化,5,、,图论,排列、组合、母函数、递推关系、容斥原理、,Burnside,引理、,Polya,定理,第一章 排列与组合,1.1,排列与组合,1.2,排列组合的生成算法,1.3,组合意义的解释与应用举例,1.1,排列与组合,加法法则和乘法法则,一一对应,排列、组合,圆周排列,可重排列,可重组合,不相邻的组合,1.,加法法则与乘法法则,加法法则：,设具有性质,A,的事件有,m,个，具有性质,B,的事件有,n,个，则具有性质,A,或,B,的事件有,m+n,个,。,若,|,A,| =,m, |,B,| =,n,A,B,= ,则,|,A,B,| =,m + n,。,集合论语言：,基本假设：性质,A,和性质,B,是,无关,的两类。,例,1,某班选修企业管理的有,18,人，不选的有,10,人，则该班共有,18 + 10 = 28,人。,例,2,假设要从北京坐飞机或者火车或者客车到上海。北京每天到达上海的飞机有,5,个航班，火车有,7,趟，客车有,10,趟， 则每天由北京到达上海的旅行方式有,5 + 7 + 10 = 22,种。,乘法法则：,设具有性质,A,的事件有,m,个，具有性质,B,的事件有,n,个，则具有性质,A,和,B,的事件有,mn,个,。,若,|,A,| =,m, |,B,| =,n,A,B,= (,a,b,) |,a,A,b,B,则,|,A,B,| =,mn,。,集合论语言：,例,3,从,A,到,B,有三条道路，从,B,到,C,有两条道路，则从,A,经,B,到,C,有,3,2 = 6,条道路。,加法法则：得到事件通过,两种不同的方法,。,乘法法则：得到事件通过,两个步骤,。,例,4,某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有,4,2 = 8,种着色方案。,若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是,4 4 = 16,， 而只有,4 3 = 12,种。,例,5,(1),求小于,10000,的含,1,的正整数的个数；,(2),求小于,10000,的含,0,的正整数的个数。,(1),小于,10000,的不含,1,的正整数可看做,4,位数，但,0000,除外,.,故有,9999,1,6560,个。,含,1,的有：,9999,6560=3439,个，,另：全部,4,位数有,10,4,个，不含,1,的四位数有,9,4,个，,含,1,的,4,位数为两个的差：,10,4,9,4,= 3439,个。,9999,7380=2619.,9+9 +9,+9,=(9,1)/(9,1)=7380,2,3,4,5,(2),“,含,0”,和“含,1”,不可直接套用,。,0019,含,1,但不含,0,。,不含,0,的,1,位数有,9,个，,2,位数有,9,2,个，,3,位数有,9,3,个，,4,位数有,9,4,个。,不含,0,小于,10000,的正整数有,含,0,小于,10000,的正整数有,(1) 435,60,；,(2) 63,18,个位数有,5,种取法，千位数有,8,种取法，百位，十位各有,8,，,7,种取法。,5887,2240,。,例,6,(1),n,=7,3,*11,2,*13,4,，求除尽,n,的数的个数；,(2),n,=7,3,*14,2,，求除尽,n,的数的个数；,例,7,在,1000,和,9999,之间有多少每位上的数字均不同的奇数？,例,8,由,a,b,c,d,e,这,5,个字符，从中取,6,个构成字符串，要求,(1),第,1,，,6,个字符必为子音字符,b,，,c,，,d,；,(2),每个字符串必有两个母音字符,a,或,e,，且两个母音字符不相邻；,(3),相邻的两个子音字符必不相同。求满足这样的条件的字符串的个数。,由条件,(1),，两个母音字符的位置不能在,1,，,6,，,又由条件,(2),，位置只能是,(2,4),(2,5),和,(3,5),之一。,对每种格式，母音,22,，相邻子音,32,，其他两个,子音,33,。因此答案为,3,（,223233,）,=648,。,如我们说,A,集合有,n,个元素,|,A,|=,n,，无非是建立了将,A,中元与,1,n,元一一对应的关系。,在组合计数时往往借助于一一对应实现模型转换。,比如要对,A,集合计数，但直接计数有困难，于是可,设法构造一易于计数的,B,，使得,A,与,B,一一对应,。,2.,一一对应,“一一对应”概念是一个在计数中极为基本的概,念。一一对应既是单射又是满射。,一种常见的思路是按轮计场，费事。,另一种思路是淘汰的选手与比赛,(,按场计,),集一一对应。,63,场比赛。,例,9,在,64,名选手之间进行淘汰赛,(,即一场的比赛结果，失败者退出比赛,),最后产生一名冠军，问要举行几场比赛？,可以先计算对角线的个数，然后计算交点，但是存在在多边形内无交点的情形，比较复杂,。,可以考虑对应关系：多边形内交点,to,多边形四个顶点。,可以证明这是一一映射（映射，单且满）。,例,10,设凸,n,边形的任意三条对角线不共点，求对角线在多边形内交点的个数。,排列的典型例子是取球模型：从,n,个不同的球中,取出,r,个,放入,r,个不同的盒子里，每盒,1,个。,第,1,个盒子有,n,种选择,第,2,个有,n,-1,种选择，,，第,r,个有,n,-,r,+1,种选择。故由乘法法则有,3.,排列、组合,定义：,从,n,个不同的元素中，取,r,个不重复的元素，按次序排列，称为从,n,个中取,r,个的,无重排列,。排列的个数用,P,(,n,r,),表示。,当,r = n,时称为,全排列,。,P,(,n,r,) =,n,(,n,-1)(,n-r,+1) =,n,!/(,n-r,)!,P,(,n,n,)=,n,!,例,11,由,5,种颜色的星状物，,20,种不同的花排列成如下图案：两边是星状物，中间是,3,朵花，问共有多少种这样的图案？,两边是星状物，从五种颜色的星状物中取两个的排列的排列数是,P,(5,2)=20,。,20,种不同的花取,3,种排列的排列数是,根据乘法法则得图案数为,P,(20,3)=20,19,18=6840,。,20,6840=136800,。,接上例，若,A,单位的,2,人排在队伍两端，,B,单位的,3,人不能相邻，问有多少种不同的排列方案？,B,单位,3,人按一个元素参加排列，,P,(8,8),P,(3,3),。,A,单位的人排法固定后,A*A*A*A*A*A*A,，,B,单位第一人有,6,种选择，第二人有,5,种，第三人有,4,种，因此答案为,P,(7,7)654,。,例,12,A,单位有,7,名代表，,B,单位有,3,位代表，排成,一列合影要求,B,单位的,3,人排在一起，问有多少种,不同的排列方案。,例,13,试求由,1,3,5,7,组成的所有不重复出现的整数的总和。,这样的整数可以是,1,位数,2,位数,3,位数,4,位数，若设,是,i,位数的总和，则,S,=,S,1,+,S,2,+,S,3,+,S,4,S,1,=1+3+5+7=16,；,于是我们只需要计算,S,i,即可。,S,4,=6(1+3+5+7)1000+6(1+3+5+7)100+6(1+3+5+7)10 +6(1+3+5+7)=96000+9600+960+96=106656,；,S,=16+528+10656+106656=117856,。,S,2,=3(1+3+5+7)10+3(1+3+5+7)= 480+48=528,；,S,3,=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7),=9600+960+96=10656,；,组合的个数用,C,(,n,r,),表示。,或者用 表示。,定义：,从,n,个不同元素中取,r,个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从,n,个中取,r,个的,无重组合,。,C,(,n,r,)=0,，若,n,n,则,N,= 0;,(2),若,r = n,则,N,=,(3),若,r,n ,且对所有的,i, ,则,(4),若,r,n ,且存在,i,n,i,r,则对,N,没有一般的求解公式，具体解法以后再说。,定理：,从 中取,r,个作可重的组合，其个数为,C,(,k+r,-1,r,),。,6.,可重组合,r,个相同的球,/,001001100, /, ,/,k,-1,个相同的盒壁,而后一问题又可转换为,r,个相同的球与,k,-1,个相同,的盒壁的排列的问题。,则所求计数为,C,(,k+r,-1,r,),。,这个计数问题相当于,r,个相同的球放入,k,个不同的盒子里，个数没有限制的计数。,另证：,不妨假设,k,个不同元素为,1,2,k,，设某一个,r,可重组合为,b,1,b,2,b,r,。由于允许重复，可以假设,这相当于从,1,到,k+r,-1,中取,r,个不允许重复的组合。很容易验证，这是一个一一对应，从而定理成立。,第二个证明可说一种,“拉伸压缩”,技巧。不可谓不巧妙。但仍不如第一证明来的明快，由此可见,组合证明,的功效。,任取一个所求的,r,组合，从中拿走每个元素一个就得到,S,的一个,r-k,组合，反之,对于,S,的一个,r-k,组合，加入元素,a,1,a,2,a,k,就得到所求组合，所以其组合数即为,S,的,r-k,可重组合数。,设,则,S,的,r,-,组合数,N,满足：,(4),若,r,n ,且存在,i,n,i,n,则,N,=0;,(2),若,r = n,则,N,=1;,(3),若,r,n ,且对所有的,i, ,则,N,=,C,(,k+r-,1,r,);,典型模型：,定理：,线性方程,的非负整数解的个数为,C,(,k+r,-1,r,),。,取,r,个无区别的球放进,k,个有标志的盒子，每个盒,子中的球的数目不加限制,允许重复的组合数即,其方案数。,定理,：,从,1,2,n,中取,r,个作不相邻的组合，其个数为,C,(,n-r,+1,r,),。,7.,不相邻的组合,不相邻的组合,是指从,1,2,n,中取,r,个，不允许重复且不存在相邻的数同时出现的组合。,设某一个不相邻组合为,b,1,b,2,b,r,，可以假设,b,1,b,2,b,r,而且相邻两项至少相差,2,。,这相当于从,1,到,n-r,+1,中取,r,个不允许重复的组合。很容易验证，这是一个一一对应，从而定理成立。,