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

排列组合问题的基本模型及解题方法 导语：解决排列组合问题要讲究策略，首先要认真审题，弄清楚是排列(有序)还是组合(无序)，还是排列与组合混合问题。其次，要抓住问题的本质特征，准确合理地利用两个基本原则进行“分类与分步”。加法原理的特征是分类解决问题，分类必须满足两个条件：类与类必须互斥(不相容)，总类必须完备(不遗漏)；乘法原理的特征是分步解决问题，分步必须做到步与步互相独立，互不干扰并确保连续性。分类与分步是解决排列组合问题的最基本的思想策略，在实际操作中往往是“步”与“类”交叉，有机结合，可以是类中有步，也可以是步中有类，以上解题思路分析，可以用顺口溜概括为：审明题意，排（组）分清；合理分类，用准加乘；周密思考，防漏防重；直接间接，思路可循；元素位置，特殊先行；一题多解，检验真伪。注意以下几点： 1、解排列组合应用题的一般步骤为：什么事：明确要完成的是一件什么事（审题）； 怎么做：分步还是分类，有序还是无序。 2、解排列组合问题的思路（1） 两种思路：直接法，间接法。（2）两种途径：元素分析法，位置分析法。3、基本模型及解题方法： (一)、元素相邻问题（1）、全相邻问题，捆邦法例1、6名同学排成一排，其中甲，乙两人必须排在一起的不同排法有（ C ）种。A、720 B、360 C、240 D、120说明：从上述解法可以看出，所谓“捆邦法”，就是在解决对于某几个元素要求相邻问题时，可以整体考虑将相邻元素视作一个“大”元素。（2）、全不相邻问题插空法例2、要排一张有6个歌唱节目和4个舞蹈节目的演出节目单，任何两个舞蹈节目不得相邻，问有多少不同的排法，解：先将6个歌唱节目排好，其中不同的排法有6！，这6个节目的空隙及两端共有七个位置中再排4个舞蹈节目有种排法，由乘法原理可知，任何两个舞蹈节目不得相邻的排法为种例3、高三（一）班学要安排毕业晚会的4各音乐节目，2个舞蹈节目和1个曲艺节目的演出顺序，要求两个舞蹈节目不连排，则不同排法的种数是A、1800 B、3600 C、4320 D、5040解：不同排法的种数为3600，故选B说明：从解题过程可以看出，不相邻问题是指要求某些元素不能相邻，由其它元素将它隔开，此类问题可以先将其它元素排好，再将特殊元素插入，故叫插空法。（3）、不全相邻排除法，排除处理例4、五个人站成一排，其中甲、乙、丙三人有两人相邻，有多少排法？解：例5、有两排座位，前排11个座位，后排12个座位，现安排2人就座，规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是解法一：前后各一个，有8122192种方法 前排左、右各一人：共有44232种方法两人都在前排：两人都在前排左边的四个位置：乙可坐2个位置乙可坐1个位置224112此种情况共有426种方法因为两边都是4个位置，都坐右边亦有6种方法，所以坐在第一排总共有6612种方法两人都坐在第二排位置，先规定甲左乙右甲左乙右总共有种方法同样甲、乙可互换位置，乙左甲右也同样有55种方法，所以甲、乙按要求同坐第二排总共有552110种方法。综上所述，按要求两人不同排法有 1923212110346种解法二：考虑20个位置中安排两个人就坐，并且这两人左右不相邻，4号座位与5号座位不算相邻（坐在前排相邻的情况有12种。），7号座位与8号座位不算相邻（坐在后排相邻的情况有22种。），共有种（二）、定序问题缩倍法例6、信号兵把红旗与白旗从上到下挂在旗杆上表示信号，现有3面红旗、2面白旗，把5面旗都挂上去，可表示不同信号的种数是（ ）（用数字作答）。解：5面旗全排列有种挂，由于3面红旗与2面白旗的分别全排列均只能作一次的挂法，故有 说明:在排列的问题中限制某几个元素必须保持一定的顺序问题,这类问题用缩小倍数的方法求解比较方便. 例7、某工程队有6项工程需要单独完成，其中工程乙必须在工程甲完成后才能进行，工程丙必须在工程乙完成后才能进行，有工程丁必须在工程丙完成后立即进行。那么安排这6项工程的不同排法种数是 。解一：依题意，只需将剩余两个工程插在由甲、乙、丙、丁四个工程形成的5个空中（插一个或二个），可得有30种不同排法。解二：=30例8、由数字0、1、2、3、4、5组成没有重复数字的6位数，其中个位数字小于十位的数字的共有（ ）A、210个 B、300个 C、464个 D、600个解： 故选B（三）、多元问题分类法例9某校从8名教师中选派4名教师同时去4个边远地区支教(每地1人),其中甲和乙不同去,甲和丙只能同去或同不去,则不同的选派方案共有 种解析：某校从8名教师中选派4名教师同时去4个边远地区支教(每地1人)，其中甲和乙不同去，甲和丙只能同去或同不去，可以分情况讨论， 甲、丙同去，则乙不去，有=240种选法；甲、丙同不去，乙去，有=240种选法；甲、乙、丙都不去，有种选法，共有600种不同的选派方案例10、设集合。选择I的两个非空子集A和B，要使B中最小的数大于A中最大的数，则不同的选择方法共有 (B)A、 B、 C、 D、解析：若集合A、B中分别有一个元素，则选法种数有=10种；若集合A中有一个元素，集合B中有两个元素，则选法种数有=10种；若集合A中有一个元素，集合B中有三个元素，则选法种数有=5种；若集合A中有一个元素，集合B中有四个元素，则选法种数有=1种；若集合A中有两个元素，集合B中有一个元素，则选法种数有=10种；若集合A中有两个元素，集合B中有两个个元素，则选法种数有=5种；若集合A中有两个元素，集合B中有三个元素，则选法种数有=1种；若集合A中有三个元素，集合B中有一个元素，则选法种数有=5种；若集合A中有三个元素，集合B中有两个元素，则选法种数有=1种；若集合A中有四个元素，集合B中有一个元素，则选法种 数有=1种；总计有，选B.解法二：集合A、B中没有相同的元素，且都不是空集，从5个元素中选出2个元素，有=10种选法，小的给A集合，大的给B集合；从5个元素中选出3个元素，有=10种选法，再分成1、2两组，较小元素的一组给A集合，较大元素的一组的给B集合，共有210=20种方法；从5个元素中选出4个元素，有=5种选法，再分成1、3；2、2；3、1两组，较小元素的一组给A集合，较大元素的一组的给B集合，共有35=15种方法；从5个元素中选出5个元素，有=1种选法，再分成1、4；2、3；3、2；4、1两组，较小元素的一组给A集合，较大元素的一组的给B集合，共有41=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号盒子，有种方法；1号盒子中放2个球，其余2个放入2号盒子，有种方法；则不同的放球方法有10种，选A 说明：元素多，取出的情况也多种，可按要求分成互不相容的几类情况分别计算，最后总计。（四）、元素交叉问题集合法（二元否定问题，依次分类）例12、从6名运动员中选出4名参加4100米接力赛，如果甲不跑第一棒，乙不跑第四棒，共有多少种不同的参赛方法？解：设全集U=6人中任选4人参赛的排列，A=甲跑第一棒的排列，B=乙跑第四棒的排列，根据求集合元素的个数的公式可得参赛方法共有：card(U)-card(A)-card(B)+card(AB)=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种填法；第三步将余下的两个数字填入余下的两格中只有一种填法，故共有331=9种填法。故选B说明：求解二元否定问题先把某个元素按规定排入，再排另一个元素，如此继续下去，依此即可完成。例15、安排5名歌手的演出顺序时，要求某名歌手不第一个出场，另一名歌手不最后一个出场，不同排法的总数是 .(用数字作答) 。（答：78种）说明：某些排列组合问题几部分之间有交集，可用集合中求元素的个数的公式来求解。（五）、多排问题单排法例16、两排座位，第一排有3个座位，第二排有5个座位，若8名学生入座（每人一座位），则不同的座法为（ ）A、 B、 C、 D、解：此题分两排座可以看成是一排座，故有 种座法。选D 说明：把元素排成几排的问题，可归纳为一排考虑，再分段处理。（六）、至多、至少问题分类法 或 间接法（去杂处理）含“至多”或“至少”的排列组合问题，是需要分类问题，或排除法。排除法，适用于反面情况明确且易于计算的情况。例17、从4名男生和3名女生中选出3人，分别从事三项不同的工作，若这3人中至少有1名女生，则选派方案共有（ ）A、108种 B、186种 C、216种 D、270种解析：从全部方案中减去只选派男生的方案数，合理的选派方案共有=186种，选B.例18、5名乒乓球队员中,有2名老队员和3名新队员.现从中选出3名队员排成1、2、3号参加团体比赛,则入选的3名队员中至少有一名老队员,且1、2号中至少有1名新队员的排法有_种.(以数作答) 【解析】两老一新时, 有种排法；两新一老时, 有种排法,即共有48种排法.例19、将5名实习教师分配到高一年级的3个班实习，每班至少1名，最多2名，则不同的分配方案有 A、30种B、90种 C、180种D、270种解析：将5名实习教师分配到高一年级的3个班实习，每班至少1名，最多2名，则将5名教师分成三组，一组1人，另两组都是2人，有种方法，再将3组分到3个班，共有种不同的分配方案，选B.（七）、部分符合条件淘汰法例20、四面体的顶点各棱中点共有10个点，在其中取4个不共面的点，不同的取法共有 （ ） A、150种 B、147种 C、144种 D、141种解：10个点取4个点共有 种取法，其中面ABC内的6个点中任取4个点必共面，这样的面共有6个，又各棱中点共6个点，有四点共面的平面有3个，故符合条件不共面的平面有 选D说明：在选取总数中，只有一部分符合条件，可从总数中减去不符合条件数，即为所求。（八）、分组问题与分配问题分组问题：均匀分组，除法处理；非均匀分组，组合处理例21、有9个不同的文具盒：（1）将其平均分成三组；（2）将其分成三组，每组个数2，3，4。上述问题各有多少种不同的分法？分析：（1）此题属于分组问题：先取3个为第一组，有 种分法，再取3个不第二组，有种分法，剩下3个为第三组，有 种分法，由于三组之间没有顺序，故有种分法。（2）同（1），共有种分法，因三组个数各不相同，故不必再除以。分配问题：定额分配，组合处理；随机分配，先组后排例22、有9本不同的书：（1）分给甲2本，乙3本，丙4本；（2）分给三个人，分别得2本，3本，4本。上述问题各有多少种不同的分法？（1）此题是定额分配问题，先让甲选，有种；再让乙选，有种；剩下的给丙，有种，共有种不同的分法（2）此题是随机分配问题：先将9本书分成2本，3本，4本共有三堆，再将三堆分给三个人，共有种不同的分法。例23、对某种产品的6件不同正品和4件不同次品一一进行测试，至区分出所有次品为止，若所有次品恰好在第5次测试时被全部发现，则这样的测试方法有多少种可能?解：第5次必测出一次品，余下3件次品在前4次被测出，从4件中确定最后一件次品有种方法，前4次中应有1件正品、3件次品，有种，前4次测试中的顺序有种，由分步计数原理即得：（）576。本题涉及一类重要问题：问题中既有元素的限制，又有排列的问题，一般是先选元素（即组合）后排列.练习：1、3名教师分配到6个班里，各人教不同的班级，若每人教2个班，有多少种分配方法？2、将10本不同的专著分成3本，3本，3本和1本，分别交给4位学者阅读，问有多少种不同的分法？例24、某外商计划在四个候选城市投资3个不同的项目,且在同一个城市投资的项目不超过2个,则该外商不同的投资方案有 ( )A.16种 B.36种 C.42种 D.60种解析：有两种情况，一是在两个城市分别投资1个项目、2个项目，此时有，二是在在两个城市分别投资1，1，1个项目，此时有， 共有=60， 故选 （D）（九）、相同元素入盒问题隔板法 在排列组合中，对于将不可分辨的球装入到可以分辨的盒子中，每盒至少一个，求方法数的问题，常用隔板法。例25、求方程x+y+z=10的正整数解的个数。(即：10个相同的小球分给三人，每人至少1个，有多少方法？) 分析：将10个球排成一排，球与球之间形成9个空隙，将两个隔板插入这些空隙中（每空至多插一块隔板），规定由隔板分成的左、中、右三部分的球数分别为 x.y.z之值（如图） 则隔板与解的个数之间建立了一一对立关系，故解的个数为 个。实际运用隔板法解题时，在确定球数、如何插隔板等问题上形成了一些技巧。下面举例说明：（1）、添加球数用隔板法 例26、求方程x+y+z=10 的非负整数解的个数。分析：注意到x 、y 、z 可以为零，故上题解法中的限定“每空至多插一块隔板”就不成立了。怎么办呢？只要添加三个球，给 x、 y、z 各一个球。这样原问题就转化为求x+y+z=13 的正整数解的个数了，故解的个数为=66个。（2）、减少球数用隔板法 例27、将20个相同的小球放入编号分别为1，2，3，4的四个盒子中，要求每个盒子中的球数不少于它的编号数，求放法总数。 分析1：先在编号1，2，3，4的四个盒子内分别放0，1，2，3个球，有1种方法；再把剩下的14个球，分成4组，每组至少1个，由例25知有 =286 种方法。 分析2：第一步先在编号1，2，3，4的四个盒子内分别放1，2，3，4个球，有1种方法；第二步把剩下的10个相同的球放入编号为1，2，3，4的盒子里，由例26知有 =286 种方法。 （3）、先后插入用隔板法例28、为构建和谐社会出一份力，一文艺团体下基层宣传演出，准备的节目表中原有4个歌舞节目，如果保持这些节目的相对顺序不变，拟再添2个小品节目，则不同的排列方法有多少种？ 分析：记两个小品节目分别为A、B。先排A节目。根据A节目前后的歌舞节目数目考虑方法数，相当于把4个球分成两堆，由例26知有 种方法。这一步完成后就有5个节目了。再考虑需加入的B节目前后的节目数，同上理知有 种方法。故由乘法原理知，共有 种方法。（十）、数字问题（组成无重复数字的整数） 能被2整除的数的特征：末位数是偶数；不能被2整除的数的特征：末位数是奇数。能被3整除的数的特征：各位数字之和是3的倍数；能被9整除的数的特征：各位数字之和是9的倍数。能被4整除的数的特征：末两位是4的倍数。能被5整除的数的特征：末位数是0或5。 能被25整除的数的特征：末两位数是25，50，75。 能被6整除的数的特征：各位数字之和是3的倍数的偶数。例29、在这五个数字组成的没有重复数字的三位数中，各位数字之和为奇数的共有A、36个 B、24个 C、18个 D、6个解：依题意，所选的三位数字有两种情况：（1）3个数字都是奇数，有种方法（2）3个数字中有一个是奇数，有，故共有24种方法，故选B例30、用数字0，1，2，3，4组成没有重复数字的五位数，则其中数字1，2相邻的偶数有24个.（十一）、分球入盒问题例30、将5个小球放到3个盒子中，在下列条件下，各有多少种投放方法？ 小球不同，盒子不同，盒子不空解：将小球分成3份，每份1，1，3或1，2，2。再放在3个不同的盒子中，即先分堆，后分配。有 小球不同，盒子不同，盒子可空 解：种小球不同，盒子相同，盒子不空解：只要将5个不同小球分成3份，分法为：1，1，3；1，2，2。共有=25种小球不同，盒子相同，盒子可空本题即是将5个不同小球分成1份，2份，3份的问题。共有种小球相同，盒子不同，盒子不空解：（隔板法）。0 00 00 ，有种方法小球相同，盒子不同，盒子可空解一：把5个小球及插入的2个隔板都设为小球（7个球）。7个球中任选两个变为隔板（可以相邻）。那么2块隔板分成3份的小球数对应于 相应的3个不同盒子。故有=21.解：分步插板法。小球相同，盒子相同，盒子不空解：5个相同的小球分成3份即可，有3，1，1；2，2，1。 共 2种小球相同，盒子相同，盒子可空解：只要将将5个相同小球分成1份，2份，3份即可。分法如下：5，0，0； 4，1，0； 3，2，0； 3，1，1； 2，2，1。例31、有4个不同的小球，放入4个不同的盒子内，球全部放入盒子内（1）共有几种放法？（答：）（2）恰有1个空盒，有几种放法？（答：）（3）恰有1个盒子内有2个球，有几种放法？（答：）（4）恰有2个盒子不放球，有几种放法？（答：）（十二）、涂色问题（1）用计数原理处理的问题，需要关注图形的特征：多少块？多少色？ （2）以涂色先后分步，以色的种类分类。例32、某城市在中心广场建造一个花圃，花圃分为6个部分（如下图）。现要栽种4种不同颜色的花，每部分栽种一种且相邻部分要能栽种同种颜色的花，则不同的栽种方法有多少种？法1：按对称区域颜色是否相同分类分析：四种不同的颜色涂在如图所示的6个区域，且相邻两个区域不能同色，只能选用4种颜色，要分四类： （1）与同色、与同色，则有； （2）与同色、与同色，则有； （3）与同色、与同色，则有； （4）与同色、 与同色，则有；（5）与同色、与同色，则有； 所以根据加法原理得涂色方法总数为5=120 。法2:转化法将其转化为空间图形如右图，转化为对点涂色。1号和其他5个区域都相邻，其他5个区域按逆时针顺序3个3个相邻，因此对这个5棱锥的涂色问题，可转化为用3种颜色对底面5边形进行涂色。第1步：对顶点1进行涂色，有种涂法；第2步：用剩余的3种颜色对平面5边形的顶点涂色，则必然有二组相对顶点同色，有如下五种分组方式：第一种：（2，4），（3，5），6；第二种：（2，4），（3，6），5；第三种：（2，5），（3，6），4；第四种：（2，5），（4，6），3；第五种：（3，5），（4，6），2.每种分组方式的涂色方法有种，根据分类、分步计数原理有种涂色方法。例33、将一个四棱锥的每一个顶点染上一种颜色，并使同一条棱的两端异色，若只有五种颜色可供使用，则不同的染色种数为 420 应该指出的是，上述所介绍的适用不同要求的各种方法并不是绝对的，对于同一问题有时会有多种方法，这时要认真思考和分析，灵活选取最佳方法。（十三）、不同元素进盒，先分堆再分配对于不同的元素放入几个不同的盒内，当有的盒内有不小于个元素时，不可分批进入，必须先分堆再分配。 例34、个老师分配到个班搞活动，每班至少一个，有几种不同的分法？ 解：先把位老师分堆，有两类：分布有种和分布有种，再排列到个班里有种，故共有种。 注意：不同的老师不可分批进入同一个班，须一次到位(否则有重复计数)。即“同一盒内的元素必须一次进入”。 （十四）、两类元素问题组合选位法例35、级楼梯，要求步走完，每步可跨一级，也可跨两级，问有几种不同的跨法？ 解：由题意知，有步跨单级，步跨两级，所以只要在步中任意选步跨两级即可。故有种跨法。 注意：两类元素的排列问题涉及面很广，应予重视。 例36、 沿图中的网格线从顶点到顶点，最短的路线有几条？ 解：每一种最短走法，都要走三段“|”线和四段“”线，这是两类元素不分顺序的排列问题。故有或种走法。 例37、从个班中选人组成校篮球队(无任何要求)，有几种选法？ 解：这个问题与例有区别，虽仍可看成块“档板”将个球分成格(构成个盒子)，是球与档板两类元素不分顺序的排列问题。但某些盒子中可能没有球，故块“档板”与个球一样也要参与排成一列而占位置，故有种选法。 （十五）、特殊元素（位置）优先法对于特殊元素的排列组合问题，一般先考虑特殊元素，再考虑其他元素的安排。在操作时，针对实际问题，有时“元素优先”，有时“位置优先”。 例38、这五个数字，组成没有重复数字的三位数，其中偶数共有几个？ 解法一：(元素优先)分两类：第一类：含，在个位有种，在十位有种；第二类：不含，有种。 故共有种。 注：在考虑每一类时，又要优先考虑个位。 解法二：(位置优先)分两类：第一类：在个位有种；第二类：不在个位，先从两个偶数中选一个放个位，再选一个放百位，最后考虑十位，有种。 故共有例39、电视台连续播放6个广告，其中含4个不同的商业广告和2个不同的公益广告，要求首尾必须播放公益广告，则共有 种不同的播放方式（结果用数值表示）.解：分二步：首尾必须播放公益广告的有A22种；中间4个为不同的商业广告有A44种，从而应当填 A22A4448. 从而应填48 （十六）、“小团体”排列，先“团体”后整体对于某些排列问题中的某些元素要求组成“小团体”时，可先按制约条件“组团”并视为一个元素再与其它元素排列。 例40、四名男歌手与两名女歌手联合举行一场演唱会，演出的出场顺序要求两名女歌手之间有两名男歌手，则出场方案有几种？ 解：先从四名男歌手中选人排入两女歌手之间进行“组团”有种，把这个“女男男女”小团体视为人再与其余男进行排列有种，由乘法原理，共有种(十七)、逐步试验法 如果题中附加条件增多,直接解决困难,用试验法寻找规律也是行之有效的方法例