解排列组合应用题的解法技巧

解排列组合应用题的解法·技巧引言：1、本资料对排列、组合应用题归纳为8种解法、13种技巧2、解排列组合问题的“16字方针”：分类相加，分步相乘，有序排列，无序组合一般先选再排，即先组合再排列，先分再排。弄清要完成什么样的事件是前提，解决这类问题通常有三种途径新疆王新敞特级教师源头学子小屋@[e-mail]源头学子小屋特级教师王新敞新疆(1)以元素为主，应先满足特殊元素的要求，再考虑其他元素新疆源头学子小屋特级教师王新敞@[e-mail]王新敞特级教师源头学子小屋新疆(2)以位置为主考虑，即先满足特殊位置的要求，再考虑其他位置新疆源头学子小屋特级教师王新敞@[e-mail]王新敞特级教师源头学子小屋新疆即采用“先特殊后一般”的解题原则.(3)先不考虑附加条件，计算出排列或组合数，再减去不符合要求的排列数或组合数新疆源头学子小屋特级教师王新敞@[e-mail]王新敞特级教师源头学子小屋新疆前两种方式叫直接解法，后一种方式叫间接(剔除)解法新疆源头学子小屋特级教师王新敞@[e-mail]王新敞特级教师源头学子小屋新疆注：数量不大时可以逐一排出结果。3、解排列组合问题的依据是：分类相加（每类方法都能独立地完成这件事，它是相互独立的，一次的且每次得出的是最后的结果，只需一种方法就能完成这件事），分步相乘（一步得出的结果都不是最后的结果，任何一步都不能独立地完成这件事，只有各个步骤都完成了，才能完成这件事，各步是关联的），有序排列，无序组合．（一）排列组合应用题的解法排列组合应用题的解题方法既有一般的规律，又有很多特别的技巧，它要求我们要认真地审题，对题目中的信息进行科学地加工处理。下面通过一些例题来说明几种常见的解法。一.运用两个基本原理二.特殊元素（位置）优先三.捆绑法四.插入法五.排除法六.机会均等法七.转化法八.隔板法一.运用两个基本原理加法原理和乘法原理是解排列组合应用题的最基本的出发点，可以说对每道应用题我们都要考虑在记数的时候进行分数或分步处理。例1：n个人参加某项资格考试，能否通过，有多少种可能的结果？解法1：用分类记数的原理，没有人通过，有Cn0种结果；1个人通过，有Cn1种结果，……；n个人通过，有Cnn种结果。所以一共有CCCnnnnn012种可能的结果。解法2：用分步记数的原理。第一个人有通过与不通过两种可能，第二个人也是这样，……，第n个人也是这样。所以一共有2n种可能的结果。例2：同室四人各写了一张贺年卡，先集中起来，然后每人从中拿一张别人的贺年卡，则四张贺年卡不同的分配方式有（）（A）6种（B）9种（C）11种（D）23种解：设四个人分别为甲、乙、丙、丁，各自写的贺年卡分别为a、b、c、d。第一步，甲取其中一张，有3种等同的方式；第二步，假设甲取b，则乙的取法可分两类：（1）乙取a，则接下来丙、丁的取法都是唯一的，（2）乙取c或d（2种方式），不管哪一种情况，接下来丙、丁的取法也都是唯一的。根据加法原理和乘法原理，一共有3129()种分配方式。二.特殊元素（位置）优先----(优待法)所谓“优待法”是指在解决排列组合问题时，对于有限制条件的元素(或位置)要优先考虑．例3：从0，1，……，9这10个数字中选取数字组成偶数，一共可以得到不含相同数字的五位偶数多少个？解：个位选0，有P94个，个位不选0且万位不能选0，有CCP418183个，所以一共可以得到1377638181449PCCP个偶数。注0，2，4，6，8是特殊元素，元素0更为特殊，首位与末位是特殊的位置。例4：8人站成两排，每排4人，甲在前排，乙不在后排的边上，一共有多少种排法？解：先排甲，有P41种排法。再排乙，有P51种排法，再排其余的人，又有P66种排法，所以一共有PPP41516614400种排法。【eg】在由数字0、1、2、3、4、5所组成的没有重复数字的四位数中，不能被5整除的数共有()个．（解法一）元素优先数字0、1、2、3、4、5中含有0元素，组成四位数时，0不能放在首位．又所求四位数不能被5整除，因而可以根据是否含有0和5两个元素将所求四位数分成四类：第一类：含0不含5的四位数，共有=48(个)；第二类：含5不含0的四位数，共有=72(个)；第三类：含0也含5的四位数，共有＝48(个)；第四类：不合0也不含5的四位数，共有＝24(个)．所以，符合条件的四位数共有48+72+48+24=192(个).（解法二）位置优待根据所求四位数对首末两个位置的特殊要求可以分步解答：第一步：排个位——个位上的数字只能从1、2、3、4这四个数字中任选一个，共有种选法；第二步；排首位——首位上的数字只能从1、2、3、4这四个数字被个位选掉后剩余的三个数字及数字5中任选一个，共有种选法；第三步：排中间两位，中间两柱可以从个位和首位排好后剩余的数字四个数字中任选两个，共有种排法．所以符合条件的四位数共有=4×4×4×3=192(个)．〔注〕这道例题是典型的限制排列组合题．解题时，若从元素入手(即元素优先)，常要分类讨论，分类时要注意堵漏防重；若从位置入手(即位置优待1，常要分步解答，分步时要注意分步完整，各步相连．三.捆绑法在解决对于某几个元素要求相邻的问题时，先整体考虑，将相邻元素视作一个大元素进行排序，然后再考虑大元素内部各元素间顺序的解题策略就是捆绑法．例5：8人排成一排，甲、乙必须分别紧靠站在丙的两旁，有多少种排法？解：把甲、乙、丙先排好，有P22种排法，把这三个人“捆绑”在一起看成是一个，与其余5个人相当于6个人排成一排，有P66种排法，所以一共有PP2266=1440种排法。〔注〕运用捆绑法解决排列组合问题时，一定要注意“捆绑”起来的大元素内部的顺序问题．四.插空法不相邻问题是指要求某些元素不能相邻，由其它元素将它们隔开．解决此类问题可以先将其它元素排好，再将所指定的不相邻的元素插入到它们的间隙及两端位置，故称插空法．例6：排一张有8个节目的演出表，其中有3个小品，既不能排在第一个，也不能有两个小品排在一起，有几种排法？解：先排5个不是小品的节目，有P55种排法，它们之间以及最后一个节目之后一共有6个空隙，将3个小品插入进去，有P53种排法，所以一共有PP5553=7200种排法。注：捆绑法与插入法一般适用于有如上述限制条件的排列问题【eg】用1、2、3、4、5、6、7、8组成没有重复数字的八位数，要求1与2相邻，2与4相邻，5与6相邻，而7与8不相邻。这样的八位数共有()个．(用数字作答)解：由于要求1与2相邻，2与4相邻，可将1、2、4这三个数字捆绑在一起形成一个大元素，这个大元素的内部中间只能排2，两边排1和4，因此大元素内部共有种排法，再把5与6也捆绑成一个大元素，其内部也有种排法，与数字3共计三个元素，先将这三个元素排好，共有种排法，再从前面排好的三个元素形成的间隙及两端共四个位置中任选两个，把要求不相邻的数字7和8插入即可，共有种插法，所以符合条件的八位数共有＝288(种)．〔注〕运用插空法解决不相邻问题时，要注意欲插入的位置是否包含两端位置．五.正难则反——排除法对于含“至多”或“至少”的排列组合问题，若直接解答多需进行复杂讨论，可以考虑“总体去杂”，即将总体中不符合条件的排列或组合删除掉，从而计算出符合条件的排列组合数的方法．例7；求以一个长方体的顶点为顶点的四面体的个数。解：从8个点中取4个点，共有C84种方法，其中取出的4个点共面的有6612种，所以符合条件的四面体的个数为C841258个。例8：100件产品中有3件是次品，其余都是正品。现在从中取出5件产品，其中含有次品，有多少种取法？解：从100件产品中取5件产品，有C1005种取法，从不含次品的95件中取出5件产品有C955种取法，所以符合题意的取法有CC100595517347001种。例9：8个人站成一排，其中A与B、A与C都不能站在一起，一共有多少种排法？解：无限制条件有P88种排法。A与B或A与C在一起各有PP2277种排法，A、B、C三人站在一起且A在中间有PP2266种排法，所以一共有P882PP2277+PP2266=21600种排法。【eg】从4台甲型和5台乙型电视机中任意取出3台，其中至少要甲型与乙型电视机各一台，则不同的取法共有()种．A．140种B．80种C．70种D．35种解：在被取出的3台中，不含甲型或不合乙型的抽取方法均不合题意，因此符合题意的抽取方法有=70(种)，故选C．应该指出的是，上述介绍的各种方法并非绝对的。同一问题有时会有多种解法，这时，要认真思考和分析，灵活选择最佳方法．〔注〕这种方法适用于反面的情况明确且易于计算的习题六.机会均等法例10：10个人排成一队，其中甲一定要在乙的左边，丙一定要在乙的右边，一共有多少种排法？解：甲、乙、丙三人排列一共有6种排法，在这6种排法中各种排列顺序在10个人的所有排列中出现的机会是均等的，因此符合题设条件的排法种数为166048001010P。例11：用1，4，5，x四个数字组成四位数，所有这些四位数中的数字的总和为288，求x。解：若x不为0，在每一个数位上1，4，5，x，出现的机会是均等的。由于一共可以得到24个四位数，所以每一个数字在每一个数位上出现6次，于是得到：64145288()x，解得x2。若x为0，无解。七.转化法例12：一个楼梯共10级台阶，每步走1级或2级，8步走完，一共有多少种走法？解：10级台阶，要求8步走完，并且每步只能走一级或2级。显然，必须有2步中每步走2级，6步中每步走一级。记每次走1级台阶为A，记每次走2级台阶为B，则原问题就相当于在8个格子中选2个填写B。其余的填写A，这是一个组合问题，所以一共有C8228种走法。例13：动点从（0，0）沿水平或竖直方向运动到达（6，8），要使行驶的路程最小，有多少种走法？解：动点只能向上或向右运动才能使路程最小而且最小的路程为14，把动点运动1个单位看成是1步，则动点走了14步，于是问题就转化为在14个格子中填写6个“上”和8个“右”，这也是一个组合的问题，于是得到一共有C1463003种走法。八.隔板法例14：20个相同的球分给3个人，允许有人可以不取，但必须分完，有多少种分法？解：将20个球排成一排，一共有21个空隙，将两个隔板插入这些空隙中（两个隔板可以插在同一空隙中），规定由隔板分成的左、中、右三部分球分别分给3个人，则每一种隔法对应了一种分法，每一种分法对应了一种隔法，于是分法的总数为C212210种方法。注：本题可转化成求方程xyz20的非负整数解的个数。【eg】10张参观公园的门票分给5个班，每班至少1张，有几种选法？解：这里只是票数而已，与顺序无关，故可把10张票看成10个相同的小球放入5个不同的盒内，每盒至少1球，可先把10球排成一列，再在其中9个间隔中选4个位置插入4块“档板”分成5格(构成5个盒子)有C94种方法。注：档板分隔模型专门用来解答同种元素的分配问题。【eg】10个相同的球各分给3个人，每人至少一个，有多少种分发？每人至少两个呢？（答：36；15）；分析：显然，直接讨论分配方案复杂而又易错，采用隔板模型法，能化繁为简：取10枚棋子排成