排列组合问题常用方法(二十种).doc

解排列组合问题常用方法（二十种）
一、定位问题优先法（特殊元素和特殊位置优先法）
例、由可以组成多少个没有重复数字五位奇数？
分析：特殊元素和特殊位置有特殊要求，应优先考虑。末位和首位有特殊要求。先排末位，从三个数中任选一个共有种组合；然后排首位，从和剩余的两个奇数中任选一个共有种组合；最后排中间三个数，从剩余四个数中任选三个共有种排列。由分步计数原理得。
变式、种不同的花种在排成一列的花盆里，若两种葵花不种在中间，也不种在两端的花盆里，问有多 少不同的种法？
分析：先种两种不同的葵花在不受限制的四个花盒中共有种排列，再种其它葵花有种排列。由分步计数原理得。
二、相邻问题捆绑法
例、人站成一排 ，其中甲乙相邻且丙丁相邻，共有多少种不同的排法？
分析：分三步。先将甲乙两元素捆绑成整体并看成一个复合元素，将丙丁两元素也捆绑成整体看成一个复合元素，再与其它元素进行排列，同时在两对相邻元素内部进行自排。由分步计数原理得。
变式、某人射击枪，命中枪，枪命中恰好有枪连在一起的情形的不同种数为 。
分析：命中的三枪捆绑成一枪，与命中的另一枪插入未命中四枪形成的五个空位，共有种排列。
三、相离问题插空法
例、一个晚会节目有个舞蹈，个相声，个独唱，舞蹈不能连续出场，则节目出场顺序有多少种？
分析：相离问题即不相邻问题。分两步。第一步排个相声和个独唱共有种排列，第二步将个舞蹈插入第一步排好后形成的6个空位中（包含首尾两个空位）共有种排列，由分步计数原理得。
变式、某班新年联欢会原定的个节目已排成节目单，开演前又增加了两个新节目，如果将这两个新节
目插入原节目单中且不相邻，那么不同插法的种数为 。　
分析：将个新节目插入原定个节目排好后形成的6个空位中（包含首尾两个空位）共有种排列，
由分步计数原理得。
四、定序问题除序（去重复）、空位、插入法
例、人排队，其中甲、乙、丙人顺序一定，共有多少种不同的排法？
分析：（除序法）除序法也就是倍缩法或缩倍法。对于某几个元素顺序一定的排列问题，可先把这几个元素与其他元素一起进行排列，然后用总排列数除以这几个元素之间的全排列数。共有不同排法种数为：。
（空位法）设想有把椅子，让除甲、乙、丙以外的四人就坐，共有种坐法；甲、乙、丙坐其余的三个位置，共有种坐法。总共有种排法。
思考：可以先让甲乙丙就坐吗？（可以）
（插入法）先选三个座位让甲、乙、丙三人坐下，共有种选法；余下四个空座位让其余四人就坐，共有种坐法。总共有种排法。
变式、人身高各不相等，排成前后排，每排人，要求从左至右身高逐渐增加，共有多少种不同的
排法？
分析：人身高各不相等且从左至右身高逐渐增加，说明顺序一定。若排成一排，则只有一种排法；现排成前后两排，因此共有种排法。

