排列组合典型题解“十法”

排列组合典型题解“十法”排列组合历来是学习中的难点，通过研究历届的高考试题，我们不难发现其应用题的特 点是条件隐晦，难以挖掘，题目多变，解法独特，数字庞大，难以验证。解排列组合问题 首先必须认真审题，明确问题是否是排列组合问题，其次是抓住问题的本质特征，灵活运用 基本原理和公式进行分析解答，同时，还要注意讲究一些基本策略和方法技巧，使一些看似 复杂的问题迎刃而解。下面就不同的题型介绍几种常用的解题技巧。一. 特殊元素（位置）“优先法”把有限制条件的元素（位置）称为特殊元素（位置），对于这类问题一般采取特殊元素 （位置）优先安排的方法。例1. 6 人站成一横排，其中甲不站左端也不站右端，有多少种不同站法？分析：解有限制条件的元素（位置）这类问题常采取特殊元素（位置）优先安排的方法。解法 1：（元素分析法）因为甲不能站左右两端，故第一步先让甲排在左右两端之间的任一位置上，有Ai种站法；第二步再让其余的5人站在其他5个位置上，有A5种站法，故 45站法共有：Ai - A5 =480 （种）45解法 2：（位置分析法）因为左右两端不站甲，故第一步先从甲以外的 5 个人中任选两人站在左右两端，有A2种；第二步再让剩余的4个人（含甲）站在中间4个位置，有A4种，54故站法共有：A2 - A4 = 480 （种）54例2.用 0， 1， 2， 3， 4这五个数，组成没有重复数字的三位数，其中偶数共有（ ）A.24 B.30 C.40 D.60 分析：由于该三位数是偶数，所以末尾数字必须是偶数， 又因为0 不能排首位，故 0就是其中的“特殊”元素，应优先安排。按0 排在末尾和不排在末尾分为两类；1）0排在末尾时，有A2个；42）0不排在末尾时，先用偶数排个位，再排百位，最后排十位有AiAiAi个；233由分类计数原理，共有偶数 30 个.例3.在由数字0，1, 2, 3, 4, 5所组成的没有重复数字的四位数中，不能被5整除的数共有个解：不能被5整除的有两种情况：情况1、首位为5有A1 A2种；情况2、首位不是5的有44种，故在由数字0， 1， 2， 3， 4， 5所组成的没有重复数字的四位数中，不能被5整除的数共有Ai A2 + Ai AiA2 = 192 （个）.4 44 3 4例4.将 4 名教师分派到3 所中学任教，每所中学至少1 名教师，则不同的分派方案共有多少种？解：可分两步进行：第一步先将4 名教师分为三组（1，1，2），（2，1，1），（1，2，1），C 2 - C i - C i共有：尸一二6 （种）第二步将这三组教师分派到3种中学任教有A3种方法。由A232C 2 - C i - C i ,分步计数原理得不同的分派方案共有：一- A3 = 36 （种）因此共有36种方案。A232练习：（1）0,1,2,3,4,5 这六个数字可组成多少个无重复数字的五位数？Ai A4 二 60055（2）0， 1， 2， 3， 4， 5 可组成多少个无重复数字的五位奇数？Ai Ai A3 二 288344（3）五个工程队承建某项工程的5 个不同的子项目，每个工程队承建1 项，其中甲工程队 不能承建1号子项目，则不同的承建方案共有（AiA4）种。44一、相邻问题“捆绑法”对于要求某几个元素必须排在一起的问题，可用“捆绑法”：可先将相邻的元素“捆绑” 在一起，看作一个“大”的元（组），与其它元素排列，然后再对相邻的元素（组）内部进 行排列。例5. 7 人站成一排照相，要求甲，乙，丙三人相邻，分别有多少种站法？分析：先将甲，乙，丙三人捆绑在一起看作一个元素，与其余4人共有 5个元素做全排列，有A5种排法，然后对甲，乙，丙三人进行全排列。由分步计数原理可得：A5A3种不553同排法。例6.5个男生和3 个女生排成一排， 3 个女生必须排在一起，有多少种不同排法？解：把3个女生视为一个元素，与5个男生进行排列，共有A6种，然后女生内部再进 6行排列，有A3种，所以排法共有：A6 - A3 = 4320 （种）363练习：求不同的排法种数：（i） 6 男 2 女排成一排， 2女相邻；（2） 4男 4 女排成一排，同性者相邻；解：（1）是“相邻”问题，用捆绑法解决：A2A7.(2)是“相邻”问题，应先捆绑后排位 ： A 4 A 4 A2 .442二、不相邻问题“插空法”元素相离(即不相邻)问题，可以先将其他元素排好，然后再将不相邻的元素插入已排 好的元素位置之间和两端的空中。例7. 7人排成一排，甲、乙、丙3 人互不相邻有多少种排法？解：先将其余4人排成一排，有A4种，再往4人之间及两端的5个空位中让甲、乙、4丙插入，有A3种，所以排法共有：A4 - A3 = 1440 (种)545引申：( 1)三个男生，四个女生排成一排，男生、女生各站一起，有几种不同方法？(2)三个男生，四个女生排成一排，男生之间、女生之间不相邻，有几种不同排法？例8.(熄灯问题)某城市新建的一条道路上有12只路灯，为节约用电而不影响照明， 可以熄灭其中三盏灯，但是两端的灯不能熄灭，也不能熄灭相邻的两盏灯，熄灯方法共有( B )种。A. C 3B. C3C. C3D. C 312 8 9 11解：直接考虑比较困难，但我们稍加变化，即能转化成我们熟悉的问题，即： 9 个相同的A和3个相同的B排成一列，要求B不排在两端，也不相邻，此时只需将B插 入到9个A中即运用插空法可解决。例9.用1、2、3、4、5、6、7、8组成没有重复数字的八位数，要求1与2相邻， 3与4相邻，5与6相邻，而7与8不相邻，这样的八位数共有个.(用数字作答)解：将1与2，3与4,5与6捆绑在一起排成一列有A2 - 23种，再将7、8插入4个3空位中的两个，有A2种，故有A2 - 23 - A2二576种.434练习：求不同的排法种数：(1) 6 男 2 女排成一排， 2 女不能相邻；(2) 4 男 4 女排成一排，同性者不能相邻.解：(1)是 “不相邻”问题，可以用插空法直接求解. 6男先排实位，再在7个空位中排2女，即用插空法解决： A6A2.67(2)是 “不相邻”问题，可以用插空法直接求解: A4 A3 A1 .442三、定序问题“除法”对于在排列中，当某些元素次序一定时，可用此法。解题方法是：先将!个元素进行全排列有An种，m(m n)个元素的全排列有Am种，由于要求m个元素次序一定，因此只 nm能取其中的某一种排法，可以利用除法起到调序的作用，即若n个元素排成一列，其中mAn个元素次序一定，则有J*种排列方法。Amm例10. 有 4 名男生， 3名女生。 3名女生高矮互不等，将7名学生排成一行，要求从左到 右，女生从矮到高排列，有多少种排法？分析：先在7个位置上作全排列，有A7种排法。其中3个女生因要求“从矮到高”排,7A7只有一种顺序，故A3只对应一种排法，所以共有十=A4种。3A 373例11.由数字 0、1、2、3、4、5 组成没有重复数字的六位数，其中个位数字小于十位数字的六位数有多少个？解：不考虑限制条件，组成的六位数有Ai - A5种，其中个位与十位上的数字一定，所 55以所求的六位数有：Ai - A555 二 300 (个)A22例12.6个人排队，甲、乙、丙三人按“甲-乙-丙”顺序排的排队方法有多少种？分析： 不考虑附加条件，排队方法有A6种，而其中甲、乙、丙的A3种排法中只有一 63种符合条件。故符合条件的排法有A6 - A3 = 120种。63例13.某班新年联欢会原定的5个节目已排成节目单,开演前有增加了2个新节目,如果将这两节目插入节目单中,那么不同的插法种数为.解:实质是7个节目的排列,因原定的 5个节目顺序不改变,故排这 5个节目是一个组合，有C点评： 排列与组合的根本区别是元素之间有否顺序.若元素之间交换次序后是两种不 同的情形，则是排列问题;若元素之间交换次序后是相同的情形，则是组合问题;另外若元素 之间已经规定了顺序， 则仍是组合问题。练习：三个男生，四个女生排成一排，其中甲、乙、丙三人的顺序不变，有几种不同排法？A7 7A3种方法，在排新插入的两个节目有A2种方法，故C5A2二42727 2四、指标问题“隔板法”解决指标分配、相同的元素分割、不定方程的正整数解的个数等. 如 n 个 相同小球放入m(mWn)个盒子里，要求每个盒子里至少有一个小球的放法等价于n个相同小球串成一串 从n-1个间隙里选m-1个结点剪成m段(或者看作插入m1块隔板)，有Cm-1种方法.n-1例14.有10个三好学生名额，分配到6个班，每班至少1个名额，共有多少种不同的分配方案？解：6个班，可用 5个隔板，将10 个名额并排成一排，名额之间有9个空，将5个隔板插入9个空，每一种插法，对应一种分配方案，故方案有：C5 二 126 (种)9例15.方程x + y + z + w二12有多少组正整数解？分析：建立隔板模型：将12个完全相同的球排成一列，在它们之间形成的11个间隙中任意插入3块隔板，把球分成4堆，而每一种分法所得4堆球的各堆球的数目，即为a,b,c,d的一组正整解，故原方程的正整数解的组数共有C3二165。11引申：(1)求不等式x + y + z 0)，这时问题也就是例子14 了，因为他们是对应的。再如方程a+b+c+d=12非负整数解的个数；三项式(a + b + c)10,四项式(a + b + c + d )10等展开式的项数，经过转化后都可用此法解。(2)方程x + x + x + x二8的非负整数解的组数是多少？1234分析：设y二x + 1(i二1,2,3,4),则y 1,原题即转换为y + y + y + y二12有多i ii1234少正整数解。可由抽象到具体建立如下模型：将12个小球排成一列，在它们两之间形成的缝隙中任意插入3块木板，则把这12个球分成4组，而这4组的数目即为y ,y ,y ,y ,即1234原方程的非负整数解是：C3二165 (组).11例16. 把9个相同小球放入其编号为1、2、3的三个箱子里，要求每个箱子放球的个数不小于其编号数， 则不同的放球方法共有种.解:先给编号为2、3的三个箱子里分别放入1 个、2个小球(先保证编号为2、3的箱 子里放球的个数与其编号数相差1) ，有1种方法；再将剩余的6个小球串成一串，用隔板法截为三段有C2二10种截断法，对应放到编号为1、2、3的三个箱子里.5因此，不同的放球方法有1X10=10种.例17.某校准备参加2005年高中数学联赛,把10个选手名额分配到高三年级的8 个教学班,每班至少一个名额,则不同的分配方案共有_种.解：这是指标分配问题，等价于把10个相同小球放入8个盒子里,每个盒子至少有一个小球 的放法种数问题.将10个小球串成一串，用隔板法截为8段有C7二36种截断法，对应放到8个盒子里.9因此，不同的分配方案共有 36 种.练习：（1）将 10个学生干部的培训指标分配给7 个不同的班级，每班至少分到一个名额，不同的分配方案共有（C6 = 84 ）种。9（2）不定方程x + x + x + + x = 10的正整数解共有（C6 = 84 ）组12379五、分排问题“直排法”对于把几个元素分成若干排的排列问题，若没有其他特殊要求，可采取统一成一排的方 法求解。例18.9 个人坐成三排，第一排2 人，第二排3人，第三排4 人，则不同的坐法共有多少种？解：9 个人可以在三排中随意就坐，无其他限制条件，所以三排可以看作一排来处理，不同的坐标共有A9种。9例19.7个人坐两排座位，第一排3个人，第二排坐4个人，则不同的坐法有多少种？分析：7 个人可以在前两排随意就坐，再无其它条件，故两排可看作一排来处理，不同的坐法共有A7种。7六、重复问题“住店法”解决“允许重复排列问题”要注意区分两类元素：一类元素可以重复，另一类不能重复把不能重复的元素看作“客”，能重复的元素看作“店”，再利用乘法原理直接求解。例20.七名学生争夺五项冠军，每项冠军只能由一人获得，获得冠军的可能的种数有（）A. 75 B. 57 C. A5 D. C 577分析：因同一学生可以同时夺得n项冠军，故学生可重复排列，将七名学生看作7家“店” 五项冠军看作5名“客”，每个“客”有7 种住宿法，由乘法原理得75种。注：对此类问题，常有疑惑，为什么不是57 呢？用分步计数原理看，5 是步骤数，自然是指数。练习： 在一次运动会上有四项比赛的冠军在甲、乙、丙三人中产生，那么不同的夺冠情况共有（） 种.（A） A 3（B） 43（C）34（D）C344 解：四项比赛的冠军依次在甲、乙、丙三人中选取，每项冠军都有3 种选取方法，由乘 法原理共有3x 3x 3 x 3 = 34种.七、复杂问题“排除法”对于某些比较复杂的或抽象的排列问题，可以采用转化思想，从问题的反面去考虑，先 求出无限制条件的方法种数，然后去掉不符合条件的方法种数。在应用此法时要注意做到不 重不漏。例21.某班里有 43 位同学，从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种?分析：此题若是直接去考虑的话,就要将问题分成好几种情况，这样解题的话,容易造成各种 情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话，不但容易理解，而且在 计算中也是非常的简便.这样就可以简化计算过程.解：43人中任抽5人的方法有C5种，正副班长，团支部书记都不在内的抽法有C5种，所4340以正副班长，团支部书记至少有1人在内的抽法有C5 -C5种.4340例22.四面体的顶点和各棱中点共有10个点，取其中4个不共面的点，则不同的取法共有（ ）A. 150种B. 147种C. 144种D. 141种解：从10个点中任取4个点有C4种取法，其中4点共面的情况有三类。第一类，取10出的4个点位于四面体的同一个面内，有4C4种；第二类，取任一条棱上的3个点及该棱6对棱的中点，这4点共面，有6种；第三类，由中位线构成的平行四边形（其两组对边分别 平行于四面体相对的两条棱），它的4个点共面，有3种。以上三类情况不合要求应减掉，所以不同的取法共有：C4 -4C4 -6-3 = 141 （种）。10 6 点评：为求完成某件事的方法种数,如果我们分步考虑时,会出现某一步的方法种数不确定或计数有重复,就要考虑用分类法,分类法是解决复杂问题的有效手段,而当正面分类情况 种数较多时,则就考虑用间接法计数.“排除法”特殊运用：n 个元素排成一列,求某两个元素各自不排在某两个确定位置的排法种数, 也可以使用 排除法”.根据集合图，我们可以得到如下规律：若n个不同元素排m个位，a、b各自不排在某两个确定位置，则有Am - 2Aml + Am2nn-1n-2例23.将 A、 B、 C、 D、 E、 F 六个不同的电子元件在线路上排成一排组成一个电路,如果元件 A 不排在始端,元件 B 不排在末端,那么这六个电子元件组成不同的电路的种数是解：不考虑限制条件共有A6种排法，元件A排在始端和B排在末端各有A5种排法，把它 65们都剔除，则A排在始端同时B排在末端的总数多减了一次，需补上A4种故组成不同的电路4A6 2A5 + A4 二 504 种.654练习：（1）五人从左到右站成一排，其中甲不站排头，乙不站第二个位置，那么不同的站法有（）A.120 B.96 C.78 D.72A5 2A4 + A3 二 78543（2）6个同学和 2个老师排成一排照相， 2个老师站中间，学生甲不站排头，学生乙不站 排尾，共有多少种不同的排法？（A6 2A5 + A4） A2 二 10086542八、分配问题“分组法”我们知道：Cm的定义是指：从n个不同元素中任取m个元素的所有不同组合的个数。n事实上，我们可以将Cm理解为对n个元素进行了分组（两个组）：其中m个元素为一组, nn剩下的n-m个元素自然形成一组，当m丰时,Cm就是所有不同的分成两组的方法种数,nn而当m二时，是将n个元素平均分成了两组,不同的分组方法数为导。关于将n个元素分成m个组的分法种数，我们有下面的结论:（1）若 k + k + k + +k =n 且 k , k , k ,k 互不相等，123m123m则将n个元素分成m个组（其中第一个组k个元素，第二个组k个元素，第n个组k个元12m素）的不同分法种数为Ck1 Ck2 Ck3Ckmn n k1 n k1 -k2km（2）若将n个元素平均分成m个组，每组k个元素（n=mk）,则所有不同的分法种数为C k C k Ckkm(m.1) kkAkk（注:关于部分平均分组问题的分组方法数，要视具体要求而定。）例24. 将6本不同的书分别按下面的方式分配，共有多少种不同的分配方法？分给学生甲3 本，学生乙2本，学生丙1本；分给甲、乙、丙3人，其中1人得3本、1人得2本、1人得1本；分给甲、乙、丙3人，每人2本；分成3堆，一堆3本，一堆2本，一堆1本；分成3堆，每堆2本。分给分给甲、乙、丙3人，其中一人4本，另两人每人1本；分成3堆，其中一堆4本，另两堆每堆1本。分析：分书过程中要分清：是均匀的还是非均匀的；是有序的还是无序的。特别是均匀的分法中要注意算法中的重复问题。注意：有序不等分；有序等分；有序局部等分；无序不等分；无序等分；无序 局部等分。解：（1）是指定人应得数量的非均匀问题：方法数为C 3C 2C1 ；631是没有指定人应得数量的非均匀问题：先将6本书分成3组：一组一本，一组二本，另一组三本，不同的分组方法为C1C2C3，分成三组后再分配给三个人，不同的分配方法为6 5 3A3。故将三本书分给甲、乙、丙三人，一人一本，一人两本，另一人三本的不同分配方法 3种数为C1C2C3A3 =360 （种）6533是指定人应得数量的均匀问题：将6本书平均分成三组，每组2本的不同分法数为C2C2C26 / 2 = 15 （种）分成三组后再分配给甲、乙、丙三个人，共有A 3种不同的分法，故A336 本书平均分给 3 个人，每人 2 本的不同分法种数为种）。C2C2C26 4 i A3 二 90 A333是分堆的非均匀问题（与等价）：方法数为C3C&；是分堆的均匀问题：方法数为C2C2C2十A3 ；6 4 23是部分均匀地分给人的问题：方法数为七-A3 ； A 232C4C1C1是部分均匀地分堆的问题：方法数为亠严亠。A22点评：以上问题归纳为分给人（有序）分成堆（无序）非均匀C 3 C 2 C1 x P 3C 3 C 2 C16313631均匀C 2 C 2 C 2C 2 C 2 C 2 十 P 36426423C 4 C iC iC 4 C1C1部分均匀6_2_1 - A36_2_1A 23A 222九、探寻规律“枚举法”题中附加条件增多，直接解决困难时，用实验逐步寻求规律有时也是行之有效的方法 把符合条件的安排不重复、不遗漏的一一列举出来，是最简单、最原始但也是最基本的计数 方法教材中多次应用到，高考中也常用枚举法解决问题例25. 某电脑用户计划使用不超过500 元的资金购买单价分别60 元、70元的单片软件和 盒装磁盘，根据需要，软件至少买 3 片，磁盘至少买2 盒，则不同的选购方法有（）A. 5种B. 6种C. 7种D. 8种解析：根据所给选项数字较小，不难用枚举法解决单片买 3 张，磁盘买2 盒，花钱320 元；单片买3 张，磁盘买3 盒，花钱390元；单片 买3 张，磁盘买4盒，花钱460元；单片买4张，磁盘买2 盒，花钱380元；单片买4张， 磁盘买3盒，花钱450元；单片买5 张，磁盘买2盒，花钱440元；单片买6 张，磁盘买2 盒，花钱500元.故选购方式有7种，选A.例26. 将数字1， 2， 3， 4填入标号为 1， 2， 3， 4的四个方格内，每个方格填1个，则每个方格的标号与所填的数字均不相同的填法种数有（）A.6B.9C.11D.23分析：此题考查排列的定义，由于附加条件较多，解法较为困难，可用实验法逐步解决。 第一方格内可填2或 3或4。如填2，则第二方格中内可填1或3或4。若第二方格内填1，则第三方格只能填4，第四方格应填 3。 若第二方格内填3，则第三方格只能填4，第四方格应填 1。同理，若第二方格内填 4，则第三方格只能填 1，第四方格应填 3。因而，第一格填 2 有3 种方法。不难得到，当第一格填3或 4时也各有3种，所以共有9种。例27.从 1到 100的一百个自然数中，每次取出两个数，使其和大于100，这样的取法共有多少种？解： 从 1 到 100 的一百个自然数中，每次取出两个数，其中必有一个是较小的我们先按 较小的一数枚举，而当较小的数取定以后，使和超过100 的另一个相应较大的数不难一一例 举，所有情况如下表：较小数相应可取的较大数取法种数11001299, 1002398, 99, 1003 4952,，100495051, 52,，100505152,，10049 991001所以共有：1+2+3+-+49+50+49+1=2500种不同的取法.以上我们讨论了学习了解决排列组合应用题的一些解题技巧,具体有插入法,捆绑法,排除法, 枚举法等等；对于不同的题目,根据它们的条件,我们就可以选取不同的技巧来解决问题.对 于一些比较复杂的问题,我们可以将几种技巧结合起来应用,便于我们迅速准确地解题.在这 些技巧中所涉及到的数学思想方法,例如:分类讨论思想,变换思想,特殊化思想等等,要在应 用中注意掌握.