第53讲排列与组合(第3课时-排列组合问题的处理策略)

第53讲排列与组合-排列组合问题的处理策略（第3课时）4.排列组合问题的处理策略⑴特殊元素的处理（优先安排）应该先处理带有条件的元素或位置，然后再处理其余的元素或位置。也就是先处理“在与不在”或“含与不含”的问题。如果有必要，还可以自己制造特殊元素。例．在3000到8000之间，有多少个没有重复数字且能被5整除的奇数？分析：符合题意的数，要具有以下条件：①个位必须是5；②千位必须是3、4、6、7中的一个；③百位和十位上可以是余下的8个数字中的任意2个。综上所述，我们应该先排个位，其次排千位，最后排百位和十位。解：个位必须是5，只有一种排法；千位必须是3、4、6、7中的一个，有14C种选法；百位和十位有28A种排法；故合题意的奇数共有14C22478428A个。例．求证：11rnrnrnrAAA。分析：左边的rnA1表示从1n个元素中取出r个的排列，设这1n个元素中有一个特殊元素Ｘ，那么rnA1由包含Ｘ和不包含Ｘ的两部分构成。先考虑包含Ｘ的，首先取出Ｘ放在某一个位置，那么还需要从剩下的n个中取1r个，这有1rnA种排法，但因为Ｘ有r个位置可以放，故包含Ｘ的排法有1rnrA种；再考虑不包含Ｘ的，显然有rnA种，∴11rnrnrnrAAA。⑵分类与分步的处理（合理分类，准确分步）使用计数原理时，分类要合理，分步要准确，做到层次清楚，不重不漏。我们一般按照元素的性质进行分类，按照事件发生的连续过程分步。例．从六个数字0、1、2、3、4、5中，每次取出3个，可以组成多少个没有重复数字的三位偶数？解法一（按百位上的数字来分类）：①百位上是奇数时，个位可以从0、2、4中任选一个，十位可以从余下的四个数中任选一个，有排法141313CCC种；②百位上是偶数时，个位只能从余下的两个偶数中任选一个，十位可以从余下的四个数中任选一个，有排法141212CCC种；综上所述，共可组成三位偶数141313CCC+521636141212CCC个。解法二（按个位上的数字来分类）：①个位放0：十位可以从1、2、3、4、5中任选一个，有15A种；百位从余下的四个数字中任选一个，有14A种；故个位是0的三位偶数有15A2014A个。②个位放2：十位可以从0、1、3、4、5中任选一个，有15A种；百位从余下的三个数字（已除开0）中任选一个，有13A种；故个位是2的三位偶数有15A1513A个。③个位放4：情况与个位放2完全相同，故个位是4的三位偶数有15A1513A个。综上所述，共可组成三位偶数15A051315131514AAAAA个。考点热点一定掌握！这里比解法一怎么少了２种？我们以个位放2的情况为例进行分析，此时，如果十位上放的数字是1、3、4、5时，百位确实有13A种放法，但若十位上放的数字是0时，百位上就有4种放法而不是313A种放法，这四种放法是：102、302、402、502，也就是说漏掉了一种。个位放4时同样也漏掉了一种。所以最终答案应为15A14A+15A113A15A52113A个。点评：显然，解法一的分类方法优于解法二的分类方法。⑶排列组合混合问题的处理（先选后排）对于排列与组合的混合问题，可采取先选出元素，后进行排列的策略。例(1995年高考理科题)．4个不同的小球放入编号为1、2、3、4的四个盒子，则恰有一个空盒的放法有_______种。分析：这是一个排列与组合的混合问题。因恰有一个空盒，所以必有一个盒子要放2个球。故可分三步进行：第一步，从4个球中任选2个球，有24C种选法；第二步，从4个盒子中选出3个，有34C种选法；第三步，把选出的2个球视为一个元素，与其余的2个球共3个元素对选出的3个盒子作全排列，有33A种排法。所以满足条件的放法共有24C34C33A=144种。⑷正面下手不易的处理（逆向思维，等价转换）如果从正面下手情况复杂，不易解决时，可考虑从反面下手，将其等价转化为一个较简单的问题来处理。例．马路上有编号为1、2、3…、9的9只路灯，为节约用电，现要求把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，也不能关掉两端的路灯，则满足条件的关灯方法共有_______种。分析：从编号为2、3…、８的７只路灯中关掉一只灯的方法有7种，再关哪一只灯，就要分类讨论，情况比较复杂。不如换一个角度，因为“关掉三只灯”等价为“在6只亮灯中插入3只暗灯”。插入时，任何两只暗灯不相邻，且暗灯不在两端，也就是在6只亮灯所形成的5个间隙中选3个插入3只暗灯，其方法有35C=10种，故满足条件的关灯的方法共有10种。⑸必须相邻元素的处理（捆绑法）对于某几个元素要求相邻的排列问题，可以先把必须相邻的元素看成一个整体（即一个元素）来与其他元素进行排列，得出结果后，再来考虑那几个相邻元素的内部排列问题。例．文艺晚会有12个节目，如果其中有三个节目一定要排在一起，共有多少种排法？解：把三个一定要排在一起的节目看成一个节目，那么共有10个节目参与安排，有1010A种排法，三个一定要排在一起的节目内部有排法33A种，故满足条件的排法共有1010A1088640033A种。⑹不能相邻元素的处理（插空法）对于某几个元素不能相邻的排列问题，可以先把那些没有规定不能相邻的元素安置好，再把不能相邻的那些元素分隔开插入到已排好的元素之间及两端的空隙中。例．文艺晚会有12个节目，如果其中有两个节目不能排在一起，共有多少种排法？解：可以相邻的节目有10个，有1010A种排法，可以用来安排那两个不能相邻的节目的空隙有11个，那两个不能相邻的节目的排法有211A种，那么共有排法1010A×3991680001103628800211A种。⑺定序问题的处理（做除法）如果参与排列的某几个元素要求固定顺序，那么可以先不考虑这一点，求出其排列数；然后再求出这几个元素的全排列数，将前者除以后者即可得出结果。例．有７名学生，站成一排，其中甲、乙、丙三人从左至右的顺序不变，共有多少种排列方法？解：不考虑甲、乙、丙三人的顺序时，有排法A77种；甲、乙、丙三人的全排列有A33种；故共有排法3377AA=840种。例．六个学生围坐成一圈，一共有多少种坐法？分析：围成一圈和站成一排的情况是不相同的，围成一圈时就没有首尾的区别了。站成一排时，因排首不同的排法有16A种，现在排首不存在，那么共有排法1201666AA种。⑻多排问题的处理（看成一排）把若干个元素排成前后若干排的排列问题，若没有其他特殊要求，那么它们的结果与排成一排的方法是相同的。例(1989年高考文科题)两排座位，第一排3个座位，第二排5个座位，若8名学生每人一个座位，则不同的坐法种数是（）。A.3858CC；B.585812CCC；C.3858CA；D.88A。分析：因8名学生可在前后两排的8个座位中随意入坐，再无其他条件，所以两排座位可看作一排来处理，其不同的坐法种数是88A，故应选D。⑼“小集体”问题的处理（先整体后局部）对于“小集体”排列问题，可先将“小集体”看作一个元素与其余元素排列，最后再进行“小集体”内部的排列。例三名男歌唱家和两名女歌唱家联合举行一场音乐会，演出的出场顺序要求两名女歌唱家之间恰有一名男歌唱家，其出场方案共有（）。A.36种；B.18种；C.12种；D.6种。分析：按要求出场顺序中必须有一个小集体“女、男、女”，因此先在三名男歌唱家中选一名(有13C种选法)与两名女歌唱家组成一个小集体，将这个小集体视为一个元素，与其余2名男歌唱家排列有33A种排法，最后小集体内2名女歌唱家排列有22A种排法，共有13C33A22A=36种出场方案，故应选A。点评：“两名女歌唱家之间恰有一名男歌唱家”与“两名女歌唱家不能连排”不等价，所以不能使用前述的“插空法”来解。1．五人排成一列，其中甲不能站排头，乙不能站排尾，丙不能站正中间。问共有多少种不同的排法？2．四男三女排成一排照相，要求女生不连排，共有多少种排法？3．学生要从六门课程中选学两门，但这六门课程中有两门是在同一时间上课，问有几种选法？4．某帆船上有8名选手，要把他们安排在船的左右两侧，每侧四人，其中2名水手只会划左侧桨，1名水手只会划右侧桨，共有多少种排法？能力测试认真完成！5*．某校准备组建一个18人的足球队，这18人由高一年级10个班的学生组成，每个班级至少1人，名额分配方案共有种。6．有3名男生，4名女生，站成一排，其中男生必须站在一起，共有多少种排列方法？7．有3名男生，4名女生，站成一排，其中任何两个男生不能站在一起，共有多少种排列方法？８．(1991年三南高考题)由数字0、1、2、3、4、5组成没有重复数字的六位数，其中个位数小于十位数字的共有（）A.210个；B.300个；C.464个；D.600个。9．四个男生四个女生坐成前后两排，每排4人，⑴前排3人，后排4人，有几种坐法？⑵每排必须有女生，有几种坐法？10．有3名男生，4名女生，排成一行，甲、乙两人中间必须间隔3人，共有多少种排列方法？11*．20个不加区别的小球放入编号为1、2、3的三个盒子中，要求每个盒内的球数不小于它的编号数，求不同的放法种数。DS2502，03排列组合问题的处理策略12345678910111.特殊元素的处理√2.分类与分步的处理√√3.排列组合混合问题的处理√4.正面下手不易的处理√√5.必须相邻元素的处理√6.不能相邻元素的处理√7.定序问题的处理√8.分排问题的处理√9.“小集体”问题的处理√1．五人排成一列，其中甲不能站排头，乙不能站排尾，丙不能站正中间。问共有多少种不同的排法？解法一：若无限制，应有55A种排法。甲不站排头、乙不站排尾、丙不站正中间分别各有44A种排法。44A中的重复如下：甲站排头同时乙站排尾、甲站排头同时丙站正中间、乙站排尾同时丙站正中间分别各有33A种排法。33A中的重复如下：甲站排头同时乙站排尾且丙站正中间有22A种排法。故共有排法55A-443A+333A-6422A种。点评：设无限制时的排列为全集I，甲站排头的为A集，乙站排尾的为B集，丙站正中间的为C集，则画出集合图如右图。利用此图即可清楚地看出上面的重复关系。2．四男三女排成一排照相，要求女生不连排，共有多少种排法？解：把三个女生安排在4个男生之间的五个空位（含首尾）上有35A种方法，此外4个男生之间也可以变换位置，有44A种，故共有排法35A44A种。错解：7人排成一排有方法77A种；把三女看成一个整体，那么7个位置就相当于5个，把这三个女生放到这5个位置上有排法55A种，三女内部还可以排，有33A种，故三女连排有55A33A种；同理，两女连排有662223AAC种；故共有排法77A-55A33A-662223AAC种。（结果略）错误原因：三女连排与两女连排中有重复。3．学生要从六门课程中选学两门，但这六门课程中有两门是在同一时间上课，问有几种选法？解：如果不考虑时间冲突，共有26C种选法，其中有一种选法正好是两门有冲突的，故实际只有选法14126C种。解题错误：误为1214CC。4．某帆船上有8名选手，要把他们安排在船的左右两侧，每侧四人，其中2名水手只会划左侧桨，1名水手只会划右侧桨，共有多少种排法？解：先把那2名只会划左侧桨的水手安排在左侧，把那1名只会划右侧桨的水手安排在右侧，再从剩下的5人中选出2人安排在左侧，有25C种方法；余下3人安排在右侧，对左侧四人进行参考答案仔细核对！全排列，有44A种方法；对右侧四人进行全排列，有44A种方法；故共有排法25C44A44A=5760种。点评：本题是排列组合混合题，先选后排。5*．某校准备组建一个18人的足球队，这18人由高一年级10个班的学生组成，每个班级至少1人，名额分配方案共有种。分析：取18枚棋子（表示名额）排成一行，在形成的17个间隙中选取9个间隙插入隔板，从而将18枚棋子分隔成10个区间，第i(1≤i≤10)个区间的棋子数对应第i个班级分配的名额，因此名额分配方案的种数与隔板插入的方法数相等。因隔板插入的方法数为917