排列组合的应用

2.给图中区域涂色,要求相邻区域不同色,现有4种可选颜色,则不同的着色方法有种.2134572基本原理组合排列排列数公式组合数公式组合数性质应用问题知识结构1、掌握优先处理元素（位置）法；2、掌握捆绑法；3、掌握插空法。4、隔板法5、分组分配问题：1、是否均匀；2、是否有组别。一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数.分析:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置先排末位共有___然后排首位共有___最后排其它位置共有___13C13C14C14C34A34A由分步计数原理得13C14C34A位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法,若以元素分析为主,需先安排特殊元素,再处理其它元素.若以位置分析为主,需先满足特殊位置的要求,再处理其它位置.实战演练练习一安排甲，乙，丙三人周一至周六值班，每人值班两天，其中甲不值周一，乙必须值周六，问有多少种不同的安排方法？分析：先安排甲，再安排乙.因甲不值周一，又不能值周六，故甲有种排法，从而此题结论应为种安排方法212432CCC24C例2.（1）7位同学站成一排，共有多少种不同的排法？775040A(2)7位同学站成两排(前3后4)，共有多少种不同的排法？76543217!5040(3)7位同学站成一排，其中甲站在中间的位置,共有多少种不同的排法？66720A(4)7位同学站成一排，甲、乙只能站在两端的排法共有多少种？解:将问题分步第一步:甲乙站两端有种第二步:其余5名同学全排列有种22A55A25252400AA＝共有种答：共有2400种不同的排列方法。(5)7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？解法一:(特殊位置法)第一步:从其余5位同学中找2人站排头和排尾,有种;25A第二步:剩下的全排列,有种;55A25552400AA＝共有种答：共有2400种不同的排列方法。解法二:(特殊元素法)第一步:将甲乙安排在除排头和排尾的5个位置中的两个位置上,有种;25A第二步:其余同学全排列,有种;55A25552400AA＝共有种答：共有2400种不同的排列方法。(5)7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？解法三:(排除法)先全排列有种,其中甲或乙站排头有种,甲或乙站排尾的有种,甲乙分别站在排头和排尾的有种.77A662A662A2525AA7625762542400AAAA＝共有种答：共有2400种不同的排列方法。(5)7位同学站成一排，甲、乙不能站在排头和排尾的排法共有多少种？优限法:对于“在”与“不在”等类似有限制条件的排列问题,常常使用“直接法”(主要为“特殊位置法”和“特殊元素法”)或者“排除法”,即优先考虑限制条件.这种方法就是优限法.例2.七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。若三个女孩要站在一起，有多少种不同的排法？解：将三个女孩看作一人与四个男孩排队，有种排法，而三个女孩之间有种排法，所以不同的排法共有：（种）。5353720AA55A33A捆绑法二.相邻元素捆绑策略若三个女孩要站在一起，四个男孩也要站在一起，有多少种不同的排法？不同的排法有：234234288AAA（种）说一说捆绑法一般适用于问题的处理。相邻例2.七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也必须排列.若三个女孩互不相邻，有多少种不同的排法？解：先把四个男孩排成一排有种排法，在每一排列中有五个空档（包括两端），再把三个女孩插入空档中有种方法，所以共有：（种）排法。35A44A43451440AA插空法例2.七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。三.不相邻问题插空策略元素不相邻问题可先把没有位置要求的元素进行排队，再把不相邻元素插入相应空隙中。男生、女生相间排列，有多少种不同的排法？解：先把四个男孩排成一排有种排法，在每一排列中有五个空档（包括两端），再把三个女孩插入空档中有种方法，所以共有：（种）排法。33A44A4343144AA插空法例2.七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。甲、乙两人的两边必须有其他人，有多少种不同的排法？解：先把其余五人排成一排有种排法，在每一排列中有四个空档（不包括两端），再把甲、乙插入空档中有种方法，所以共有：（种）排法。24A55A52541440AA插空法例2.七个家庭一起外出旅游，若其中四家是一个男孩，三家是一个女孩，现将这七个小孩站成一排照相留念。例2七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩站成两排照相留念。若前排站三人，后排站四人，其中的A.B两小孩必须站前排且相邻，有多少种不同的排法？AB解：A，B两小孩的站法有：（种），其余人的站法有（种），所以共有（种）排法。222A55A48025522AA练习二7人站成一排，其中A、B两人必须相邻，且C、D两人不能相邻有多少种不同的排法？AAA254422种练习三有10个座位，安排给6个人就座，其中空位不相邻的做法有多少种？种实战演练CA4766解：把此问题当作一个排队模型在6个空座的5个空隙中插入3个人有种.练习五某城新建的一条道路上有12只路灯,为了节省用电而不影响正常的照明，可以熄灭其中三盏灯，但两端的灯不能熄灭，也不能熄灭相邻的两盏灯，可以熄灭的方法共有多少种？解：把此问题当作一个排队模型在9盏亮灯的8个空隙中插入3个不亮的灯有种.35A思维转化练习四某排共有9个座位，若3人坐在座位上，每人左右都有空位，则不同的坐法有多少种？38C将n个相同的元素按顺序分成m份，每份至少一个元素,每一种插板方法对应一种分法共有___种分法.四.元素相同问题隔板策略例3有10个运动员名额，在分给7个班，每班至少一个,有多少种分配方案？分析：因为10个名额没有差别，把它们排成一排.在９个空隙中选６个位置插入隔板，可把名额分成７份，对应地分给７个班级，69C11.mnC相邻名额之间形成９个空隙.可以用m-1块隔板插入n个元素排成一排的n-1个空隙中,所有分法数为一班二班三班四班五班六班七班实战演练练习七求方程x+y+z+w=100的正整数解的组数.49C399C练习六10个相同的球装入有编号的5个盒中,每盒至少一个，有多少装法？···五.排列组合混合问题先选后排策略例4有5个不同的小球,装入4个不同的盒内,每盒至少装一个球,共有多少不同的装法?25C44A根据分步计数原理装球的方法共有_____25C44A解决排列组合混合问题,先选后排是最基本的指导思想.解:第一步从5个球中选出2个组成复合元共有__种方法.第二步把4个元素(包含一个复合元素)装入4个不同的盒内有_____种方法.练习九某学习小组有5个男生3个女生，从中选3名男生和1名女生参加三项竞赛活动，每项活动至少有1人参加，则有不同参赛方法多少种.解：采用先组后排方法:练习八从1到7的7个数字中取2个偶数3个奇数，其中2个偶数排在一起，问组成没有重复数字的5位数？解：采用先组后排方法:实战演练AACC44223423AACC44223423ACCC33241335(5).平均分组问题除法策略例5.6本不同的书平均分成3堆,每堆2本共有多少分法？解:分三步取书得种方法,但这里出现重复计数的现象,不妨记6本书为ABCDEF.若第一步取AB,第二步取CD,第三步取EF,该分法记为(AB,CD,EF),则中还有(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有种取法,而这些分法仅是(AB,CD,EF)一种分法,故共有种分法。222642CCC222642CCC33A222642CCC33A平均分成的组,不管它们的顺序如何,都是一种情况,所以分组后要一定要除以(n为均分的组数)避免重复计数。nnA例5.(1)将四个小球分成两组，每组两个，有多少分法？3种六分组问题(2)将四个小球分给两人，每人两个,有多少分法？甲甲乙乙6种(3)将四个小球分成两组，一组三个，一组一个，有多少分法？4种(4)将四个小球分给两人，一人三个,一人一个，有多少分法？甲乙甲乙8种若分成的m组是有组别的，只需在原来的分组基础上再mmA例6.有6本不同的书，分成3堆.（1）如果每堆2本，有多少种分法？（2）如果分成一堆1本，一堆2本，一堆3本，有多少种分法？分析:这与例2不同，区别在于把6本不同的书分给甲、乙、丙3人，每人2本，相当于把6本不同的书先分成3堆，再把分得的3堆分给甲、乙、丙3人.2226423390156CCCA12365360CCC例6.有6本不同的书，分成4堆.（3）如果一堆3本，其余各堆各1本，有多少种分法？（4）如果每堆至多2本，至少1本，有多少种分法？311163213320321206CCCCA221164212222156214522CCCCAA3620C或注意：分组分配问题主要有分组后有分配对象(即组本身有序)的均分与不均分问题及分组后无分配对象(即组本身无序)的均分与不均分问题四种类型，常见的情形有以下几种:rrrrnrrnrnCCCC2(2)均匀、有序分组:把n个不同的元素分成有序的m组，每组r个元素，则共有种分法.(其中mr=n)mmrrrrnrrnrnACCCC2(1)均匀、无序分组:把n个不同的元素分成无序的m组，每组r个元素，则共有种分法.(其mr=n)mmrrrrrnrrnrnCCCC321211(3)非均匀、无序分组:把n个不同的元素分成m组，第1组r1个元素，第2组r2个元素，第3组r3个元素，……第m组rm个元素，则共有种分法.(其中r1+r2+r3+…+rm=n)(4)非均匀、有序分组:把n个不同的元素分成m组，第1组r1个元素，第2组r2个元素，第3组r3个元素，……第m组rm个元素，再分给m个人，则共有种分法.(其中r1+r2+r3+…+rm=n)mmrrrrrnrrnrnACCCCmm321211(5)局部均匀分组:把n个不同的元素分成m组，其中m1个组有r1个元素，m2个组有r2个元素，……mk个组有rk个元素，则共有种分法.(其中m1r1+m2r2+m3r3+…+mkrk=n)kkkkmmmmmmrrrmrnrrmnrrnrnAAACCCCC221121111111)1(练习:9件不同的玩具，按下列方案有几种分法？1.甲得2件，乙得3件，丙得4件，有多少种分法？2.一人得2件，一人得3件，一人得4件，有多少种分法？3.分给甲乙丙，每人3件，有多少种分法？4.平均分成三堆，有多少种分法？5.分为2、2、2、3四堆，有多少种分法？解：①2349741260CCC②234397437560CCCA③3339631680CCC④33396333280CCCA⑤22236429331260CCCCA感悟●分享（一）解决排列组合16字方针是解排列组合的基本规律，即分类相加，分步相乘，有序排列，无序组合.（二）几种解题策略1.特殊元素和特殊位置优先策略2.相邻元素捆绑策略3.不相邻问题插空策略4.元素相同问题隔板策略你掌握了哪些探求问题的方法和数学思想？由特殊到一般类比、归纳、转化例6:从6个学校中选出30名学生参加数学竞赛,每校至少有1人,这样有几种选法?分析:问题相当于把30个相同的球放入6个不同盒子(盒子不能空的)有几种放法?这类问题可用“隔板法”处理.小结：把n个相同元素分成m份，每份至少1个元素，问有多少种不同分法的