排列组合问题解法

排列组合问题的求解策略杨昌叶求解排列组合的综合问题，一般是先选元素（组合），后排列，按元素的性质“分类”和按事件发生连续性过程“分步”，在计数时注意不重复，不遗漏。常见的解题策略有以下几种：特殊位置（或元素）优先安排例1.从6人中选4人分别到巴黎、伦敦、悉尼、莫斯科四个城市游览，要求每个城市有一人游览，每人只游览一个城市，且这6人中，甲、乙两人不去巴黎游览，则不同的选择方案共有（）A.300种B.240种C.144种D.96种（05年福建卷）解析：因为甲、乙不去巴黎，故从其余4人选1人去巴黎有q种方法，再从剩余5人中选3人去其余3市，有A|种方法，所以共有方案q人；=240（种），故选（B）。合理分类与准确分步例2.从集合｛O,P，Q，R，S｝与｛0，1，2，3,4，5，6,7，8，9｝中各任取2个元素排成一排（字母和数字均不能重复），每排中字母P、Q和数字0至多只出现一个的不同排法种数是（用数字作答）。（05年浙江卷）解析：（1）每排中只有数字0的排法有C9C2A4；（2）每排中只有字母P或Q的排法都有C1C92A4；（3）每排中无数字0，字母P、Q的排法有C2C2A4。所以不同的排法种数共有：（C1C2+2C1C2+C2C2）A4=84249339394排列、组合混合问题先选元（组合）后排列例3.四个不同的小球放入编号为1，2,3,4的四个盒子中，则恰有一个空盒的放法共种（用数字作答）。（全国高考）解析：先将4个球分成3组，每组至少1个（即必有一组为2个），分法有C2种，然后4再将这3组球放入4个盒子中每盒最多装一组，则恰有一个空盒的放法种数为C：A3=144（种）。正难则反、等价转化例4.在由数字0，1，2,3,4,5所组成的没有重复数字的四位数中，不能被5整除的数共有个。（05年全国卷）解析：用排除法解决。（1）总的四位数有C1A3；55（2）个位数字为0的四位数有A3；5（3）个位数字为5的四位数有C：A2。所以符合条件的四位数个数共有：CiA3-A3-C1A2=300-60-48=192另解：直接求有4x4xA2法（想一想，为什么？）相邻问题捆绑处理例5.四棱锥的8条棱代表8种不同的化工产品，有公共顶点的两条棱代表的化工产品放在同一仓库是危险的，没有公共顶点的两条棱代表的化工产品放在同一仓库是安全的，现打算用编号为①、②、③、④的4个仓库存放这8种化工产品，那么安全存放的不同放法种数为（）A,96B.48C.24D.0（05年江苏卷）解析：在四棱锥S-ABCD中（1）先把安全的产品捆绑在一起有2种方法（SA，CD），（SB，AD），（SC，AB），（SD，BC）；（SA，BC），（SB，CD），（SC，AD），（SD，AB）。（2）四组产品放在4个编号不同的仓库里有A：种，所以安全存放的方法共有：2A4=2x24=48（种）。4故选（B）。不相邻问题插空处理例6.用1，2,3,4,5,6,7,8组成没有重复数字的八位数，要求1与2相邻，3与4相邻，5与6相邻，而7与8不相邻，这样的八位数共有个（用数字作答）。（05年辽宁卷）解析：此题是捆绑法和插空法的综合应用问题。把相邻的两个数捆成一捆，分成四个空，然后再将7与8插进空中有A：种插法；而相邻的三捆都有A；种排法，再它们之间又有A33种排序方法。故这样的八位数共有：A2A2A2A3A2=8x6x12=576（个）22234定序问题排除处理例7.在7名运动员中选4名运动员组成接力队，参加4x100接力赛，那么甲、乙两人都不跑中间两棒的安排方法共有多少种？解析：先从7人中任选4人接力有A；种方法，排除甲和乙跑中间棒的2A；A3种方法，中小学教育网www.ehappystudy.^^mhfzp://www.ehappys/快乐学习，尽在中小学教育网TOC\o"1-5"\h\z但甲、乙二人都跑中间的减了两次，故再加上二人都跑中间棒的A2A2种方法，即25A4-2AiA3+A2A2=400（种）另解：直接求有A|A2法（想一想，为什么？）分排问题直接处理例8.有两排座位，前排11个座位，后排12个座位，现安排2人就座，规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是（）A.234B.346C.350D.363（04年辽宁卷）解析：在排列问题中，站若干排与站一排一样，故一共可坐的位子有20个，2个人就座方法数为A2，还需排除两人左右相邻的情况，把可坐的20座位排成连续一行（一排末位B20与二排首位C相接），任两个座位看成一个整体，即相邻的坐法有A19A2，但这其中包括B、C相邻与E、F（前排中间3座的左E、右F）相邻，而这种相邻在实际中是不相邻的，还应再加上2A;。所以不同排法的种数为：A20-A19A;+2A;=346故选B。构造模型例9.6本不同的书，按照以下要求处理，各有几种方法？（1）一堆一本，一堆两本，一堆三本；（2）甲得一本，乙得两本，丙得三本；（3）一人得一本，一人得二本，一人得三本；（4）平均分给甲、乙、丙三人；（5）平均分成三堆。解析：本问题中的每一小题都提出了一种类型问题，要搞清类型的归属。（1）属非均匀分组问题，先在6本书中任取一本，作为一堆，有C1种取法，再从余下的5本书中任取2本作为一堆，有C5种取法，最后余下的3本作为一堆有C3种取法，故共有分法：C1C2C3=60（种）653（2）属非均匀定向分配问题，与（1）同解，因每种分组方法仅对应一种分配方法，故也共有分法60种。（3）属非均匀不定向分配问题，由（1）知分成三堆有60种，但每一种分组方法又有A33种不同的分配方案，故共有分法60A3=360（种）。（4）属均匀定向分配问题，3个人一个一个地来取书，甲取有亳种，乙再去取有C2种，最后余下的归丙有C2种，故共有2C2C2C2=90（种）642（5）属均匀分组问题，把6本不同的书分成三堆，每堆2本与把6本不同的书分给甲、乙、丙三，每人2本的区别在于后者相当于把6本不同的书，平均分成三堆后再把分得的三堆书分给甲、乙、丙三个人，因此设把6本不同的书平均分成三堆的方法有x种，由（4）知把6本不同的书分给甲、乙、丙三人，每人2本的方法有C2C2C2种。642所以xA3=C2C2C23642则x=15（种）10.用“树型”图处理例10.设ABCDEF为正六边形，一只青蛙开始在顶点A处，它每次可随意地跳到相邻两个顶点之一，若在5次之内跳到D点，则停止跳动，若在5次之内不能到达D点，则跳完5次也停止跳动，那么这只青蛙从开始到停止，可能出现的不同跳法的种数是（）B.8A.6

C.1