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

排列组合问题的基本模型及解题方法导语：解决排列组合问题要讲究策略，首先要认真审题，弄清楚是排列(有序)还是组合(无序)，还是排列与组合混合问题。其次，要抓住问题的本质特征，准确合理地利用两个基本原则进行“分类与分步”。加法原理的特征是分类解决问题，分类必须满足两个条件：①类与类必须互斥(不相容)，②总类必须完备(不遗漏)；乘法原理的特征是分步解决问题，分步必须做到步与步互相独立，互不干扰并确保连续性。分类与分步是解决排列组合问题的最基本的思想策略，在实际操作中往往是“步”与“类”交叉，有机结合，可以是类中有步，也可以是步中有类，以上解题思路分析，可以用顺口溜概括为：审明题意，排（组）分清；合理分类，用准加乘；周密思考，防漏防重；直接间接，思路可循；元素位置，特殊先行；一题多解，检验真伪。注意以下几点：1、解排列组合应用题的一般步骤为：①什么事：明确要完成的是一件什么事（审题）；②怎么做：分步还是分类，有序还是无序。2、解排列组合问题的思路（1）两种思路：直接法，间接法。（2）两种途径：元素分析法，位置分析法。3、基本模型及解题方法：(一)、元素相邻问题（1）、全相邻问题，捆邦法例1、6名同学排成一排，其中甲，乙两人必须排在一起的不同排法有（C）种。A、720B、360C、240D、120说明：从上述解法可以看出，所谓“捆邦法”，就是在解决对于某几个元素要求相邻问题时，可以整体考虑将相邻元素视作一个“大”元素。（2）、全不相邻问题插空法例2、要排一张有6个歌唱节目和4个舞蹈节目的演出节目单，任何两个舞蹈节目不得相邻，问有多少不同的排法，解：先将6个歌唱节目排好，其中不同的排法有6！，这6个节目的空隙及两端共有七个位置中再排4个舞蹈节目有47A种排法，由乘法原理可知，任何两个舞蹈节目不得相邻的排法为4676AA种例3、高三（一）班学要安排毕业晚会的4各音乐节目，2个舞蹈节目和1个曲艺节目的演出顺序，要求两个舞蹈节目不连排，则不同排法的种数是A、1800B、3600C、4320D、5040解：不同排法的种数为5256AA＝3600，故选B说明：从解题过程可以看出，不相邻问题是指要求某些元素不能相邻，由其它元素将它隔开，此类问题可以先将其它元素排好，再将特殊元素插入，故叫插空法。（3）、不全相邻排除法，排除处理例4、五个人站成一排，其中甲、乙、丙三人有两人相邻，有多少排法？解：533235332372AAAAA222232或3AAA例5、有两排座位，前排11个座位，后排12个座位，现安排2人就座，规定前排中间的3个座位不能坐，并且这2人不．左右相邻，那么不同排法的种数是解法一：①前后各一个，有8×12×2＝192种方法②前排左、右各一人：共有4×4×2＝32种方法③两人都在前排：两人都在前排左边的四个位置：乙可坐2个位置乙可坐1个位置2＋2＝41＋1＝2此种情况共有4＋2＝6种方法因为两边都是4个位置，都坐右边亦有6种方法，所以坐在第一排总共有6＋6＝12种方法④两人都坐在第二排位置，先规定甲左乙右∴甲左乙右总共有55102110128910种方法．同样甲、乙可互换位置，乙左甲右也同样有55种方法，所以甲、乙按要求同坐第二排总共有55×2＝110种方法。综上所述，按要求两人不同排法有192＋32＋12＋110＝346种解法二：考虑20个位置中安排两个人就坐，并且这两人左右不相邻，4号座位与5号座位不算相邻（坐在前排相邻的情况有12种。），7号座位与8号座位不算相邻（坐在后排相邻的情况有22种。），共有346)611(2220A种（二）、定序问题缩倍法例6、信号兵把红旗与白旗从上到下挂在旗杆上表示信号，现有3面红旗、2面白旗，把5面旗都挂上去，可表示不同信号的种数是（）（用数字作答）。解：5面旗全排列有55A种挂，由于3面红旗与2面白旗的分别全排列均只能作一次的挂法，故有55323210AAA说明:在排列的问题中限制某几个元素必须保持一定的顺序问题,这类问题用缩小倍数的方法求解比较方便.例7、某工程队有6项工程需要单独完成，其中工程乙必须在工程甲完成后才能进行，工程丙必须在工程乙完成后才能进行，有工程丁必须在工程丙完成后立即进行。那么安排这6项工程的不同排法种数是。解一：依题意，只需将剩余两个工程插在由甲、乙、丙、丁四个工程形成的5个空中（插一个或二个），可得有22525AA＝30种不同排法。解二：6!4!=30例8、由数字0、1、2、3、4、5组成没有重复数字的6位数，其中个位数字小于十位的数字的共有（）A、210个B、300个C、464个D、600个解：155513002AA故选B（三）、多元问题分类法例9．某校从8名教师中选派4名教师同时去4个边远地区支教(每地1人),其中甲和乙不同去,甲和丙只能同去或同不去,则不同的选派方案共有种解析：某校从8名教师中选派4名教师同时去4个边远地区支教(每地1人)，其中甲和乙不同去，甲和丙只能同去或同不去，可以分情况讨论，①甲、丙同去，则乙不去，有2454CA=240种选法；②甲、丙同不去，乙去，有3454CA=240种选法；③甲、乙、丙都不去，有45120A种选法，共有600种不同的选派方案．例10、设集合1,2,3,4,5I。选择I的两个非空子集A和B，要使B中最小的数大于A中最大的数，则不同的选择方法共有(B)A、50种B、49种C、48种D、47种解析：若集合A、B中分别有一个元素，则选法种数有25C=10种；若集合A中有一个元素，集合B中有两个元素，则选法种数有35C=10种；若集合A中有一个元素，集合B中有三个元素，则选法种数有45C=5种；若集合A中有一个元素，集合B中有四个元素，则选法种数有55C=1种；若集合A中有两个元素，集合B中有一个元素，则选法种数有35C=10种；若集合A中有两个元素，集合B中有两个个元素，则选法种数有45C=5种；若集合A中有两个元素，集合B中有三个元素，则选法种数有55C=1种；若集合A中有三个元素，集合B中有一个元素，则选法种数有45C=5种；若集合A中有三个元素，集合B中有两个元素，则选法种数有55C=1种；若集合A中有四个元素，集合B中有一个元素，则选法种数有55C=1种；总计有49种，选B.解法二：集合A、B中没有相同的元素，且都不是空集，从5个元素中选出2个元素，有25C=10种选法，小的给A集合，大的给B集合；从5个元素中选出3个元素，有35C=10种选法，再分成1、2两组，较小元素的一组给A集合，较大元素的一组的给B集合，共有2×10=20种方法；从5个元素中选出4个元素，有45C=5种选法，再分成1、3；2、2；3、1两组，较小元素的一组给A集合，较大元素的一组的给B集合，共有3×5=15种方法；从5个元素中选出5个元素，有55C=1种选法，再分成1、4；2、3；3、2；4、1两组，较小元素的一组给A集合，较大元素的一组的给B集合，共有4×1=4种方法；总计为10+20+15+4=49种方法。选B.例11、将4个颜色互不相同的球全部放入编号为1和2的两个盒子里，使得放入每个盒子里的球的个数不小于该盒子的编号，则不同的放球方法有（）A、10种B、20种C、36种D、52种解析：将4个颜色互不相同的球全部放入编号为1和2的两个盒子里，使得放入每个盒子里的球的个数不小于该盒子的编号，分情况讨论：①1号盒子中放1个球，其余3个放入2号盒子，有144C种方法；②1号盒子中放2个球，其余2个放入2号盒子，有246C种方法；则不同的放球方法有10种，选A．说明：元素多，取出的情况也多种，可按要求分成互不相容的几类情况分别计算，最后总计。（四）、元素交叉问题集合法（二元否定问题，依次分类）例12、从6名运动员中选出4名参加4×100米接力赛，如果甲不跑第一棒，乙不跑第四棒，共有多少种不同的参赛方法？解：设全集U={6人中任选4人参赛的排列}，A={甲跑第一棒的排列}，B={乙跑第四棒的排列}，根据求集合元素的个数的公式可得参赛方法共有：card(U)-card(A)-card(B)+card(A∩B)=252例13、某天的课表要排入语文、数学、英语、物理、化学、体育共六门课程，且上午安排四节课，下午安排两节课。（1）若第一节不排体育，下午第一节不排数学，一共有多少种不同的排课方法？（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个方格，又有3种填法；第三步将余下的两个数字填入余下的两格中只有一种填法，故共有3×3×1=9种填法。故选B说明：求解二元否定问题先把某个元素按规定排入，再排另一个元素，如此继续下去，依此即可完成。例15、安排5名歌手的演出顺序时，要求某名歌手不第一个出场，另一名歌手不最后一个出场，不同排法的总数是.(用数字作答)。（答：78种）说明：某些排列组合问题几部分之间有交集，可用集合中求元素的个数的公式来求解。（五）、多排问题单排法例16、两排座位，第一排有3个座位，第二排有5个座位，若8名学生入座（每人一座位），则不同的座法为（）A、5388CCB、153288ACCC、3588AAD、88A解：此题分两排座可以看成是一排座，故有88A种座法。∴选D说明：把元素排成几排的问题，可归纳为一排考虑，再分段处理。（六）、至多、至少问题分类法或间接法（去杂处理）含“至多”或“至少”的排列组合问题，是需要分类问题，或排除法。排除法，适用于反面情况明确且易于计算的情况。例17、从4名男生和3名女生中选出3人，分别从事三项不同的工作，若这3人中至少有1名女生，则选派方案共有（）A、108种B、186种C、216种D、270种解析：从全部方案中减去只选派男生的方案数，合理的选派方案共有3374AA=186种，选B.例18、5名乒乓球队员中,有2名老队员和3名新队员.现从中选出3名队员排成1、2、3号参加团体比赛,则入选的3名队员中至少有一名老队员,且1、2号中至少有1名新队员的排法有_______种.(以数作答)【解析】两老一新时,有112322C12CA种排法；两新一老时,有123233CC36A种排法,即共有48种排法.例19、将5名实习教师分配到高一年级的3个班实习，每班至少1名，最多2名，则不同的分配方案有A、30种B、90种C、180种D、270种解析：将5名实习教师分配到高一年级的3个班实习，每班至少1名，最多2名，则将5名教师分成三组，一组1人，另两组都是2人，有12542215CCA种方法，再将3组分到3个班，共有331590A种不同的分配方案，选B.（七）、部分符合条件淘汰法例20、四面体的顶点各棱中点共有10个点，在其中取4个不共面的点，不同的取法共有（）A、150种B、147种C、144种D、141种解：10个点取4个点共有410C种取法，其中面ABC内的6个点中任取4个点必共面，这样的面共有6个，又各棱中点共6个点，有四点共面的平面有3个，故符合条件不共面的平面有44106463141CC选D说明：在选取总数中，只有一部分符合条件，可从总数中减去不符合条件数，即为所求。（八）、分组问题与分配问题①分组问题：均匀分组，除法处理；非均匀分组，组合处理例21、有9个不同的文具盒：（1）将其平均分成三组；（2）将其分成三组，每组个数2，3，4。上述问题各有多少种不同的分法？分析：（1）此题属于分组问题：先取3个为第一组，有39C种分法，再取3个不第二组，有36C种分法，剩下3个为第三组，有33C种分法，由于三组之间没有顺序，故有3