排列组合问题基本类型及解题方法

《排列组合问题基本类型及解题方法》由会员分享，可在线阅读，更多相关《排列组合问题基本类型及解题方法（12页珍藏版）》请在金锄头文库上搜索。

1、 排列组合问题的基本模型及解题方法排列组合问题的基本模型及解题方法 导语：解决排列组合问题要讲究策略，首先要认真审题，弄清楚是排列(有序)还是组合(无 序)，还是排列与组合混合问题。其次，要抓住问题的本质特征，准确合理地利用两个基本原则进 行“分类与分步”。加法原理的特征是分类解决问题，分类必须满足两个条件：类与类必须互 斥(不相容)，总类必须完备(不遗漏)；乘法原理的特征是分步解决问题，分步必须做到步与步 互相独立，互不干扰并确保连续性。分类与分步是解决排列组合问题的最基本的思想策略，在实 际操作中往往是“步”与“类”交叉，有机结合，可以是类中有步，也可以是步中有类，以上解 题思路分析，可以

2、用顺口溜概括为：审明题意，排（组）分清；合理分类，用准加乘；周密思考， 防漏防重；直接间接，思路可循；元素位置，特殊先行；一题多解，检验真伪。注意以下几点： 1、解排列组合应用题的一般步骤为： 什么事：明确要完成的是一件什么事（审题） ； 怎么做：分步还是分类，有序还是无序。 2、解排列组合问题的思路 （1） 两种思路：直接法，间接法。 （2）两种途径：元素分析法，位置分析法。 3、基本模型及解题方法： ( (一一) )、元素相邻问题、元素相邻问题 （1） 、全相邻问题，捆邦法全相邻问题，捆邦法 例 1、6 名同学排成一排，其中甲，乙两人必须排在一起的不同排法有（ C ）种。 A、720 B、

3、360 C、240 D、120 说明：从上述解法可以看出，所谓“捆邦法” ，就是在解决对于某几个元素要求相邻问题时，可 以整体考虑将相邻元素视作一个“大”元素。 （2） 、全不相邻问题插空法全不相邻问题插空法 例 2、要排一张有 6 个歌唱节目和 4 个舞蹈节目的演出节目单，任何两个舞蹈节目不得相邻，问 有多少不同的排法， 解：先将 6 个歌唱节目排好，其中不同的排法有 6！，这 6 个节目的空隙及两端共有七个位置中再排 4 个舞蹈节目有种排法，由乘法原理可知，任何两个舞蹈节目不得相邻的排法为种4 7A46 76A A例 3、高三（一）班学要安排毕业晚会的 4 各音乐节目，2 个舞蹈节目和 1

4、 个曲艺节目的演出顺序， 要求两个舞蹈节目不连排，则不同排法的种数是 A、1800 B、3600 C、4320 D、5040解：不同排法的种数为3600，故选 B52 56A A说明：从解题过程可以看出，不相邻问题是指要求某些元素不能相邻，由其它元素将它隔开，此 类问题可以先将其它元素排好，再将特殊元素插入，故叫插空法。 （3） 、不全相邻排除法，排除处理不全相邻排除法，排除处理 例 4、五个人站成一排，其中甲、乙、丙三人有两人相邻，有多少排法？解：53323 5332372AA AA A222 232或3A A A例 5、有两排座位，前排 11 个座位，后排 12 个座位，现安排 2 人就座

5、，规定前排中间的 3 个座 位不能坐，并且这 2 人不左右相邻，那么不同排法的种数是 解法一： 前后各一个，有 8122192 种方法前排左、右各一人：共有 44232 种方法 两人都在前排：两人都在前排左边的四个位置：乙可坐 2 个位置乙可坐 1 个位置224112此种情况共有 426 种方法 因为两边都是 4 个位置，都坐右边亦有 6 种方法，所以坐在第一排总共有 6612 种方法两人都坐在第二排位置，先规定甲左乙右 甲左乙右总共有55102110128910L 种方法同样甲、乙可互换位置， 乙左甲右也同样有 55 种方法，所以甲、乙按要求同坐第二排总共有 552110 种方法。综上所述，

