排列组合复习课-解排列组合问题的常用技巧

1、知识复习知识复习+梳理梳理 12nN=m +m +m复习巩固复习巩固12nN=m mm复习回顾排列数排列数从从n n个不同元素中取出个不同元素中取出m(mn)m(mn)个元素个元素, ,按照一定按照一定的顺序排成一列的顺序排成一列, ,叫做从叫做从n n个不同元素中取出个不同元素中取出m m个个元素的元素的一个排列一个排列.从n nm m个元素的个元素的排列数排列数。n n个不同元素中取出个不同元素中取出叫做从所有排列的个数，所有排列的个数，个元素的个元素的个不同元素中取出个不同元素中取出m(mn)排列排列排列数公式排列数公式) 1() 2)(1(mnnnnAmn!mn )!n (我们规定我们

2、规定:0!=1:0!=1复习回顾组合数组合数从从n n个不同元素中取出个不同元素中取出m(mn)m(mn)个元素个元素, ,并成一组并成一组, ,叫做从叫做从n n个不同元素中取出个不同元素中取出m m个元素的个元素的一个组合一个组合.从n nm m个元素的个元素的组合数组合数。n n个不同元素中取出个不同元素中取出叫做从所有组合的个数，所有组合的个数，个元素的个元素的个不同元素中取出个不同元素中取出m(mn)组合组合组合数公式和两个重要性组合数公式和两个重要性质质!()!mmn mnnnmmAnCCAmnm 11mmmnnnCCC 解决实际问题时首先要看是否与顺解决实际问题时首先要看是否与顺

3、序有关，从而确定是排列问题还是组序有关，从而确定是排列问题还是组合问题，必要时要利用分类和分步计合问题，必要时要利用分类和分步计数原理数原理强调：排列强调：排列有顺序；有顺序； 组合组合无顺序无顺序 在处理问题时，一般可采用在处理问题时，一般可采用直接直接和和间接间接 两种思维形式，从而寻求有效的解题途径两种思维形式，从而寻求有效的解题途径:例例1.由由0,1,2,3,4,5可以组成多少个没有重复数字可以组成多少个没有重复数字 五位奇数五位奇数. 解解:由于末位和首位有特殊要求由于末位和首位有特殊要求,应该优先安应该优先安 排排,以免不合要求的元素占了这两个位置以免不合要求的元素占了这两个位置

4、先排末位共有先排末位共有_ 然后排首位共有然后排首位共有_最后排其它位置共有最后排其它位置共有_13C13C14C14C34A34A由分步计数原理得由分步计数原理得=28813C14C34A例例2. 72. 7人站成一排人站成一排 , ,其中甲乙相邻且丙丁相其中甲乙相邻且丙丁相 邻邻, , 共有多少种不同的排法共有多少种不同的排法. .甲甲乙乙丙丙丁丁由分步计数原理可得共有由分步计数原理可得共有种不同的排法种不同的排法55A22A22A=480解：可先将甲乙两元素捆绑成整体并看成解：可先将甲乙两元素捆绑成整体并看成 一个复合元素，同时丙丁也看成一个一个复合元素，同时丙丁也看成一个 复合元素，再

5、与其它元素进行排列，复合元素，再与其它元素进行排列， 同时对相邻元素内部进行自排。同时对相邻元素内部进行自排。 . .55A第二步将第二步将4 4舞蹈插入第一步排舞蹈插入第一步排好的好的5 5个元素中间包含首尾两个空位共有个元素中间包含首尾两个空位共有种种 不同的方法不同的方法 46A由分步计数原理由分步计数原理,节目的节目的不同顺序共有不同顺序共有 种种55A46A相相相相独独独独独独四四. .重排问题求幂策略重排问题求幂策略例例4.4.把把6 6名实习生分配到名实习生分配到7 7个车间实习个车间实习, ,共有共有 多少种不同的分法多少种不同的分法解解: :完成此事共分六步完成此事共分六步:

6、 :把第一名实习生分配把第一名实习生分配 到车间有到车间有 种分法种分法. .7 7把第二名实习生分把第二名实习生分配配 到车间也有到车间也有7 7种分法，种分法， 依此类推依此类推, ,由分步由分步计计数原理共有数原理共有 种不同的排法种不同的排法67允许重复的排列问题的特点是以元素为研究允许重复的排列问题的特点是以元素为研究对象，元素不受位置的约束，可以逐一安排对象，元素不受位置的约束，可以逐一安排各个元素的位置，一般地各个元素的位置，一般地n不同的元素没有限不同的元素没有限制地安排在制地安排在m个位置上的排列数为个位置上的排列数为 种种n nm m（住店法）（住店法）解决解决“允许重复排

7、列问题允许重复排列问题”要注意区分两类元素：要注意区分两类元素： 一类元素可以重复，另一类不能重复，把不能重复的一类元素可以重复，另一类不能重复，把不能重复的元素看作元素看作“客人客人”，能重复的元素看作，能重复的元素看作“店店”，再利用乘，再利用乘法原理直接求解。法原理直接求解。练习练习 七名学生争夺五项冠军，每项冠军只能由一人七名学生争夺五项冠军，每项冠军只能由一人获得，获得冠军的可能的种数有（获得，获得冠军的可能的种数有（ ）A. B. C D.分析：因同一学生可以同时夺得分析：因同一学生可以同时夺得n项冠军，故学生可重复排列，项冠军，故学生可重复排列，将七名学生看作将七名学生看作7家家

8、“店店”，五项冠军看作，五项冠军看作5名名“客人客人”，每，每个个“客人客人”有有7种住宿法，由乘法原理得种住宿法，由乘法原理得 种。种。注：对此类问题，常有疑惑，为什么不是注：对此类问题，常有疑惑，为什么不是 呢？呢？57577557A57C75用分步计数原理看，用分步计数原理看，5是步骤数，自然是指数。是步骤数，自然是指数。住店法：住店法：例例5.5. 8 8人排成前后两排人排成前后两排, ,每排每排4 4人人, ,其中甲乙其中甲乙在前排在前排, ,丁在后排丁在后排, ,共有多少排法？共有多少排法？解解:8人排前后两排人排前后两排,相当于相当于8人坐人坐8把椅子把椅子,可以可以 把椅子排成

9、一排把椅子排成一排. 先在前先在前4个位置排甲乙两个位置排甲乙两个特殊元素有个特殊元素有_种种,再排后再排后4个位置上的个位置上的特殊元素有特殊元素有_种种,其余的其余的5人在人在5个位置个位置上任意排列有上任意排列有_种种,则共有则共有_种种.前排后排后排24A14A55A24A55A14A一般地一般地,元素分成多排的排列问题元素分成多排的排列问题,可归结为一排考虑可归结为一排考虑,再分段研究再分段研究.例例6.6.有有5 5个不同的小球个不同的小球, ,装入装入4 4个不同的盒内个不同的盒内, , 每盒至少装一个球每盒至少装一个球, ,共有多少不同的装共有多少不同的装 法法. .解解: :

10、第一步从第一步从5 5个球中选出个球中选出2 2个组成复合元共个组成复合元共 有有_种方法种方法. .再把再把5 5个元素个元素( (包含一个复合包含一个复合 元素元素) )装入装入4 4个不同的盒内有个不同的盒内有_种方法种方法. .25C44A根据分步计数原理装球的方法共有根据分步计数原理装球的方法共有_25C44A练习题一个班有一个班有6 6名战士名战士, ,其中正副班长各其中正副班长各1 1人人现从中选现从中选4 4人完成四种不同的任务人完成四种不同的任务, ,每人每人完成一种任务完成一种任务, ,且正副班长有且只有且正副班长有且只有1 1人人参加参加, ,则不同的选法有则不同的选法有

11、_ _ 种种192192例例7.7.用用1,2,3,4,51,2,3,4,5组成没有重复数字的五位数组成没有重复数字的五位数 其中恰有两个偶数夹其中恰有两个偶数夹在在1,1,两个奇数之两个奇数之 间间, ,这样的五位数有多少个？这样的五位数有多少个？解：把解：把,当作一个小集团与排队当作一个小集团与排队共有共有_种排法，再排小集团内部共有种排法，再排小集团内部共有_种排法，由分步计数原理共有种排法，由分步计数原理共有_种排法种排法.22A2222A A2222A A22A31524小集团小集团小集团排列问题中，先整体后局小集团排列问题中，先整体后局部，再结合其它策略进行处理。部，再结合其它策略

12、进行处理。八八. .元素相同问题隔板策略元素相同问题隔板策略例例8.有有1010个运动员名额，在分给个运动员名额，在分给7 7个班，每班至少个班，每班至少一个一个, ,有多少种分配方案？有多少种分配方案？ 解：解：因为因为10个名额没有差别，把它们排成一排。个名额没有差别，把它们排成一排。相邻名额之间形成个空隙。相邻名额之间形成个空隙。在个空档中选个位置插个隔板，可把名额在个空档中选个位置插个隔板，可把名额分成份，对应地分给个班级，每一种插板分成份，对应地分给个班级，每一种插板方法对应一种分法共有方法对应一种分法共有_种分法。种分法。一班二班三班四班五班六班七班69C11mnC练习题.将将8个

13、学生干部的培训指标分配给个学生干部的培训指标分配给5个不同的个不同的班级，每班班级，每班至少至少分到分到1个名额，共有多少种不同个名额，共有多少种不同的分配方法？的分配方法？ .从从6个学校中选出个学校中选出30名学生参加数学竞赛名学生参加数学竞赛,每每校校至少至少有有1人人,这样有几种选法这样有几种选法?例例9.9.我们班里有我们班里有6262位同学位同学, ,从中任抽从中任抽5 5人人, ,正、正、副班长、团支部书记至少有一人在内的副班长、团支部书记至少有一人在内的抽法有多少种抽法有多少种? ?十十. .平均分组问题除法策略平均分组问题除法策略例10. 6本不同的书平均分成本不同的书平均分

14、成3堆堆,每堆每堆2本共有本共有 多少分法？多少分法？解解: 分三步取书得分三步取书得 种方法种方法,但这里出现但这里出现 重复计数的现象重复计数的现象,不妨记不妨记6本书为本书为ABCDEF 若第一步取若第一步取AB,第二步取第二步取CD,第三步取第三步取EF 该分法记为该分法记为(AB,CD,EF),则则 中还有中还有 (AB,EF,CD),(CD,AB,EF),(CD,EF,AB) (EF,CD,AB),(EF,AB,CD)共有共有 种取法种取法 ,而而 这些分法仅是这些分法仅是(AB,CD,EF)一种分法一种分法,故共故共 有有 种分法。种分法。222642CCC222642CCC33

15、A222642CCC33A平均分成的组平均分成的组,不管它们的顺序如何不管它们的顺序如何,都是一都是一种情况种情况,所以分组后要一定要除以所以分组后要一定要除以 (n为均为均分的组数分的组数)避免重复计数。避免重复计数。nnA练习练习. 将将13个球队分成个球队分成3组组,一组一组5个队个队,其它两其它两组组4个队个队, 有多少分法？有多少分法？544138422C C CA “多面手多面手”没有被选上的选法共有没有被选上的选法共有_种种, ,“多面手多面手”若被选上，则又可以分两类：若被选上，则又可以分两类： 他唱歌他唱歌的选法共有的选法共有_种，种， 他跳舞的选法共有他跳舞的选法共有 种种

16、, ,由分类计数原理共有由分类计数原理共有_ _ _种。种。十一. 合理分类与分步策略例例1 11.1.在一次演唱会上共在一次演唱会上共1010名演员名演员, ,其中其中7 7人能人能 能唱歌能唱歌, ,4 4人会跳舞人会跳舞, ,现要演出一个现要演出一个2 2人人 唱歌唱歌2 2人伴舞的节目人伴舞的节目, ,有多少选派方法有多少选派方法? ?解：10演员中有演员中有6人只会唱歌，人只会唱歌，3人只会跳舞人只会跳舞 1人为人为“多面手多面手”。以以“多面手多面手”是否被是否被选上为标准进行研究：选上为标准进行研究：2263CC2163CC1263C C + +2263CC1263C C2163

17、CC解含有约束条件的排列组合问题，可按元素的性质进行分类，按事件发生的连续过程分步，做到标准明确。分步层次清楚，不重不漏，分类标准一旦确定要贯穿于解题过程的始终。十二十二. .构造模型策略构造模型策略例例1 12.2. 马路上有编号为马路上有编号为1,2,3,4,5,6,7,8,91,2,3,4,5,6,7,8,9的九只的九只路灯路灯, ,现要关掉其中的现要关掉其中的3 3盏盏, ,但不能关掉相邻的但不能关掉相邻的2 2盏盏, ,也不能关掉两端的也不能关掉两端的2 2盏盏, ,求满足条件的关灯方法有多求满足条件的关灯方法有多少种？少种？解：把此问题当作一个排队模型在解：把此问题当作一个排队模型

18、在6 6盏盏 亮灯的亮灯的5 5个空隙中插入个空隙中插入3 3个不亮的灯个不亮的灯 有有_ _ 种种35C一些不易理解的排列组合题如果能转化为非常熟悉的模型，如插空法，排队模型，装盒模型等，可使问题直观解决练习题某排共有某排共有1010个座位，若个座位，若4 4人就坐，每人左右人就坐，每人左右两边都有空位，那么不同的坐法有多少种？两边都有空位，那么不同的坐法有多少种？练习题B BA A3735C十三十三. .实际操作穷举策略实际操作穷举策略例例1 13.3.设有编号设有编号1,2,3,4,51,2,3,4,5的五个球和编号的五个球和编号1,2,3,4,51,2,3,4,5的五的五个盒子个盒子,

19、 ,现将现将5 5个球投入这五盒子内个球投入这五盒子内, ,要求每个盒子放一个要求每个盒子放一个球，并且恰好有两个球的编号与盒子的编号相同球，并且恰好有两个球的编号与盒子的编号相同, ,有多少有多少投法投法? ? 利用实际操作法，如果剩利用实际操作法，如果剩下下3,4,53,4,5号球和号球和3,4,53,4,5号盒号盒, ,3 3号球装号球装4 4号盒时，则号盒时，则4,54,5号球有只有号球有只有1 1种装法种装法. .3 3号盒号盒4 4号盒号盒5 5号盒号盒3 34 45 5解：从解：从5 5个球中取出个球中取出2 2个与盒子对号有个与盒子对号有_种种, ,还剩还剩下下3 3球球3 3

20、盒序号不能对应，盒序号不能对应，25C 同理同理3 3号球装号球装5 5号盒时号盒时,4,5,4,5号球号球有也只有有也只有1 1种装法种装法, ,由分步计数原理有由分步计数原理有2 2 种种. .25C类似列举法类似列举法（实验法）（实验法） 题中附加条件增多，直接解决困难时，用实验逐题中附加条件增多，直接解决困难时，用实验逐步寻求规律有时也是行之有效的方法。步寻求规律有时也是行之有效的方法。 例例8 将数字将数字1，2，3，4填入标号为填入标号为1，2，3，4的四个的四个方格内，每个方格填方格内，每个方格填1个，则每个方格的标号与所填的个，则每个方格的标号与所填的数字均不相同的填法种数有（

21、数字均不相同的填法种数有（ ）A.6 B.9 C.11 D.23分析：分析：此题考查排列的定义，由于附加条件较多，解法较为困难，此题考查排列的定义，由于附加条件较多，解法较为困难，可用实验法逐步解决。可用实验法逐步解决。第一方格内可填第一方格内可填2或或3或或4。如填。如填2，则第二方格中内可填，则第二方格中内可填1或或3或或4。若第二方格内填若第二方格内填1，则第三方格只能填，则第三方格只能填4，第四方格应填，第四方格应填3。若第二方格内填若第二方格内填3，则第三方格只能填，则第三方格只能填4，第四方格应填，第四方格应填1。同理，若第二方格内填同理，若第二方格内填4，则第三方格只能填，则第三方格只能填1，第四方格应，第四方格应填填3。因而，第一格填。因而，第一格填2有有3种方法。种方法。（实验法）（实验法）1 1对有约束条件问题，注意如下类型最常见：对有约束条件问题，注意如下类型最常见： 特殊位置；必须相邻；不能相邻；特殊位置；必须相邻；不能相邻；2 2基本的解题方法：基本的解题方法： 优先法优先法； 捆绑法捆绑法； 插空法插空法；3. 3. 在处理问题时，一般可采用在处理问题时，一般可采用直接直接和和间接间接两种思维形式，从而寻求有效的解题途径两种思维形式，从而寻求有效的解题途径4.4.借助借助一题多解一题多解检验答案