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

解排列组合应用题的解法技巧引言：1、本资料对排列、组合应用题归纳为8种解法、13种技巧2、解排列组合问题的“16字方针”：分类相加，分步相乘，有序排列，无序组合一般先选再排，即先组合再排列，先分再排。弄清要完成什么样的事件是前提，解决这类问题通常有三种途径 (1)以元素为主，应先满足特殊元素的要求，再考虑其他元素 (2)以位置为主考虑，即先满足特殊位置的要求，再考虑其他位置即采用“先特殊后一般”的解题原则.(3)先不考虑附加条件，计算出排列或组合数，再减去不符合要求的排列数或组合数 前两种方式叫直接解法，后一种方式叫间接(剔除)解法 注：数量不大时可以逐一排出结果。3、解排列组合问题的依据是：分类相加（每类方法都能独立地完成这件事，它是相互独立的，一次的且每次得出的是最后的结果，只需一种方法就能完成这件事），分步相乘（一步得出的结果都不是最后的结果，任何一步都不能独立地完成这件事，只有各个步骤都完成了，才能完成这件事，各步是关联的），有序排列，无序组合（一）排列组合应用题的解法排列组合应用题的解题方法既有一般的规律，又有很多特别的技巧，它要求我们要认真地审题，对题目中的信息进行科学地加工处理。下面通过一些例题来说明几种常见的解法。 一. 运用两个基本原理 二. 特殊元素（位置）优先 三. 捆绑法 四. 插入法 五. 排除法 六. 机会均等法 七. 转化法 八. 隔板法一. 运用两个基本原理 加法原理和乘法原理是解排列组合应用题的最基本的出发点，可以说对每道应用题我们都要考虑在记数的时候进行分数或分步处理。 例1：n个人参加某项资格考试，能否通过，有多少种可能的结果？ 解法1：用分类记数的原理，没有人通过，有种结果；1个人通过，有种结果，；n个人通过，有种结果。所以一共有种可能的结果。 解法2：用分步记数的原理。第一个人有通过与不通过两种可能，第二个人也是这样，第n个人也是这样。所以一共有种可能的结果。 例2：同室四人各写了一张贺年卡，先集中起来，然后每人从中拿一张别人的贺年卡，则四张贺年卡不同的分配方式有（ ） （A）6种 （B）9种 （C）11种 （D）23种 解：设四个人分别为甲、乙、丙、丁，各自写的贺年卡分别为a、b、c、d。 第一步，甲取其中一张，有3种等同的方式； 第二步，假设甲取b，则乙的取法可分两类： （1）乙取a，则接下来丙、丁的取法都是唯一的， （2）乙取c或d（2种方式），不管哪一种情况，接下来丙、丁的取法也都是唯一的。 根据加法原理和乘法原理，一共有种分配方式。二. 特殊元素（位置）优先-(优待法) 所谓“优待法”是指在解决排列组合问题时，对于有限制条件的元素(或位置)要优先考虑 例3：从0，1，9这10个数字中选取数字组成偶数，一共可以得到不含相同数字的五位偶数多少个？ 解：个位选0，有个，个位不选0且万位不能选0，有个，所以一共可以得到个偶数。 注 0，2，4，6，8是特殊元素，元素0更为特殊，首位与末位是特殊的位置。 例4：8人站成两排，每排4人，甲在前排，乙不在后排的边上，一共有多少种排法？解：先排甲，有种排法。再排乙，有种排法，再排其余的人，又有种排法，所以一共有种排法。【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中任选一个，共有种选法；第三步：排中间两位，中间两柱可以从个位和首位排好后剩余的数字四个数字中任选两个，共有种排法所以符合条件的四位数共有=4443=192(个) 注这道例题是典型的限制排列组合题解题时，若从元素入手(即元素优先)，常要分类讨论，分类时要注意堵漏防重；若从位置入手(即位置优待1，常要分步解答，分步时要注意分步完整，各步相连三. 捆绑法 在解决对于某几个元素要求相邻的问题时，先整体考虑，将相邻元素视作一个大元素进行排序，然后再考虑大元素内部各元素间顺序的解题策略就是捆绑法 例5：8人排成一排，甲、乙必须分别紧靠站在丙的两旁，有多少种排法？解：把甲、乙、丙先排好，有种排法，把这三个人“捆绑”在一起看成是一个，与其余5个人相当于6个人排成一排，有种排法，所以一共有=1440种排法。注运用捆绑法解决排列组合问题时，一定要注意“捆绑”起来的大元素内部的顺序问题四. 插空法 不相邻问题是指要求某些元素不能相邻，由其它元素将它们隔开解决此类问题可以先将其它元素排好，再将所指定的不相邻的元素插入到它们的间隙及两端位置，故称插空法 例6：排一张有8个节目的演出表，其中有3个小品，既不能排在第一个，也不能有两个小品排在一起，有几种排法？ 解：先排5个不是小品的节目，有种排法，它们之间以及最后一个节目之后一共有6个空隙，将3个小品插入进去，有种排法，所以一共有=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个点，共有种方法，其中取出的4个点共面的有种，所以符合条件的四面体的个数为个。 例8：100件产品中有3件是次品，其余都是正品。现在从中取出5件产品，其中含有次品，有多少种取法？ 解：从100件产品中取5件产品，有种取法，从不含次品的95件中取出5件产品有种取法，所以符合题意的取法有种。 例9：8个人站成一排，其中A与B、A与C都不能站在一起，一共有多少种排法？解：无限制条件有种排法。A与B或A与C在一起各有种排法，A、B、C三人站在一起且A在中间有种排法，所以一共有+=21600种排法。【eg】从4台甲型和5台乙型电视机中任意取出3台，其中至少要甲型与乙型电视机各一台，则不同的取法共有( )种 A140种 B80种 C70种 D35种 解：在被取出的3台中，不含甲型或不合乙型的抽取方法均不合题意，因此符合题意的抽取方法有=70(种)，故选C应该指出的是，上述介绍的各种方法并非绝对的。同一问题有时会有多种解法，这时，要认真思考和分析，灵活选择最佳方法 注这种方法适用于反面的情况明确且易于计算的习题六. 机会均等法 例10：10个人排成一队，其中甲一定要在乙的左边，丙一定要在乙的右边，一共有多少种排法？ 解：甲、乙、丙三人排列一共有6种排法，在这6种排法中各种排列顺序在10个人的所有排列中出现的机会是均等的，因此符合题设条件的排法种数为。 例11：用1，4，5，四个数字组成四位数，所有这些四位数中的数字的总和为288，求。 解：若不为0，在每一个数位上1，4，5，出现的机会是均等的。由于一共可以得到24个四位数，所以每一个数字在每一个数位上出现6次，于是得到： ，解得。 若为0，无解。 七. 转化法 例12：一个楼梯共10级台阶，每步走1级或2级，8步走完，一共有多少种走法？ 解：10级台阶，要求8步走完，并且每步只能走一级或2级。显然，必须有2步中每步走2级，6步中每步走一级。记每次走1级台阶为A，记每次走2级台阶为B，则原问题就相当于在8个格子中选2个填写B。其余的填写A，这是一个组合问题，所以一共有种走法。 例13：动点从（0，0）沿水平或竖直方向运动到达（6，8），要使行驶的路程最小，有多少种走法？ 解：动点只能向上或向右运动才能使路程最小而且最小的路程为14，把动点运动1个单位看成是1步，则动点走了14步，于是问题就转化为在14个格子中填写6个“上”和8个“右”，这也是一个组合的问题，于是得到一共有种走法。 八. 隔板法 例14：20个相同的球分给3个人，允许有人可以不取，但必须分完，有多少种分法？ 解：将20个球排成一排，一共有21个空隙，将两个隔板插入这些空隙中（两个隔板可以插在同一空隙中），规定由隔板分成的左、中、右三部分球分别分给3个人，则每一种隔法对应了一种分法，每一种分法对应了一种隔法，于是分法的总数为种方法。注：本题可转化成求方程的非负整数解的个数。【eg】 10张参观公园的门票分给5个班，每班至少1张，有几种选法？解：这里只是票数而已，与顺序无关，故可把10张票看成10个相同的小球放入5个不同的盒内，每盒至少1球，可先把10球排成一列，再在其中9个间隔中选4个位置插入4块“档板”分成5格(构成5个盒子)有C94种方法。注：档板分隔模型专门用来解答同种元素的分配问题。【eg】10个相同的球各分给3个人，每人至少一个，有多少种分发？每人至少两个呢？（答：36；15）；分析：显然，直接讨论分配方案复杂而又易错，采用隔板模型法，能化繁为简：取10枚棋子排成一列，在相邻的每两枚棋子形成的9个空隙中选取2个空隙，分别插入1个隔板（共两个隔板），讲10枚棋子分割成3部分，因此名额分配方案的种数与隔板插入的组合数相等为如果没人至少两个，可以这样理解：先每人发一本，然后剩下7本每人至少1本按上面的方法有种方法。（二）排列、组合、解题技巧 排列组合问题是高考必考题，它联系实际生动有趣，但题型多样，思路灵活，不易掌握，实践证明，备考有效方法是题型与解法归类、识别模式、熟练运用，本文介绍十二类典型排列组合题的解答策略 1相邻问题并组法2相离问题插空法3定序问题缩倍法 4标号排位问题分步法 5有序分配问题逐分法 6多元问题分类法 7交叉问题集合法8定位问题优先法9多排问题单排法10“至少”问题间接法 11选排问题先取后排法12部分合条件问题排除法13、均匀分配问题-均分法1相邻问题并组法题目中规定相邻的几个元素并为一个组(当作一个元素)参与排列【例1】A、B、C、D、E五人并排站成一排，如果A、B必须相邻且B在A的右边，那么不同的排法种数有A60种 B48种C36种D24种分析 把A、B视为一人，且B固定在A的右边，则本题相当于42相离问题插空法元素相离(即不相邻)问题，可先把无位置要求的几个元素全排列，再把规定相离的几个元素插入上述几个元素间的空位和两端【例2】七个人并排站成一行，如果甲乙两个必须不相邻，那么不同排法的种数是A1440 B3600 C4820D48003定序问题缩倍法在排列问题中限制某几个元素必须保持一定顺序，可用缩小倍数的方法【例3】A、B、C、D、E五个人并排站成一排，如果 B必须站A的右边(A、B可不相邻)，那么不同的排法种数有 A24种B60种C90种D120种分析 B在A右边与B在A左边排法数相同，所以题设的排法只是4标号排位问题分步法把元素排到指定号码的位置上，可先把某个元素按规定排入，第二步再排另一个元素，如此继续下去，依次即可完成【例4】将数字1，2，3，4填入标号为1，2，3，4的四个方格里，每格填一个数，则每个方格的标号与所填数字均不相同的填法有A6种 B9种 C11种D23种分析 先把1填入方格，符合条件的有3种方法，第二步把被填入方格的对应数字填入其它三个方格，又有三种方法；第三步填余下的两个数字，只有一种填法，共有3319种填法，故选B5有序分配问题逐分法有序分配问题是指把元素按要求分成若干组，可用逐步下量分组法【例5】有甲、乙、丙三项任务，甲需2人承担，乙丙各需1人承担，从10人中选出4人承担这三项任务，不同的选法总数有A1260种 B2025种 C2520种D5040种分析 先从10人中选出2个承担甲项任务，再从剩下8个中选1人承担乙项任务，第三步从另外7人中选1个承担两项任务，不同6多元问题分类法元素多，取出的情况也有多种，可按结果要求，分成不相容的几类情况分别计算，最后总计【例6】由数字 0，1，2，3，4，5组成且没有重复数字的六位数，其中个位数字小于十位数字的共有A210个 B300个 C464个D600个分析 按题意，个位数字只可能是0，1，2，3，4共5种情况，【例7】从1，2，3，100这100个数中，任取两个数，使它们的乘积能被7整除，这两个数的取法(不计顺序)共有多少种？分析 被取的两个数中至少有一个能被7整除时，它们的乘积就能被7整除，将这100个数组成的集合视为全集，能被7整除的数的集合记作A，则A7，14，98共有14个元素，不能被7整除【例8】从1，2，100这100个数中，任取两个数，使其和能被4整除的取法(不计顺序)有多少？分析 将1，2，100分成四个不相交的子集，能被4整除的数集A4，8， 100；被4除余1的数集B1，5，97；被4除余2的数集为C2，6，98；被4除余3的数集为D3，7，99，易见这四个集合，每一个都含25个元素；从A中任取两个数符合要求；从B、D中各取一个数的取法也符合要求；从C中任取两个数的取法同样符合要求；此外其它取法都7交叉问题集合法某些排列组合问题几部分之间有交集，可用集合中求元素个数公式n(AB)n(A)n(B)n(AB)【例9】从6名运动员中选出4个参加4100m接力赛，如果甲不跑第一棒，乙不跑第四棒，共有多少种不同参赛方法？分析 设全集6人中任取4人参赛的排列，A甲第一棒的排列，B乙跑第四棒的排列，根据求集合元素个数的公式得参赛方法共有：8定位问题优先法某个(或几个)元素要排在指定位置，可先排这个(几个)元素，再排其他元素【例10】1名老师和4名获奖同学排成一排照像留念，若老师不在两端，则有不同的排法有_种【eg】书架上有3本不同的书，如果保持这些书的相对顺序不变，再放上2本不同的书，有 种不同的放法 分析：法一：分两部完成，第一步，固定3本不同的书前后顺序进行排列，设其排列数为N，第二步，再对三本书进行内部排列，有种不同的方法，由分布计数原理，所以种不同的方法。法二：可理解为从5个位置中选2个进行排列，三本书放剩余位置。9多排问题单排法把元素排成几排的问题，可归结为一排考虑，再分段处理【例11】6个不同的元素排成前后两排，每排3个元素，那么不同的排法种数是A36 B120 C720D1440分析 前后两排可看成一排的两段，因此本题可视为6个不同元素【例12】8个不同的元素排成前后两排，每排4个元素，其中某2个元素要排在前排，某 1个元素要排在后排，有多少种排法？(高中代数甲种本第三册P82，23)10“至多”、“至少”问题间接法关于“至少”类型组合问题，用间接法较方便【例13】从4台甲型和5台乙型电视机中任取出3台，其中至少要甲型和乙型电视机各一台，则不同取法共有A140种 B80种 C70种D35种分析 逆向思考，至少各一台的反面就是分别只取一种型号，不取如从7名男同学和5名女同学中选出5人，至少有2名女同学当选的选法有_种（答：596）提醒：亦可分类来求.11选排问题先取后排法从几类元素中取出符合题意的几个元素，再安排到一定位置上，可用先取后排法【例14】四个不同的球放入编号为1，2，3，4的四个盒中，则恰有一个空盒的放法共有_种【例15】9名乒乓球运动员，其中男5名，女4名，现在要进行混合双打训练，有多少种不同分组法？如某种产品有4只次品和6只正品，每只产品均不相同且可区分，今每次取出一只测试，直到4只次品全测出为止，则最后一只次品恰好在第五次测试时，被发现的不同情况种数是_（答：576）。12部分合条件问题排除法在选取总数中，只有一部分合条件，可从总数中减去不合条件数，即为所求【例16】以一个正方体顶点为顶点的四面体共有 A70个B64个C58个D52个面体，但6个表面和6个对角面的四个顶点共面都不能构成四面体，所【例17】正六边形中心和顶点共7个点，以其中3个点为顶点的三角形共有_个13、均匀分配问题-均分法【例17】6本不同的书，按下列要求各有多少种不同的选法：（1）分给甲、乙、丙三人，每人2本；（2）分为三份，每份2本；（3）分为三份，一份1本，一份2本，一份3本；（4）分给甲、乙、丙三人，一人1本，一人2本，一人3本；（5）分给甲、乙、丙三人，每人至少1本 解：（1）根据分步计数原理得到：种；（2）分给甲、乙、丙三人，每人两本有种方法，这个过程可以分两步完成：第一步分为三份，每份两本，设有x种方法；第二步再将这三份分给甲、乙、丙三名同学有种方法根据分步计数原理可得：，所以因此，分为三份，每份两本一共有15种方法点评：本题是分组中的“均匀分组”问题一般地：将个不同元素均匀分成组（每组个元素），共有 种方法（3）这是“不均匀分组”问题，一共有种方法（4）在（3）的基础上再全排列，一共有种方法（5）可以分为三类情况：“2、2、2型”即（1）中的分配情况，有种方法；“1、2、3型”即（4）中的分配情况，有种方法；“1、1、4型”，有种方法；所以，一共有90+360+90540种方法点评：本题第（3）种类型为部分均匀分组再分配，其分组总数为思考（1）：8名球员住A、B、C三个房间，每个房间最多住3人，有多少种住宿方法？解：思考（2）：六本相同的书发给甲、乙、丙三人，要求全部分完，不管三人是否均分到书问有多少种不同的分法？解：用档板法处理，|，结果为点评：类题求不定方程的非负整数解的个数？练习：（1）四本不同的书，分给三个人，每人至少一本，全部分完，有几种分法？解：先分组，再分配有种（2）本不同的书，分给个人，每人至少1本，全部分完，有几种分法？解：先分组，再分配有种 （3）本相同的书，分给个人，每人至少1本，全部分完，有几种分法？解：共种分法（4）10个相同的小球放入编号为1、2、3的盒子中，球数不少于编号数的放法有多少种？解：按要求放6个，其余4个按上题的方法放有【eg】3名飞行员和6名特勤人员分别上3架不同型号的直升飞机执行任务,每机11中飞行员和两名特勤人员，有多少种分配方法？解：先分组，再分配，类题：20名同学分两组，每组10人去某地社会实践，其中6名干部，每组3人，不同分法总数是多少？解：