五、平均分组问题倍除法（去重复法）
例、本不同的书平均分成堆，每堆本，有多少种不同的分法？
分析：分三步取书有种分法，但存在重复计数。记本书为，若第一步取，第二步取，第三步取，该分法记为，则在中还有、、、、共种分法 ，而这些分法仅是一种分法。总共应有种分法。平均分成的组，不管它们的顺序如何，都是一种情况，分组后一定要除以（为均分的组数），避免重复计数。
变式①、将个球队分成组，一组个队，其它两组个队，有多少种不同的分法？
分析：分三步。第一步取个队为一组，有种分法；余下个队平均分成两组，每组个队，有种分法，但存在重复计数。记个队为，若第二步取，第三步取，该分法记为，则在中还有共种分法，而这种分法是同一种分法。总共应有种分法。
变式②、名学生分成组，其中一组人，另两组人，正、副班长不能分在同一组，有多少种不同的分组方法？
分析：㈠总的分组方法：分三步。第一步取人为一组，有种分法；余下个人平均分成两组，每组个人，有种分法，但存在重复计数。记个人为，若第二步取，第三步取，该分法记为，则在中还有共种分法，而这种分法是同一种分法。总共应有种分法。
㈡正、副班长同分在人一组：分三步。第一步在人中取人，加上正、副班长共人为一组，有种分法；余下个人平均分成两组，每组个人，有种分法，但存在重复计数。记个人为，若第二步取，第三步取，该分法记为，则在中还有共种分法，而这种分法是同一种分法。总共应有种分法。
㈢正、副班长同分在人一组：分三步。第一步在人中取人，有种分法；第二步在余下的人中取人，有种分法；第三步余下人加上正、副班长形成一组，只有一种分法。总共应有种分法。
㈠减㈡减㈢得：总共有种分法。
变式③、某校高二年级共有个班级，现从外地转入名学生，要安排到该年级的两个班级且每班安
排名，则不同的安排种数为 。
分析：分三步。前两步将转入的名学生平均分成两组，每组名学生，有种分法，但存在重复计数。记名学生为，若第一步取，第二步取，该分法记为，则在中还有共种分法，而这种分法是同一种分法。第三步将分成的两组分配到个班级，有种分法。总共应有种分法。
六、元素相同问题隔板法
例、有个运动员名额，分给个班，每班至少一个，有多少种分配方案？
分析：隔板法也就是档板法。分两步。第一步：每班分配个名额，只有种分法；第二步：将剩下的个名额分配给个班。取块相同隔板，连同个相同名额排成一排，共个位置。由隔板法知，在个位置中任取个位置排上隔板，有种排法。每一种插板方法对应一种分法，由分步计数原理知，共有种分法。
变式①、个相同的球装入个盒中，每盒至少一球，有多少中装法？
分析：分两步。第一步：每盒先装入个球，只有种装法；第二步：将剩下的个球装入个盒中。取块相同隔板，连同个相同的球排成一排，共个位置。由隔板法知，在个位置中任取个位置排上隔板，有种排法。每一种插板方法对应一种装法，由分步计数原理知，共有种装法。
变式②、，求这个方程的自然数解的组数。
分析：取块相同隔板，连同个相同的排成一排，共个位置。由隔板法知，在个位置中任取个位置排上隔板，有种排法。每一种插板方法对应一组数，共有组数。
七、正难问题则反总体淘汰法（若直接法难，则用间接法）
例、从十个数字中取出三个，使其和为不小于的偶数，不同的取法有多少种？
分析：直接求不小于的偶数很困难，可用总体淘汰法。十个数字中有个偶数个奇数，所取的三个数字含有个偶数的取法有，只含有个偶数的取法有，和为偶数的取法共有。淘汰和小于的偶数共种、、、、、、、、，符合条件的取法共有。
变式、一个班有名同学，从中任抽人，正、副班长、团支部书记至少抽到一人的抽法有多少种?
分析：未抽到正、副班长、团支部书记的抽法有种；正、副班长、团支部书记至少抽到一人的抽法有种。
八、重排问题求幂法
例、把名实习生分配到个车间实习，共有多少种不同的分法？
分析：完成此事共分六步：把第一名实习生分配到车间有种分法，把第二名实习生分配到车间也有种分法，依此类推，由分步计数原理共有种不同的分法。
变式①、某班新年联欢会原定的个节目已排成节目单，开演前又增加了两个新节目，如果将这两个新节目插入原节目单中，那么不同插法的种数为 。
分析：完成此事共分两步：把第一个新节目插入原定个节目排后形成的六个空中，有种插法；把第二个新节目插入前面个节目排后形成的七个空中，有种插法。由分步计数原理共有种不同的插法。
变式②、某层大楼一楼电梯上来名乘客，他们到各自的一层下电梯，下电梯的下法有多少种？
分析：完成此事共分八步：第一名乘客下电梯有种下法，第二名乘客下电梯也有种下法，依此类推，由分步计数原理共有种不同的下法。
九、环（圆）排问题直排法
①环形排列问题：如果在圆周上个不同的位置编上不同的号码，那么从个不同的元素的中选取个不同的元素排在圆周上不同的位置，这种排列和直线排列是相同的；如果从个不同的元素的中选取个不同的元素排列在圆周上，位置没有编号，元素间的相对位置没有改变，不计顺逆方向，这种排列和直线排列是不同的，这就是环形排列的问题。
②环形排列数：
一个个元素的环形排列，相当于一个有个顶点的多边形，沿相邻两个点的弧线剪断，再拉直就是形成一个直线排列，即一个个元素的环形排列对应着个直线排列。
设从个元素中取出个元素组成的环形排列数为个，则对应的直线排列数为个。
又因为从个元素中取出个元素排成一排的排列数为个，所以，即。
③环形排列数公式：
㈠从个元素中取出个元素组成的环形排列数为。
㈡个元素的环形排列数为。
例、人围桌而坐，共有多少种坐法？
分析：围桌而坐与坐成一排的不同点在于坐成圆形没有首尾之分，所以固定一人并从此位置把圆形展成直线（如图所示），其余人共有种不同的坐法。

