第一章 排列与组合

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 排列与组合,1.1 加法法则与乘法法则,-,是解决计数问题的两个最基本和最常用的规则,1.1,加法法则,若具有性质,A,的事件有,m,个，具有性质,B,的事件有,n,个，则具有性质,A,或,B,的事件数为,m+n,。,集合论语言描述：,若,|,A|=m,|B|=n,A,B=,则,|,AB|=m+n=|A|+|B|。,一般地,设,S,为有限集,将,S,分解为互不相交的子集,S,1,S,2,S,m,的并,S,i,为具有性质,A,i,的事件的集合,i=1,2,m,则,S,中事件的个数为,|S|=|S,1,|+|S,2,|+|,S,m,|.,例,1,某班选修人工智能的有 18 人，不选的有 10 人，则该班共有,18+10=28 人。,例,2,北京每天直达上海的客车有 5 次，客机有 3 次，则每天由北京直达上海的旅行方式有,5+3=8 种。,二、,乘法法则,若具有性质,A,的事件有,m,个，具有性质,B,的事件有,n,个，则具有性质,A,与,B,的事件数有,m n,个,。,集合论语言：,若,|,A|=m,|B|=n,A,B=(a,b)|a A,b B,则,|,A B|=m,n。,一般地，设,S=S,1,S,2,S,m,=(a,1,a,2,a,m,)|a,i,S,i,i,=1,2,m,则,|S|=|S,1,|S,2,|,S,m,|,。,例,3,某种字符串由两个字符组成，第一个字符可选自,a，b，c，d，e,，,第二个字符可选自1，2，3，则这种字符串共有,5,3=15 个。,例,4,从,A,到,B,有三条道路，从,B,到,C,有两条道路，则从,A,经,B,到,C,有,3,2=6 条道路。,例,5,某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有4,2 =8种着色方案。,若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是4 4=16，而只有 4 3=12 种。,在乘法法则中要注意事件,A,和事件,B,的相互独立性。,例,6,求小于10000的含1的正整数的个数,解：,小于10000的不含1的正整数可看做4位数,但0000除外，故有999916560个.从而含1的有：99996560=3439个。,另:全部4位数有10,4,个,不含1的四位数有9,4,个,含1的4位数为两个的差:10,4,9,4,=3439,个,三、计数问题,分两类：,1),计算事物的有序安排或选择数,a,、不允许任何事物重复,b,、允许事物重复,2),计算事物的无序安排或选择数,a,、不允许任何事物重复,b,、允许事物重复,如何区分事物的重复或不重复？,利用集合与重集的安排或选择的说法加以区别。,集合：元素一定不相同,重集：元素可以相同,例如，集合,A=,a,b,c,d,重集,B=,a,a,b,b,b,c,d,d,d,d,=2,a,3,b,1,c,4,d,。,一般地，重集,B=k,1,b,1,k,2,b,2,k,n,b,n,其中，,k,i,为元素,b,i,的重复次数，,i=1,2,n,。,如对某元素没有限制，则在重集中该元素,可以出现无限次，即,k,i,=,。,1.2 排列,一、线排列,从,n,个不同元素的集合中，取,r,个不重复的元素，按次序排成一列，称为从,n,个中取,r,个的,一个排列，又称为,A,的,r-,排列,。,所有,r-,排列的个数用,P(n,r),表示。当,r=n,时称为,全排列,。,规定：,一些重要的结果：,1),2),当,nr,2,时，,P(n,r,)=nP(n-1,r-1);,3)P(n,r)=rP(n-1,r-1)+P(n-1,r),例,1,将具有,9,个字母的单词,FRAGMENTS,进行排列，要求字母,A,总是紧跟字母,R,的右边，问有多少种排法？,例,2,求,20000,到,70000,间的偶数中由不同的数字组成的,5,位数的个数。,例,3,求有多少个,5,位数，每位数字都不相同，不能取,0,，且数字,7,和,9,不相邻。,二、圆排列,从,n,个不同元素的集合中取出,r,个元素按某顺序排成一个圆圈，这样的排列称为圆排列，所有圆排列的个数记为,Q(n,r,),。,Q(n,r,),与,P(n,r,),间的关系,Q(n,n,)=(n-1)!.,例,3,有,8,人围圆桌就餐，问有多少种就座方式？如有两人不愿意坐在一起，又有多少种坐法？,例,4,有,4,男,4,女围圆桌交替就座有多少种方式？,三、重排列,从重集,B=k,1,b,1,k,2,b,2,k,n,b,n,中选取,r,个元素按一定的顺序排成一列，称为重排列。,结论：,1),重集,B=,b,1,b,2,b,n,的,r-,排列的个数为,n,r,。,2),重集,B=n,1,b,1,n,2,b,2,n,k,b,k,的全排列的个数为,其中 。,例,5,由,1,2,3,4,5,6,这几个数字组成多少个,5,位数？可组成多少个大于,34500,的,5,位数？,例,6,用字母,A,、,B,、,C,组成,5,个字母的符号，要求在每个符号里，,A,至多出现,2,次，,B,至多出现,1,次，,C,至多出现,3,次，求此类符号的个数。,1.,3,组合,一、不允许重复,从,n,个不同元素的集合,A,中取,r,个且不考虑其元素的顺序组合起来，称为从,n,中取,r,个的,组合,，或,A,的,r-,组合，它是,A,的,r-,无序子集。,A,的所有,r-,组合的个数记为,C(n,r,),或,C,n,r,或,。,规定：,几个重要的结论：,1),2)C(n,r)=,C(n,n-r,);,C(n,r,)=C(n-1,r)+C(n-1,r-1)-Pascal,公式,=C(n-1,r-1)+C(n-2,r-1)+C(r-1,r-1).,例,1,某班要从,7,名女生和,4,名男生中产生一个班委会，问有多少种方式？若,(1),这个班委员有,5,人，其中,3,女、,2,男。,(2),这个班委员有,4,人，其中至少,2,名女生。,(3),这个班委员有,4,人，其中之一为指定某同学。,例,2,数,510510,能被多少个不同的奇数整除？,二、允许重复的组合,从重集,B=k,1,b,1,k,2,b,2,k,n,b,n,中选取,r,个元素，不考虑它们的次序组织在一起称为从,B,中取,r,个元素的重组合，所有重组合的个数记为,F(n,r,),。,结论：,B=,b,1,b,2,b,n,的,r-,组合数为,F(n,r,)=C(n+r-1,r),。,例,3,某餐厅有,7,种不同的菜，为招待朋友，一个顾客需要买,14,个菜，问有多少种买法？,例,4,求,n,个无区别的球放入,r,个有标志的盒子里,(,nr,),而无一空盒的方式数。,例,5,求方程,x,1,+x,2,+,x,n,=r,的非负整数解的个数。,三、不相邻组合,从集合,A=a,1,a,2,a,n,中取,r,个，不存在,a,i,a,i+1,两个相邻元素出现在同一个组合中的组合，称为,r-,不相邻组合。,结论：,从,A=a,1,a,2,a,n,中取,r,个作不相邻的组合，其个数为：,C(n-r+1,r),。,1.,4,二项式定理,当,n,为正整数时,对任意,x,与,y,有,2.,以上公式的推广形式,:,对,R,对满足,|,x/y,|1,的所有,x,和,y,有,其中,几个推论,:,对,|x|1,的任何,x,有,1),2),1.,5,常用组合恒等式,对正整数,m,n,k,p,有,1.,6,应用举例,例,1,将,n,个有区别的球放入,k,个有区别的盒子中,盒内有序的放法有多少种,?,例,2,某售票处有,5,个窗口,现有,8,个人,他们排队购票的方案有多少种,?,例,3,证明下图中从,O,到,A,的路径数为,例,4,给出以下等式的组合意义,