《排列组合问题的基本类型及解题方法》由会员分享，可在线阅读，更多相关《排列组合问题的基本类型及解题方法（6页珍藏版）》请在金锄头文库上搜索。
1、排列组合问题的基本类型及解题方法排列组合问题的基本类型及解题方法解决排列组合问题要讲究策略，首先要认真审题，弄清楚是排列(有序)还是组合(无序)，还是排列与组合混合问题。其次，要抓住问题的本质特征，准确合理地利用两个基本原则进行“分类与分步”。加法原理的特征是分类解决问题，分类必须满足两个条件：类与类必须互斥(不相容)，总类必须完备(不遗漏)；乘法原理的特征是分步解决问题，分步必须做到步与步互相独立，互不干扰并确保连续性。分类与分步是解决排列组合问题的最基本的思想策略，在实际操作中往往是“步”与“类”交叉，有机结合，可以是类中有步，也可以是步中有类。以上解题思路分析，可以用顺口溜概括为：审明题
2、意，排组分清；合理分类，用准加乘；周密思考，防漏防重；直接间接，思路可循；元素位置，特殊先行；一题多解，检验真伪。一特殊元素的“优先安排法”一特殊元素的“优先安排法”对于特殊元素的排列组合问题，一般先考虑特殊元素，再考虑其他元素的安排。在操作时，针对实际问题，有时“元素优先”，有时“位置优先”。例例 1 1：0,2,3,4,5这五个数字，组成没有重复数字的三位数，其中偶数共有几个？解法一：解法一：(元素优先)分两类：第一类，含0，0在个位有A4种，0在十位有A2A3种；1221112第二类，不含0，有A2A3种。 故共有(A4 A2A3)+A2A3 30种。211注：注：在考虑每一类时，又要优
3、先考虑个位。解法二：解法二：(位置优先)分两类：第一类，0在个位有A4种；第二类，0不在个位，先从两个偶数中选一个放个位，再选一个放百位，最后考虑十位，有A2A3A3种。故共有A4+A2A3A3=30二总体淘汰法二总体淘汰法对于含有否认词语的问题，还可以从总体中把不符合要求的除去，此时应注意既不能多减也不能少减，例如在例1中也可以用此法解答：5个数字组成三位数的全排列为A5，排好后发现0不能在首位，而且3和5不能排在末尾，这两种不合题意的排法要除去，故有30个偶数三合理分类与准确分步三合理分类与准确分步解含有约束条件的排列组合问题，应按元素的性质进行分类，事情的发生的连续过程分步，做到分类标准
4、明确，分布层次清楚，不重不漏例例 2 2：5个人从左到右站成一排，甲不站排头，乙不站第二个位置，不同的站法有解解：由题意，可先安排甲，并按其进行分类讨论：1假设甲在第二个位置上，则剩下的四人可自由安排，有A4种方法；2假设甲在第三个或第四个位置上，则根据分布计数原理不同的站法有A3A3A3种站2113法；再根据分类计数原理，不同的站法共有：A4 A3A3A3 78种2111211134113四相邻问题：捆绑法四相邻问题：捆绑法对于某些元素要求相邻排列的问题， 可先将相邻元素捆绑成整体并看作一个元素再与其它元素进行排列，同时对相邻元素内部进行自排。例例 3 3：5个男生3个女生排成一列，要求女生
5、排一起，共有几种排法？1解：解：先把3个女生捆绑为一个整体再与其他5个男生全排列。同时，3个女生自身也应全排列。由乘法原理共有A6A3种。五不相邻问题用“插空法”五不相邻问题用“插空法”对于某几个元素不相邻的排列问题， 可先将其他元素排好， 再将不相邻的元素在已排好的元素之间及两端的空隙之间插入即可注意有时候两端的空隙的插法是不符合题意的.例例 4 4：5个男生3个女生排成一列，要求女生不相邻且不可排两头，共有几种排法？解：解： 先排无限制条件的男生， 女生插在5个男生间的4个空隙， 由乘法原理共有A5A4种。注意：注意：分清“谁插入谁”的问题。要先排无限制条件的元素，再插入必须间隔的元素；数
6、清可插的位置数；插入时是以组合形式插入还是以排列形式插入要把握准。例例 5 5：马路上有编号为1,2,3,9的9盏路灯，现要关掉其中的三盏，但不能同时关掉相邻的两盏或三盏，也不能关两端的路灯，则满足要求的关灯方法有几种？解：解：由于问题中有6盏亮3盏暗，又两端不可暗，故可在6盏亮的5个间隙中插入3个暗的即可，有C5种。六顺序固定问题用“除法”或选位不排或先定后插六顺序固定问题用“除法”或选位不排或先定后插对于某几个元素顺序一定的排列问题，可先把这几个元素与其他元素一起进行排列，然后用总排列数除以这几个元素之间的全排列数。或先在总位置中选出顺序一定元素的位置而不参加排列，然后对其它元素进行排列。
7、也可先放好顺序一定元素，再一一插入其它元素。例例 6 6：5人参加百米跑，假设无同时到达终点的情况，则甲比乙先到有几种情况？解法一：解法一：先5人全排有A5种，由于全排中有甲、乙的全排种数A2，而这里只有1种是5235363A5符合要求的，故要除以定序元素的全排列A种，所以有5=60种。2A223解法二：解法二： 先在5个位置中选2个位置放定序元素(甲、 乙)有C5种， 再排列其它3人有A3，22由乘法原理得共有C5A3=60种。解法三：解法三：先固定甲、乙，再插入另三个中的第一人有3种方法，接着插入第二人有4种方法，最后插入第三人有5种方法。由乘法原理得共有345=60种。七“小团体”排列，
8、先“团体”后整体七“小团体”排列，先“团体”后整体对于某些排列问题中的某些元素要求组成“小团体”时，可先按制约条件“组团”并视为一个元素再与其它元素排列。例例 7:7:四名男歌手与两名女歌手联合举行一场演唱会，演出的出场顺序要求两名女歌手之间有两名男歌手，则出场方案有几种？解：解：先从四名男歌手中选2人排入两女歌手之间进行“组团”有A4A2种，把这个“女男33男女”小团体视为1人再与其余2男进行排列有A3种，由乘法原理，共有A4A2A3222223种八分排问题用“直排法”八分排问题用“直排法”把n个元素排成假设干排的问题， 假设没其他的特殊要求， 可用统一排成一排的方法来处理例例 8 8：7个
9、人坐两排座位，第一排坐3人，第二排坐4人，则有种排法2解：解：7个人， 可以在前后两排随意就座， 没有其他的限制条件， 故两排可以看成一排来处理，所以不同的坐法有A7( (九九) )逐步试验法逐步试验法如果题中附加条件增多,直接解决困难,用试验法寻找规律有时也是行之有效的方法例例 9 9：将数字1,2,3,4填入标号为1,2,3,4的四个方格内，每个方格填一个，则每个方格的标号与所填的数字均不相同的填法种数有种。解：解：此题考查排列的定义，由于附加条件较多，解法较为复杂，可用试验法逐步解决第一方格内可填2或3或4如填2，则第二方格内可填1或3或4假设第二方格内填1,则第三方格内只能填4，第四方
10、格内填3假设第二方格填3，则第三方格应填4，第四方格应填1同理，假设第二方格填4，则第三、四方格应分别填3，1。因而第一方格填2共有3种方法。同理，第一格填3或4也各有3种，所以一共有9种方法。十探索规律法十探索规律法对于情况复杂，不易发现其规律的问题需要仔细分析，探索出其中规律，再予以解决。例例 1010：从1到100的自然数中，每次取出不同的两个数，使他们的和大于100，则不同的取法种数有种。解：解：此题的数字较多，情况也不一样，需要分析摸索其规律。为方便，两个加数中较小的为被加数，1100 101100，1为被加数的有1种；同理，2为被加数的有2种；3为被加数的有3种；49为被加数的有4
11、9种；50为被加数的有50种；但51为被加数的只有49种；52为被加数的只有48种；99为被加数的只有1种，故不同的区法有：(12350)(49481) 2500种。十一十一 “住店”问题“住店”问题解决“允许重复排列”的问题要注意区分两类元素：一类元素可重复， 另一类元素不能重复。把不能重复的元素看着“客” ，能重复的元素看着“店” ，再利用分步计数原理直接求解的方法称为“住店法” 。例例 1111：7名学生争夺五项冠军，获得冠军的可能种数是种。解：解：应同一学生可同时夺得n项冠军，故学生可重复排列，将7名学生看着7家“店” ，五项冠军看着5名“客” ，每个客有7种住宿方法，由分步计数原理得
12、N=7种。十二特征分析法十二特征分析法有约束条件的排数问题， 必须紧扣题中所提供的数字和结构特征， 进行推理， 分析求解。例例 1212：由1,2,3,4,5,6六个数可组成多少个无重复且是6的倍数的五位数？解：解： 分析数字的特征：6的倍数的数既是2的倍数， 又是3的倍数。 其中3的倍数又满足 “各个数位上的数字之和是3的倍数”的特征。而且126 21是3的倍数，从6个数字中取5个，使之和还是3的倍数，则所去掉的数字只能是3或6。因而可以分两类讨论：第一类，所排的五位数不含3，即由1,2,3,4,5,6作数码；首先从2,4,6三个中任选一个作个1114位数字有A3种，然后其余4个数字在其他数
13、位上的全排列有A4，所以N1 A3A4；第二7514类 ， 所 排 的 五 位 数 不 含6， 即 由1,2,3,4,5作 数 码 ， 依 上 法 有N2 A2A4， 故N=N1 N2120种。十三相同元素进盒，用档板分隔十三相同元素进盒，用档板分隔例例 1313：10张参观公园的门票分给5个班，每班至少1张，有几种选法？3解：解：这里只是票数而已，与顺序无关，故可把10张票看成10个相同的小球放入5个不同的盒内， 每盒至少1球， 可先把10球排成一列， 再在其中9个间隔中选4个位置插入4块“档板”分成5格(构成5个盒子)有C9种方法。注：注：档板分隔模型专门用来解答同种元素的分配问题。十四个
14、数不少于盒子编号数，先填满再分隔十四个数不少于盒子编号数，先填满再分隔例例 1414：15个相同的球放入编号为1,2,3的盒子内，盒内球数不少于编号数，有几种不同的放法？解：解：先用6个球按编号数“填满”各盒(符合起码要求),再把9个球放入3个盒内即可,可用2块档板与9个球一起排列(即为两类元素的排列问题),有C11种。十五不同元素进盒，先分堆再排列十五不同元素进盒，先分堆再排列对于不同的元素放入几个不同的盒内，当有的盒内有不小于2个元素时，不可分批进入，必须先分堆再排入。例例 1515：5个老师分配到3个班搞活动，每班至少一个，有几种不同的分法？122C5C4C2解：解：先把5位老师分3堆，
15、有两类：3,1,1分布有C种和1,2,2分布有种，再排2A23524列到3个班里有A33种，故共有122C5C4C23(C)A3种。2A235注意：注意：不同的老师不可分批进入同一个班，须一次到位(否则有重复计数)。即“同一盒内的元素必须一次进入”。十六两类元素的排列，用组合选位法十六两类元素的排列，用组合选位法例例 1616：10级楼梯， 要求7步走完， 每步可跨一级， 也可跨两级， 问有几种不同的跨法？解：解：由题意知，有4步跨单级，3步跨两级，所以只要在7步中任意选3步跨两级即可。故有C7种跨法。注意：注意：两类元素的排列问题涉及面很广，应予重视。例例 1717：沿图中的网格线从顶点A到
16、顶点B， 最短的路线有几条？解：解：每一种最短走法，都要走三段“|”线和四段“”线，这是两类元素不分顺序的排列问题。故有C7或C7种走法。例例 1818：从5个班中选10人组成校篮球队(无任何要求)，有几种选法？解：解： 这个问题与例12有区别， 虽仍可看成4块“档板”将10个球分成5格(构成5个盒子)， 是球与档板两类元素不分顺序的排列问题。 但某些盒子中可能没有球， 故4块“档板”与10个球一样也要参与排成一列而占位置，故有C14种选法。注意：注意：怎样把问题等价转化为“两类元素的排列”问题是解题的关键。4334十七元素交叉问题集合法所谓集合思想，就是运用集合的概念、逻辑语言、运算、图形等
17、来解决数学问题或非纯数学问题的思想方法。利用集合思想解决排列组合问题，可以使抽象4的数学问题具体化，也可以防止在分类或分步的过程中出现重复和遗漏问题。在利用集合思想求解时，要借助于以下一组公式，它们容易用文氏图来验证。1. 德摩根定律：2. 容斥原理：假设用=下面举例说明：例 1. 从 6 名运发动中选出 4 名参加跑第四棒，共有多少种不同的参赛方法？解：设全集接力赛，如果甲不跑第一棒，乙不表示有限集合 A 中的元素的个数， 则对于任意集合 A、 B， 有。特殊的，。，根据容斥原理得参赛方法共有：答：共有 252 种不同的参赛方法。例 2. 高一3班的学生中，参加课外语文小组的有20 人，参加
18、数学小组的有22 人，既参加语文又参加数学小组的有10 人，既未参加语文又未参加数学小组的有 15 人，问高一3班共有多少学生？解：设由容斥原理及德摩根定律：5答：高一3班共有学生 47 人。例 3. 由数字 1、2、3、4、5 可以组成多少个无重复数字且 2、3 都与 4 不相邻的五位数。解：设，由容斥原理及德摩根定律：则原题即求注：表示 2 与 4 相邻且 3 与 4 相邻的五位数的个数，那么 4 一定排在 2种排法。与 3 之间，且 2、3、4 相邻，故有从以上三例可以看出，用集合思想处理排列组合问题，既可使问题正确归类，又可防止重复、遗漏现象，且思路清晰，层次分明，能有效地防止错误。以上介绍了排列组合应用题的几种常见求解策略，这些策略不是彼此孤立的,而是相互依存的，相互为用的。有时解决某一问题时要综合运用几种求解策略。6