变式、颗颜色不同的钻石，可穿成几种钻石圈？　
分析：可穿成种不同的钻石圈。
十、多排问题单排法
例、人排成前后两排，每排人，其中甲、乙在前排，丙在后排，共有多少种排法？
分析：人排前后两排，相当于人坐把椅子，可以把椅子排成一排。先排前个位置上的个特殊元素甲、乙有种排法；再排后个位置上的个特殊元素丙有种；其余的人在个位置上任意排列有种。共有种不同的排法。排好后，按前人为前排，后人为后排分成两排即可。
变式、有两排座位，前排个座位，后排个座位。现安排人就坐，规定前排中间的个座位不能坐，并且这人不左右相邻，那么不同坐法的种数为 。
分析：①前后两排共有个座位。②前排中间第号个座位甲、乙二人不能坐。③甲、乙二人不能左右相邻。前排第号和后排第号个座位，甲、乙中任一人就坐，有种坐法，与之相邻座位只能排除一个，另一人有种坐法，共有种坐法；而其它个座位，甲、乙中任一人就坐，有种坐法，与之相邻座位要排除两个，另一人有种坐法，共有种坐法。总共有种不同坐法。
十一、排列组合混合问题先选后排法
例、有个不同的小球，装入个不同的盒内，每盒至少装一个球，共有多少种不同的装法？
分析：第一步从个球中选出个组成复合元素，有种方法；第二部把个元素（包含一个复合元素）装入个不同的盒内，有种方法。由分步计数原理得。
变式、一个班有名战士，其中正、副班长各人。现从中选人完成四种不同的任务，每人完成一种任务，且正、副班长有且只有人参加，则不同的选法有多少种？
分析：①正、副班长选一人，有种选法。②名战士选三人，有种选法。③给选出的人分配四种不同任务，有种分配法。由分步计数原理得。
十二、小集团问题先整体后局部法
例、用组成没有重复数字的五位数，其中恰有两个偶数在之间，这样的五位数有多少个？
分析：①两个偶数在之间是一个不能打破的小集团，在这个小集团之外。②把当作一个小集团与３排列，有种排法。③再排小集团内部。有种排法；也有种排法。由分步计数原理得。
变式①、计划展出幅不同的画，其中幅水彩画，幅油画，幅国画，排成一行陈列。要求同一品种的必须连在一起，并且水彩画不在两端，那么共有陈列方式的种数为 。
分析：幅油画是一个小集团，内部有种排法；幅国画也是一个小集团，内部有种排法；两个小集团排列，有种排法；将幅水彩画插入两个小集团排列后形成的一个空中，有种排法。由分步计数原理得。
变式②、男生和女生站成一排照像，男生相邻且女生也相邻的排法有 种。
分析：男生是一个小集团，内部有种排法；女生也是一个小集团，内部也有种排法；两个小集团排列，有种排法。由分步计数原理得。
十三、含约束条件问题合理分类与分步法
例、在一次演唱会上共名演员，其中人会唱歌，人会跳舞，现要演出一个人唱歌人伴舞的节目，有多少种选派方法？
分析：名演员中有人只会唱歌，人只会跳舞，人为全能演员。以选上唱歌人员为标准分三类，每一类中再分步：①只会唱歌的人中没有人选上唱歌人员，有种；②只会唱歌的人中只有人选上唱歌人员，有种；③只会唱歌的人中有人选上唱歌人员，有种。由分类计数原理得，共有种选派方法。
解含有约束条件的排列组合问题，可按元素的性质进行分类，按事件发生的连续过程分步。做到分类标准明确，贯穿解题过程始终；每一类中分步层次清楚，不重不漏。
本题还有如下分类标准：①以个全能演员是否选上唱歌人员为标准；②以个全能演员是否选上跳舞人员为标准；③以只会跳舞的人是否选上跳舞人员为标准。
变式①、从名男生和名女生中选出人参加某个座谈会，若这人中必须既有男生又有女生，则不同的选法共有 种。
分析：以选上女生为标准分三类，每一类中再分步：①选上女生人，有种；②选上女生人，有种；③选上女生人，有种。由分类计数原理得，共有种选派方法。本题还可以选上男生为标准分三类。
变式②、成人小孩乘船游玩，号船最多乘人，号船最多乘人，号船只能乘人，他们任选只船或只船，但小孩不能单独乘一只船，这人共有多少种乘船方法？
分析：分两大类。第一大类为选只船，则只能选号船和号船。以号船乘成人为标准，又可分为两小类：每一小类乘成人人，有种；每二小类乘成人人，有种。第二大类为选只船。以号船乘成人为标准，又可分为三小类，每一小类均有种。由分类计数原理得，共有种乘船方法。
十四、简单问题实际操作穷举法
例、设有编号，，，，的五个球和编号，，，，的五个盒子，现将个球放入个盒子内，要求每个盒子放个球，并且恰好有两个球的编号与盒子的编号相同，有多少种不同的放法？
分析：从个球中取出个与盒子对号，有种取法；剩下球盒不对号，利用实际操作法。如果剩下，，号球，，，号盒，号球只能装入号或号盒，有两种装法；当号球装号盒时，则，号球，只有种装法；同理号球装号盒时，，号球有也只有种装法。由分步计数原理有种。
变式、同一寝室4人，每人写一张贺年卡集中起来，然后每人各拿一张别人的贺年卡，则四张贺年卡不同的分配方式有多少种？
分析：设甲、乙、丙、丁4人，甲可拿乙、丙、丁的贺年卡。分三类。第一类：甲拿乙的，则乙可拿甲、丙、丁的，无论乙拿甲（或丙或丁）的，丙、丁的拿法都唯一，有种。第二类：甲拿丙的，则乙只能拿甲、丁的。若乙拿甲的，丙、丁的拿法唯一，有种；若乙拿丁的，则丙拿甲丁拿乙或丙拿乙丁拿甲，有种。小计有种。第三类：与第二类同理，有种。由分类计数原理知，共有种。
十五、数字排序问题查字典法
例、由，，，，，六个数字可以组成多少个没有重复的比大的数？
分析：数字排序问题可用查字典法。从高位向低位查，依次求出其符合要求的个数，根据分类计数原理求出其总数。①首位（十万位）为或，各有个；②首位为，万位为或，各有个；③首位为，万位为，千位为，有个；④首位为，万位为，千位为，百位为，有个；⑤首位为，万位为，千位为，百位为，十位为，有个。共有个。
变式、用，，，，，这六个数字组成没有重复的四位偶数，将这些数字从小到大排列起来，第个数是 。
分析：①千位为，个位为，有个；②千位为，个位为，有个；③千位为，个位为，有个；④千位为，个位为，有个；⑤千位为，个位为，有个；⑥千位为，十位为，个位为（或），各有个。共个。接下来有，，，，，，第个数是。
十六、复杂问题分解与合成法
分解与合成法是解排列组合问题的一种最基本的解题方法。把一个复杂问题分解成几个小问题逐一解决，然后依据问题分解后的结构，用分类计数原理和分步计数原理将问题合成。从而得到问题的答案。每个比较复杂的问题，都要用到这种解题方法。
例、能被多少个不同的偶数整除？
分析：先把分解成质因数的乘积形式。依题意可知：偶因数必先取，再从其余个因数中任取若干个组成乘积。所有的偶因数为：。
变式、正方体的个顶点可连成多少对异面直线？
分析：从个顶点中任取个顶点构成四面体共有个，每个四面体有对异面直线，正方体的个顶点可连成对异面直线。
十七、复杂问题转化归结法（化归法）
例、人排成方阵，现从中选人，要求人不在同一行也不在同一列，不同的选法有多少种？
分析：将问题退化成人排成方阵，现从中
选人，要求人不在同一行也不在同一列，有多少种
不同的选法？这样每行（列）有且只有人，从其中的
一行中选取人后，把这人所在的行列都划掉，如此继
续下去，从方队中选人的方法有种。再
从方阵选出方阵便可解决问题。从方队
A
B
中选取行列，有选法。所以从方阵选不在同一行也不在同一列的人有选法。
变式、某城市的街区由个全等的矩形区域组成，
其中实线表示马路，从走到的最短路径有多少种？
分析：将问题退化成从走到的最短路径需要
七步，四步向右三步向上，共有（或）种。
十八、复杂分类问题表格法
例、有红、黄、兰色的球各只，分别标有、、、、五个字母，现从中取只，要求各字母均有且三色齐备，则共有多少种不同的取法？
分析：一些复杂的分类选取题，要满足的条件比较多，无从入手，经常出现重复遗漏的情况，用表格法，则分类明确，能保证题中须满足的条件，达到好的效果。
红
1
1
1
2
2
3
黄
1
2
3
1
2
1
兰
3
2
1
2
1
1
取法