6、 按要求两人不同排法有 1923212110346 种 解法二：考虑 20 个位置中安排两个人就坐，并且这两人左右不相邻，4 号座位与 5 号座位不算相 邻（坐在前排相邻的情况有 12 种。 ） ，7 号座位与 8 号座位不算相邻（坐在后排相邻的情况有 22 种。） ，共有种346)611(22 20A（二）（二） 、定序问题缩倍法、定序问题缩倍法 例 6、信号兵把红旗与白旗从上到下挂在旗杆上表示信号，现有 3 面红旗、2 面白旗，把 5 面旗都 挂上去，可表示不同信号的种数是（ ） （用数字作答） 。解：5 面旗全排列有种挂，由于 3 面红旗与 2 面白旗的分别全排列均只能作一次的挂法，故有

7、 5 5A5 5 32 3210A A A说明:在排列的问题中限制某几个元素必须保持一定的顺序问题,这类问题用缩小倍数的方法求解 比较方便.例 7、某工程队有 6 项工程需要单独完成，其中工程乙必须在工程甲完成后才能进行，工程丙必 须在工程乙完成后才能进行，有工程丁必须在工程丙完成后立即进行。那么安排这 6 项工程的不 同排法种数是 。 解一：依题意，只需将剩余两个工程插在由甲、乙、丙、丁四个工程形成的 5 个空中（插一个或二个） ，可得有30 种不同排法。22 525AA 解二：=306! 4! 例 8、由数字 0、1、2、3、4、5 组成没有重复数字的 6 位数，其中个位数字小于十位的数字

8、的 共有（ ） A、210 个 B、300 个 C、464 个 D、600 个解： 故选 B15 5513002A A （三）（三） 、多元问题分类法、多元问题分类法 例 9某校从 8 名教师中选派 4 名教师同时去 4 个边远地区支教(每地 1 人),其中甲和乙不同去, 甲和丙只能同去或同不去,则不同的选派方案共有 种 解析：某校从 8 名教师中选派 4 名教师同时去 4 个边远地区支教(每地 1 人)，其中甲和乙不同去，甲和丙只能同去或同不去，可以分情况讨论， 甲、丙同去，则乙不去，有=240 种选法；24 54CA甲、丙同不去，乙去，有=240 种选法；甲、乙、丙都不去，有种选法，共有3

9、4 54CA4 5120A 600 种不同的选派方案例 10、设集合。选择 I 的两个非空子集 A 和 B，要使 B 中最小的数大于 A 中最大1,2,3,4,5I 的数，则不同的选择方法共有 (B)A、 B、 C、 D、50种49种48种47种解析：若集合 A、B 中分别有一个元素，则选法种数有=10 种；若集合 A 中有一个元素，集合 B2 5C中有两个元素，则选法种数有=10 种；若集合 A 中有一个元素，集合 B 中有三个元素，则选法种3 5C数有=5 种；若集合 A 中有一个元素，集合 B 中有四个元素，则选法种数有=1 种；若集合 A4 5C5 5C中有两个元素，集合 B 中有一个

10、元素，则选法种数有=10 种；若集合 A 中有两个元素，集合 B 中3 5C有两个个元素，则选法种数有=5 种；若集合 A 中有两个元素，集合 B 中有三个元素，则选法种4 5C数有=1 种；若集合 A 中有三个元素，集合 B 中有一个元素，则选法种数有=5 种；若集合 A5 5C4 5C中有三个元素，集合 B 中有两个元素，则选法种数有=1 种；若集合 A 中有四个元素，集合 B 中5 5C有一个元素，则选法种 数有=1 种；总计有，选 B.5 5C49种解法二：集合 A、B 中没有相同的元素，且都不是空集，从 5 个元素中选出 2 个元素，有=10 种选法，小的给 A 集合，大的给 B 集

11、合；2 5C从 5 个元素中选出 3 个元素，有=10 种选法，再分成 1、2 两组，较小元素的一组给 A 集合，3 5C较大元素的一组的给 B 集合，共有 210=20 种方法；从 5 个元素中选出 4 个元素，有=5 种选法，再分成 1、3；2、2；3、1 两组，较小元素的一4 5C组给 A 集合，较大元素的一组的给 B 集合，共有 35=15 种方法；从 5 个元素中选出 5 个元素，有=1 种选法，再分成 1、4；2、3；3、2；4、1 两组，较小元5 5C素的一组给 A 集合，较大元素的一组的给 B 集合，共有 41=4 种方法； 总计为 10+20+15+4=49 种方法。选 B.

12、 例 11、将 4 个颜色互不相同的球全部放入编号为 1 和 2 的两个盒子里，使得放入每个盒子里的球 的个数不小于该盒子的编号，则不同的放球方法有（ ） A、10 种 B、20 种 C、36 种 D、52 种 解析：将 4 个颜色互不相同的球全部放入编号为 1 和 2 的两个盒子里，使得放入每个盒子里的球的 个数不小于该盒子的编号，分情况讨论：1 号盒子中放 1 个球，其余 3 个放入 2 号盒子，有种方法；1 号盒子中放 2 个球，其余 2 个放入 2 号盒子，有种方法；则不同的放球1 44C 2 46C 方法有 10 种，选 A 说明：元素多，取出的情况也多种，可按要求分成互不相容的几类

13、情况分别计算，最后总计。 （四）（四） 、元素交叉问题集合法（二元否定问题，依次分类）、元素交叉问题集合法（二元否定问题，依次分类） 例 12、从 6 名运动员中选出 4 名参加 4100 米接力赛，如果甲不跑第一棒，乙不跑第四棒，共 有多少种不同的参赛方法？ 解：设全集 U=6 人中任选 4 人参赛的排列，A=甲跑第一棒的排列，B=乙跑第四棒的排列， 根据求集合元素的个数的公式可得参赛方法共有：card(U)-card(A)-card(B)+card(AB)=252 例 13、某天的课表要排入语文、数学、英语、物理、化学、体育共六门课程，且上午安排四节 课，下午安排两节课。 （1）若第一节不

14、排体育，下午第一节不排数学，一共有多少种不同的排课方法？ （2）要求数学、物理、化学不能排在一起（上午第四节与下午第一节不算连排） ，有多少种不同的 排课方法？ 例 14、同室 4 人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送来的贺年卡，则四张 贺年卡不同的分配方式有（ ） A、6 种 B、9 种 C、11 种 D、23 种 解：此题可以看成是将数字 1、2、3、4 填入标号为 1、2、3、4 的四个方格里，每格填一数，且 每个方格的标号与所填数字不同的填法问题。所以先将 1 填入 2 至 4 的 3 个方格里有 3 种填法；第 二步把被填入方格的对应数字填入其它 3 个方格，又有

15、3 种填法；第三步将余下的两个数字填入余 下的两格中只有一种填法，故共有 331=9 种填法。故选 B 说明：求解二元否定问题先把某个元素按规定排入，再排另一个元素，如此继续下去，依此即可 完成。 例 15、安排 5 名歌手的演出顺序时，要求某名歌手不第一个出场，另一名歌手不最后一个出场， 不同排法的总数是 .(用数字作答) 。 （答：78 种） 说明：某些排列组合问题几部分之间有交集，可用集合中求元素的个数的公式来求解。 （五）（五） 、多排问题单排法、多排问题单排法 例 16、两排座位，第一排有 3 个座位，第二排有 5 个座位，若 8 名学生入座（每人一座位） ，则 不同的座法为（ ）A、 B、