排列组合题型大全

第六节排列与组合(理)重点难点重点：1.两个计数原理的理解和应用．2．排列与组合的定义、计算公式，组合数的两个性质．难点：1.如何区分实际问题中的“类”与“步”．2．组合数的性质和有限制条件的排列组合问题．知识归纳1．分类计数原理完成一件事，有两类不同方案，在第1类方案中有m种不同的方法，在第2类方案中有n种不同的方法，那么完成这件事共有N＝m＋n种不同的方法．2．分步计数原理完成一件事，需要分成两个步骤，做第一步有m种不同的方法，做第二步有n种不同的方法，那么完成这件事共有N＝m×n种不同的方法．3．排列从n个不同元素中，取出m(m≤n)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列．所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号Amn表示．(1)当mn时的排列称为选排列，排列数Amn＝n(n－1)×…×(n－m＋1)＝n！n－m！.(2)当m＝n时的排列称为全排列，排列数Ann＝n(n－1)×…×3×2×1＝n！.规定0！＝1.4．组合从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数．用符号Cmn表示．(1)Cmn＝AmnAmm＝nn－1n－2·…·n－m＋1m！＝n！m！n－m！.规定：C0n＝1.(2)Cmn＝Cn－mn；Cmn＋1＝Cmn＋Cm－1n.误区警示1．正确区分“分类”与“分步”，恰当地进行分类，使分类后不重、不漏．2．正确区分是组合问题还是排列问题，要把“定序”和“有序”区分开来．3．正确区分分堆问题和分配问题一、“分类”与“分步”，应该如何理解与区分(1)分类：“做一件事，完成它可以有两类办法”．每一类办法中的每一种方法都能将这件事完成．分类时，首先据问题特点确定一个合理的分类标准，在这个“标准”下分类能够做到“不重不漏”．①完成这件事的任何一种方法必须属于其中的某一类．(不漏)②分别在不同两类中的两种方法不能相同．(不重复)(2)分步要做到“步骤完整”，完成了所有步骤，恰好完成任务．步与步之间要相互独立．必须并且只需连续完成这些步骤后，这件事才算最终完成．所以区分一种分法是分类还是分步就看这种分法中的．．．．．．一种方法能否完成这件事情．．．．．．．．．．．．．．二、排列、组合问题的类型及解答策略排列、组合问题，通常都是以选择题或填空题的形式出现在试卷上，它联系实际，生动有趣；但题型多样，解法灵活．实践证明，备考有效的方法是将题型与解法归类，识别模式、熟练运用．下面介绍常见排列组合问题的解答策略．(1)相邻元素捆绑法．在解决某几个元素必须相邻问题时，可整体考虑将相邻元素视为一个元素参与排列．[例1](2010·重庆理，9)某单位安排7位员工在10月1日至7日值班，每天安排1人，每人值班1天．若7位员工中的甲、乙排在相邻两天，丙不排在10月1日，丁不排在10月7日，则不同的安排方案共有()A．504种B．960种C．1008种D．1108种分析：甲、乙相邻看作一个元素与其它元素一块排，由于丙不排在第1天也不排在第7天，因此按甲乙的排位进行分类．解析：甲、乙相邻的所有方案有A22A66＝1440种；其中丙排在10月1日的和丁排在10月7日的一样多，各有：A22A55＝240种，其中丙排在10月1日且丁排在10月7日的有A22A44＝48种，故符合题设要求的不同安排方案有：1440－2×240＋48＝1008种，故选C.答案：C(2)相离问题插空法．相离问题是指要求某些元素不能相邻，由其它元素将它隔开，此类问题可以先将其它元素排好，再将所指定的不相邻的元素插入到它们的空隙及两端位置，故称“插空法”．[例2](2011·湘潭期末)2010年上海世博会某国将展出5件艺术作品，其中不同书法作品2件、不同绘画作品2件、标志性建筑设计1件，在展台上将这5件作品排成一排，要求2件书法作品必须相邻，2件绘画作品不能相邻，则该国展出这5件作品不同的方案有________种．(用数字作答)解析：将两件书法作品排在一块看作“一件”作品与标志性建筑设计一块排好，有A22·A22种排法，在上述“两件”作品形成的三个空档中插入绘画作品，有A23种插法．∴共有不同展出方案A22A22·A23＝24种．答案：24(3)定序问题属组合．排列时，如果限定某些元素或所有元素保持一定顺序称为定序问题，定序的元素属组合问题．[例3]6个人排一队参观某项目，其中甲、乙、丙三人进入展厅的次序必须是先乙，再甲，最后丙，则不同的列队方式有________种．解析：解法1：由于甲、乙、丙三人的次序已定，故只须从6个位置中选取3个排上其余3人，有A36种排法，剩下的三个位置排甲、乙、丙三人，只有一种排法，∴共有A36＝120种．解法2：先选取3个位置排甲、乙、丙三人有C36种方法，剩下3个位置站其余3人，有A33种方法，∴共有C36·A33＝120种．答案：120(4)定元、定位优先排．在有限制条件的排列、组合问题中，有时限定某元素必须排在某位置，某元素不能排在某位置；有时限定某位置只能排(或不能排)某元素．这种特殊元素(位置)解题时要优先考虑．[例4](2010·山东理)某台小型晚会由6个节目组成，演出顺序有如下要求：节目甲必须排在前两位，节目乙不能排在第一位，节目丙必须排在最后一位，该台晚会节目演出顺序的编排方案共有()A．36种B．42种C．48种D．54种分析：丙占最后一位不必考虑．“甲在前两位，乙不在第一位”，故应以甲为标准进行分类．解析：若甲在第一位有A44＝24种方法；若甲在第二位有C13A33＝18种方法，故共有18＋24＝42种方法．答案：B(5)至多、至少间接法．含“至多”、“至少”的排列组合问题，是需要分类问题．可用间接法，即排除法，但仅适用于反面情况明确且易于计算的情况．[例5](2011·丽水月考)从6名男生和2名女生中选出3名志愿者，其中至少有1名女生的选法共有()A．36种B．30种C．42种D．60种解析：解法1(直接法)：选出的3名志愿者中含1名女生有C12·C26种选法，含2名女生有C22·C16种选法，∴共有C12C26＋C22C16＝36种选法．解法2(间接法)：若选出的3名全是男生，则有C36种选法，∴至少有一名女生的选法数为C38－C36＝36种．答案：A(6)选排问题先选后排法．对于排列组合的混合应用题，一般解法是先选(组合)后排(排列)．[例6]四个不同的小球放入编号为1,2,3,4的四个盒子中，则恰有一个空盒的放法共有________种(用数字作答)．解析：先从四个小球中取两个放在一起，有C24种不同的取法，再把取出的两个小球与另外两个小球看作三堆，并分别放入四个盒子中的三个盒子中，有A34种不同的放法，据分步计数原理，共有C24·A34＝144种不同的放法．答案：144(7)部分符合条件淘汰法．在选取总数中，只有一部分符合条件，可从总数中减去不符合条件数，即为所求．[例7]过三棱柱任意两个顶点的直线共15条，其中异面直线有()A．18对B．24对C．30对D．36对解析：三棱柱共6个顶点，由此6个顶点可组成C46－3＝12个不同四面体，而每个四面体有三对异面直线则共有12×3＝36对．答案：D(8)数字问题要弄清可否重复及首位不能为0[例8]用0到9这10个数字，可以组成没有重复数字的三位偶数的个数为()A．324B．328C．360D．648解析：利用分类计数原理，共分两类：(1)0作个位，共A27＝72个偶数；(2)0不作个位，共A14·A18·A18＝256个偶数，共计72＋256＝328个偶数，故选B.答案：B三、建模思想[例9]一只电子蚂蚁在如图所示的网格线上由原点O(0,0)出发，沿向上或向右方向爬至点(m，n)，(m，n∈N*)，记可能的爬行方法总数为f(m，n)，则f(m，n)＝________.解析：从原点O出发，只能向上或向右方向爬行，记向上为1，向右为0，则爬到点(m，n)需m个0和n个1.这样爬行方法总数f(m，n)是m个0和n个1的不同排列方法数．m个0和n个1共占m＋n个位置，只要从中选取m个放0即可．∴f(m，n)＝Cmm＋n.答案：Cmm＋n点评：①例如f(3,4)＝C37其中0010111表示从原点出发后，沿右右上右上上上的路径爬行．②抽象建模后就是一个含相同数字的纯粹排列组合问题．[例10]方程x＋y＋z＝8的非负整数解的个数为________．解析：把x、y、z分别看作是x个1，y个1和z个1，则共有8个1，问题抽象为8个1和两个十号的一个排列问题．由于x、y、z非负，故允许十号相邻，如11＋＋111111表示x＝2，y＝0，z＝6，[phone]＋表示x＝0，y＝8，z＝0等等，∴不同排法总数为从10个位置中选取2个放十号，∴方程的非负整数解共有C210＝45个．答案：45[例11]一条街道上共有12盏路灯，为节约用电又不影响照明，决定每天晚上十点熄灭其中的4盏，并且不能熄灭相邻两盏也不能熄灭两头两盏，问不同熄灯方法有多少种．解析：记熄灭的灯为0，亮灯为1，则问题是4个0和8个1的一个排列，并且要求0不相邻，且不排在两端，故先将1排好，在8个1形成的7个空中，选取4个插入0，共有方法数C47＝35种．点评：实际解题中，先找出符合题设条件的一种情形，然后选取一种替代方案，注意是否相邻、相间等受限条件，然后确定有无顺序是排列还是组合，再去求解．[例12]如图，从上往下读(不能跳读)构成句子“构建和谐社会，创美好未来”的不同读法种数是()构建建和和和谐谐谐谐社社社社社会会会会会会创创创创创美美美美好好好未未来A．250B．240C．252D．300解析：要组成题设中的句子，则每行读一字，不能跳读．每一种读法须10步完成(从上一个字到下一个字为一步)，其中5步是从左上角到右下角方向读的，故共有不同读法C510＝252种．答案：C四、枚举法[例13]如果直线a与b异面，则称a与b为一对异面直线，六棱锥的侧棱与底边共12条棱所在的直线中，异面直线共有________对．解析：六棱锥的侧棱都相交，底面六条边所在直线都共面，故异面直线只可能是侧棱与底面上的边．考察PA与底面六条边所在直线可用枚举法列出所有异面直线(PA，BC)，(PA，CD)，(PA，DE)，(PA，EF)共四对．同理与共它侧棱异面的底边也各有4条，故共有4×6＝24对．答案：24[例1]若直线方程ax＋by＝0中的a、b可以从0,1,2,3,5这五个数字中任取两个不同的数字，则方程所表示的不同直线一共有________条．分类加法计数原理解析：分两类：第一类，a、b均不为零，a、b的取值共有A24＝12种方法．第二类：a、b中有一个为0，则不同的直线仅有两条x＝0和y＝0.∴共有不同直线14条．答案：14(2010·湖南考试院调研)从5位男生，4位女生中选派4位代表参加一项活动，其中至少有两位男生，且至少有1位女生的选法共有()A．80种B．100种C．120种D．240种解析：分两类，第一类是2男2女，有C25·C24种方法，第二类是3男1女，有C35C14种方法，∴共有C25C24＋C35C14＝100种方法．答案：B分步乘法计数原理[例2]如图所示，用五种不同的颜色分别给A、B、C、D四个区域涂色，相邻区域必须涂不同颜色，若允许同一种颜色多次使用，则不同的涂色方法共有()A．180种B．120种C．96种D．60种解析：按区域分四步：第一步A区域有5种颜色可选；第二步B区域有4种颜色可选；第三步C区域有3种颜色可选；第四步D区域也有3种颜色可选．由分步计数原理，共有5×4×3×3＝180(种)．答案：A点评：课标要求掌握分类计数原理与分步计数原理，并能用它们分析和解决问题，这就要求我们不仅要准确地理解两个基本原理，更要能灵活地运用两个原理分析和解决问题，运用两个原理解题的关键在于正确区分“类”与“步”．(2010·山东日照模考)某校园有一椭圆型花坛，分成如图四块种花，现有4