十九、运算困难问题树图法
例、人相互传球，由甲开始发球，并作为第一次传球，经过次传球后，球仍回到甲的手中，则不同的传球方式有 种？
解析：此题不易用公式进行运算，用树图法会收到意想不到的结果。

变式、 分别编有，，，，号码的人与椅，其中号人不坐号椅的不同坐法有多少种？
解析：树图法如下：

二十、不易理解问题构造模型法
例、马路上有编号为的九只路灯，现要关掉其中的盏，但不能关掉相邻的盏或盏，也不能关掉两端的盏，求满足条件的关灯方法有多少种？
分析：此问题可转化为排队模型。在盏亮灯形成的个空隙中，插入盏不亮的灯，有 种。
一些不易理解的排列组合问题可转化为熟悉的模型，使问题直观化。
变式、某排共有个座位，若人就坐，每人左右两边都有空位，那么不同的坐法有多少种？（120）
分析：每人坐一个座位,还剩个。把这个座位,插入个人,且两头必须有座位,两人之间至少有一个座位。用表示个空座位,用表示个人。①；②；③；④；⑤。有种。又，这个人的坐法有顺序,共有：种。
此问题也可转化为排队模型。每人坐一个座位,还剩个。这个座位排成一排，可迭相邻的两个座位，
有种迭法。跌后有个座位形成个空隙（不包括两端），插入个人，有种。又，这个人的坐法有顺序,共有：种。

8