排列组合常见题型及解题策略(详解)10
可重复的排列求幂法:重复排列问题要区分两类元素:一类可以重复,另一类不能重复,把不能重复的元素看作“客”,能重复的元素看作“店”,则通过“住店法”可顺利解题,在这类问题使用住店处理的策略中,关键是在正确判断哪个底数,哪个是指数【例1】(1)有4名学生报名参加数学、物理、化学竞赛,每人限报一科,有多少种不同的报名方法?(2)有4名学生参加争夺数学、物理、化学竞赛冠军,有多少种不同的结果?(3)将3封不同的信投入4个不同的邮筒,则有多少种不同投法?【解析】:(1)3^{4}(2)4^{3}(3)4^{3}【例2】把6名实习生分配到7个车间实习共有多少种不同方法?【解析】:完成此事共分6步,第一步; 相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一个组,当作一个大元素参与排列.【例1】A,B,C,D,E五人并排站成一排,如果A,B必须相邻且B在A的右边,那么不同的排法种数有_【解析】:把A,B视为一人,且B固定在A的右边,则本题相当于4人的全排列,A_{4}^{4}=24种【例2】(2009四川卷理)3位男生和3位女生共6位同学站成一排,若男生甲不站两端,3位女生中有且只有两位女生相邻,则不同排法的种数是()A.360B.188C.216D.96【解析】:间接法6位同学站成一排,3位女生中有且只有两位女生相邻的排法有,C_{3}^{2}A_{2}^{2}A_{4}^{2}A_{2}^{2} 元素分析法(位置分析法):某个或几个元素要排在指定位置,可先排这个或几个元素;再排其它的元素。【例1】2010年广州亚运会组委会要从小张、小赵、小李、小罗、小王五名志愿者中选派四人分别从事翻译、导游、礼仪、司机四项不同工作,若其中小张和小赵只能从事前两项工作,其余三人均能从事这四项工作,则不同的选派方案共有()A.36种B.12种C.18种D.48种【解析】:方法一:从后两项工作出发,采取位置分析法。A_{3}^{2}A_{3}^{3}=36方法二:分两类:若小张或小赵入选,则有选法C_{2}^{1}C_{2}^{1}A_{3}^{3}=24;若小张、小赵都入选,则有选法A_{2}^{2}A_{3}^{2}=12,共有选法36种,选A. 定序问题缩倍法(等几率法):在排列问题中限制某几个元素必须保持一定的顺序,可用缩小倍数的方法.【例1】.A,B,C,D,E五人并排站成一排,如果B必须站在A的右边(A,B可以不相邻)那么不同的排法种数是()【解析】:B在A的右边与B在A的左边排法数相同,所以题设的排法只是5个元素全排列数的一半,即\frac {1}{2}A_{5}^{5}=60【例2】书架上某层有6本书,新买3本插进去,要保持原有6本书的顺序,有多少种不同的插法?【解析】:法一:法二:\frac {1}{A_{6}^{6}}A_{9}^{9}【例3】将A、B、C、D、E、F这6个字母排成一排,若A、B、C必须按A在前,B居中,C在后的原则(A、B、C允许不相邻),有多少种不同的排法? 标号排位问题(不配对问题)把元素排到指定位置上,可先把某个元素按规定排入,第二步再排另一个元素,如此继续下去,依次即可完成.【例1】将数字1,2,3,4填入标号为1,2,3,4的四个方格里,每格填一个数,则每个方格的标号与所填数字均不相同的填法有()A、6种B、9种C、11种D、23种【解析】:先把1填入方格中,符合条件的有3种方法,第二步把被填入方格的对应数字填入其它三个方格,又有三种方法;第三步填余下的两个数字,只有一种填法,共有3 \times 3 \times 1=9种填法,选B.【例2】编号为1、2、3、4、5的五个人分别去坐编号为1、2、3、4、5的五个座位,其中有且只有两个的编号 不同元素的分配问题(先分堆再分配);注意平均分堆的算法【例1】有6本不同的书按下列分配方式分配,问共有多少种不同的分配方式?(1)分成1本、2本、3本三组;(2)分给甲、乙、丙三人,其中一个人1本,一个人2本,一个人3本;(3)分成每组都是2本的三个组;(4)分给甲、乙、丙三人,每个人2本;(5)分给5人每人至少1本。【解析】:(1)C_{6}^{1}C_{5}^{2}C_{3}^{3}(2)C_{6}^{1}C_{5}^{2}C_{3}^{3}A_{3}^{3}(3)\frac {C_{6}^{2}C_{4}^{2}C_{2}^{2}}{A_{3}^{3}}(4)C_{6}^{2}C_{4} 相同元素的分配问题隔板法:【例1】:把20个相同的球全放入编号分别为1,2,3的三个盒子中,要求每个盒子中的球数不少于其编号数,则有多少种不同的放法?【解析】:向1,2,3号三个盒子中分别放入0,1,2个球后还余下17个球,然后再把这17个球分成3份,每份至少一球,运用隔板法,共有C_{16}^{2}=120种。【例2】10个三好学生名额分到7个班级,每个班级至少一个名额,有多少种不同分配方案?【解析】:10个名额分到7个班级,就是把10个名额看成10个相同的小球分成7堆,每堆至少一个,可以在10个小球的9个空位中插入6块木板,每一种插法对应着一种分配方案,故共有不同的分配方案为C_{9}^{6}=84种. 多面手问题(分类法---选定标准)【例1】:有11名外语翻译人员,其中5名是英语译员,4名是日语译员,另外两名是英、日语均精通,从中找出8人,使他们可以组成翻译小组,其中4人翻译英语,另4人翻译日语,这两个小组能同时工作,问这样的8人名单可以开出几张?C_{5}^{4}C_{4}^{4}+C_{5}^{3}C_{2}^{1}C_{4}^{4}+C_{5}^{4}C_{2}^{1变式:.有11名外语翻译人员,其中有5名会英语,4名会日语,另外两名英,日语都精通,从中选出8人,组成两个翻译小组,其中4人翻译英语,另4人翻译日语,问共有多少不同的选派方式?答案:185 染色问题:涂色问题的常用方法有:(1)可根据共用了多少种颜色分类讨论;(2)根据相对区域是否同色分类讨论;(3)将空间问题平面化,转化成平面区域涂色问题。【例1】将一个四棱锥S-ABCD的每个顶点染上一种颜色,并使同一条棱的两端点异色,如果只有5种颜色可供使用,那么不同的染色方法的总数是_【解析一】满足题设条件的染色至少要用三种颜色。(1)若恰用三种颜色,可先从五种颜色中任选一种染顶点S,再从余下的四种颜色中任选两种涂A、B、C、D四点,此时只能A与C、B与D分别同色,故有C_{5}^{1}A_{4}^{2}=60种方法。(2)若恰用四种颜色 “至多”“至少”问题用间接法或分类:十三.几何中的排列组合问题:【例1】已知直线\frac {x}{a}+\frac {y}{b}=1b是非零常数)与圆x^{2}+y^{2}=100有公共点,且公共点的横坐标和纵坐标均为整数,那么这样的直线共有_条【解析】:圆上的整点有:(\pm 6, \pm 8),(\pm 8, \pm 6),(\pm 10,0),(0 \pm 10)12个C_{12}^{2}=66其中关于原点对称的有4条不满则条件切线有C_{12}^{1}=12,其中平行于坐标轴的有14条不满则条件66-4+12-14=60答案:60