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

《排列组合复习课-解排列组合问题的常用技巧ppt课件.ppt》由会员分享，可在线阅读，更多相关《排列组合复习课-解排列组合问题的常用技巧ppt课件.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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!=10!=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例例5.85.8人排成前后两排人排成前

7、后两排, ,每排每排4 4人人, ,其中甲乙在其中甲乙在 前排前排, ,丁在后排丁在后排, ,共有多少排法共有多少排法解解:8人排前后两排人排前后两排,相当于相当于8人坐人坐8把椅子把椅子,可以可以 把椅子排成一排把椅子排成一排. 先在前先在前4个位置排甲乙两个位置排甲乙两个特殊元素有个特殊元素有_种种,再排后再排后4个位置上的个位置上的特殊元素有特殊元素有_种种,其余的其余的5人在人在5个位置个位置上任意排列有上任意排列有_种种,则共有则共有_种种.前排后排后排24A14A55A24A55A14A一般地一般地,元素分成多排的排列问题元素分成多排的排列问题,可归结为一排考虑可归结为一排考虑,再

8、分段研究再分段研究.例例6.6.有有5 5个不同的小球个不同的小球, ,装入装入4 4个不同的盒内个不同的盒内, , 每盒至少装一个球每盒至少装一个球, ,共有多少不同的装共有多少不同的装 法法. .解解: :第一步从第一步从5 5个球中选出个球中选出2 2个组成复合元共个组成复合元共 有有_种方法种方法. .再把再把5 5个元素个元素( (包含一个复合包含一个复合 元素元素) )装入装入4 4个不同的盒内有个不同的盒内有_种方法种方法. .25C44A根据分步计数原理装球的方法共有根据分步计数原理装球的方法共有_25C44A练习题一个班有一个班有6 6名战士名战士, ,其中正副班长各其中正副

9、班长各1 1人人现从中选现从中选4 4人完成四种不同的任务人完成四种不同的任务, ,每人每人完成一种任务完成一种任务, ,且正副班长有且只有且正副班长有且只有1 1人人参加参加, ,则不同的选法有则不同的选法有_ _ 种种192192例例7.7.用用1,2,3,4,51,2,3,4,5组成没有重复数字的五位数组成没有重复数字的五位数 其中恰有两个偶数夹其中恰有两个偶数夹在在1,1,两个奇数之两个奇数之 间间, ,这样的五位数有多少个？这样的五位数有多少个？解：把解：把,当作一个小集团与排队当作一个小集团与排队共有共有_种排法，再排小集团内部共有种排法，再排小集团内部共有_种排法，由分步计数原理

10、共有种排法，由分步计数原理共有_种排法种排法.22A2222A A2222A A22A31524小集团小集团小集团排列问题中，先整体后局小集团排列问题中，先整体后局部，再结合其它策略进行处理。部，再结合其它策略进行处理。基基本本原原理理组合组合排列排列排列数公式排列数公式组合数公式组合数公式组合数性质组合数性质应应用用问问题题.计划展出计划展出10幅不同的画幅不同的画,其中其中1幅水彩画幅水彩画,幅油画幅油画,幅国画幅国画, 排成一行陈列排成一行陈列,要求同一要求同一品种的必须连在一起，并且水彩画不在两品种的必须连在一起，并且水彩画不在两端，那么共有陈列方式的种数为端，那么共有陈列方式的种数为

11、_2. 5男生和女生站成一排照像男生和女生站成一排照像,男生相邻男生相邻,女女生也相邻的排法有生也相邻的排法有_种种255255A A A254254A A A变式：变式：小集团问题小集团问题和捆绑法类和捆绑法类似吗？似吗？八八. .元素相同问题隔板策略元素相同问题隔板策略例例8.有有1010个运动员名额，在分给个运动员名额，在分给7 7个班，每个班，每班至少一个班至少一个, ,有多少种分配方案？有多少种分配方案？ 解：因为解：因为10个名额没有差别，把它们排成个名额没有差别，把它们排成一排。相邻名额之间形成个空隙。一排。相邻名额之间形成个空隙。在个空档中选个位置插个隔板，在个空档中选个位置插

12、个隔板，可把名额分成份，对应地分给个可把名额分成份，对应地分给个班级，每一种插板方法对应一种分法班级，每一种插板方法对应一种分法共有共有_种分法。种分法。一班二班三班四班五班六班七班69C11mnC练习题.将将8个学生干部的培训指标分配给个学生干部的培训指标分配给5个不同的个不同的班级，每班班级，每班至少至少分到分到1个名额，共有多少种不同个名额，共有多少种不同的分配方法？的分配方法？ .从从6个学校中选出个学校中选出30名学生参加数学竞名学生参加数学竞赛赛,每校每校至少至少有有1人人,这样有几种选法这样有几种选法?例例9.9.我们班里有我们班里有6262位同学位同学, ,从中任抽从中任抽5

13、5人人, ,正、正、副班长、团支部书记至少有一人在内的副班长、团支部书记至少有一人在内的抽法有多少种抽法有多少种? ?十十. .平均分组问题除法策略平均分组问题除法策略例10. 6本不同的书平均分成本不同的书平均分成3堆堆,每堆每堆2本共有本共有 多少分法？多少分法？解解: 分三步取书得分三步取书得 种方法种方法,但这里出现但这里出现 重复计数的现象重复计数的现象,不妨记不妨记6本书为本书为ABCDEF 若第一步取若第一步取AB,第二步取第二步取CD,第三步取第三步取EF 该分法记为该分法记为(AB,CD,EF),则则 中还有中还有 (AB,EF,CD),(CD,AB,EF),(CD,EF,A

14、B) (EF,CD,AB),(EF,AB,CD)共有共有 种取法种取法 ,而而 这些分法仅是这些分法仅是(AB,CD,EF)一种分法一种分法,故共故共 有有 种分法。种分法。222642CCC222642CCC33A222642CCC33A平均分成的组平均分成的组,不管它们的顺序如何不管它们的顺序如何,都是一都是一种情况种情况,所以分组后要一定要除以所以分组后要一定要除以 (n为均为均分的组数分的组数)避免重复计数。避免重复计数。nnA1 将将13个球队分成个球队分成3组组,一组一组5个队个队,其它两组其它两组4 个队个队, 有多少分法？有多少分法？544138422C C CA “全能型全能

15、型”没有被选上的选法共有没有被选上的选法共有_种种, ,“全能型全能型”若被选上，则又可以分两类：若被选上，则又可以分两类： 他唱歌他唱歌的选法共有的选法共有_种，种， 他跳舞的选法共有他跳舞的选法共有 种种, ,由分类计数原理共有由分类计数原理共有_ _ _种。种。十一. 合理分类与分步策略例例1 11.1.在一次演唱会上共在一次演唱会上共1010名演员名演员, ,其中其中7 7人能人能 能唱歌能唱歌, ,4 4人会跳舞人会跳舞, ,现要演出一个现要演出一个2 2人人 唱歌唱歌2 2人伴舞的节目人伴舞的节目, ,有多少选派方法有多少选派方法? ?解：10演员中有演员中有6人只会唱歌，人只会唱

16、歌，3人只会跳舞人只会跳舞 1人为人为“全能型全能型”。以以“全能型全能型”是否被是否被选上为标准进行研究：选上为标准进行研究：2263CC2163CC1263C C + +2263CC1263C C2163CC解含有约束条件的排列组合问题，可按元素的性质进行分类，按事件发生的连续过程分步，做到标准明确。分步层次清楚，不重不漏，分类标准一旦确定要贯穿于解题过程的始终。十二十二. .构造模型策略构造模型策略例例1 12. 2. 马路上有编号为马路上有编号为1,2,3,4,5,6,7,8,91,2,3,4,5,6,7,8,9的的 九只路灯九只路灯, ,现要关掉其中的现要关掉其中的3 3盏盏, ,但

17、不能关但不能关 掉相邻的掉相邻的2 2盏盏, ,也不能关掉两端的也不能关掉两端的2 2盏盏, ,求求 满足条件的关灯方法有多少种？满足条件的关灯方法有多少种？解：把此问题当作一个排队模型在解：把此问题当作一个排队模型在6 6盏盏 亮灯的亮灯的5 5个空隙中插入个空隙中插入3 3个不亮的灯个不亮的灯 有有_ _ 种种35C一些不易理解的排列组合题如果能转化为非常熟悉的模型，如插空法，排队模型，装盒模型等，可使问题直观解决练习题某排共有某排共有1010个座位，若个座位，若4 4人就坐，每人左右人就坐，每人左右两边都有空位，那么不同的坐法有多少种？两边都有空位，那么不同的坐法有多少种？十三十三. .

18、实际操作穷举策略实际操作穷举策略例例1 13.3.设有编号设有编号1,2,3,4,51,2,3,4,5的五个球和编号的五个球和编号1,2,3,4,51,2,3,4,5的五个盒子的五个盒子, ,现将现将5 5个球投入这五盒子内个球投入这五盒子内, ,要求每个盒要求每个盒子放一个球，并且恰好有两个球的编号与盒子的编号子放一个球，并且恰好有两个球的编号与盒子的编号相同相同, ,有多少投法有多少投法? ? 利用实际操作法，如果剩利用实际操作法，如果剩下下3,4,53,4,5号球和号球和3,4,53,4,5号盒号盒, ,3 3号球装号球装4 4号盒时，则号盒时，则4,54,5号球有只有号球有只有1 1种

19、装法种装法. .3 3号盒号盒4 4号盒号盒5 5号盒号盒3 34 45 5解：从解：从5 5个球中取出个球中取出2 2个与盒子对号有个与盒子对号有_种种, ,还剩还剩下下3 3球球3 3盒序号不能对应，盒序号不能对应，25C 同理同理3 3号球装号球装5 5号盒时号盒时,4,5,4,5号球号球有也只有有也只有1 1种装法种装法, ,由分步计数原理有由分步计数原理有2 2 种种. .25C类似列举法类似列举法1 1对有约束条件问题，注意如下类型最常见：对有约束条件问题，注意如下类型最常见： 特殊位置；特殊位置；必须相邻；必须相邻；不能相邻；不能相邻；2 2基本的解题方法：基本的解题方法： 优先

20、法优先法； 捆绑法捆绑法； 插空法插空法；3. 3. 在处理问题时，一般可采用在处理问题时，一般可采用直接直接和和间接间接两种思维形式，从而寻求有效的解题途径两种思维形式，从而寻求有效的解题途径4.4.借助借助一题多解一题多解检验答案的正确性检验答案的正确性 排列组合高考汇编排列组合高考汇编1(07全国全国)从班委会5名成员中选出3名，分别担任班级学习委员、文娱委员与体育委员，其中甲、乙二人不能担任文娱委员，则不同的选法共有 种（用数字作答）解：先从其余解：先从其余3人中选出人中选出1人担任人担任文娱委员，再从文娱委员，再从4人中选人中选2人担任人担任学习委员和体育委员，不同的选学习委员和体育

21、委员，不同的选法共有法共有 种。种。1134.3 4 336C A 32542AA间接法间接法2(07全国全国II) 从从5位同学中选派位同学中选派4位同位同学在星期五、星期六、星期日参加学在星期五、星期六、星期日参加公益活动，每人一天，要求星期五公益活动，每人一天，要求星期五有有2人参加，星期六、星期日各有人参加，星期六、星期日各有1人参加，则不同的选派方法共有人参加，则不同的选派方法共有（ ） A40种种 B60种种 C100种种 D120种种B3(07陕西卷陕西卷) 安排3名支教教师去6所学校任教，每校至多2人，则不同的分配方案共有 种.（用数字作答）2103（07四川卷）用数字四川卷）用数字0，1，2，3，4，5可以组成没有重复数字，可以组成没有重复数字，并且比并且比20000大的五位偶数共有（大的五位偶数共有（）（A）288个个 （B）240个个 （C）144个个 （D）126个个2404（07浙江卷）某书店有浙江卷）某书店有11种杂志，种杂志，2元元1本本 的的8种，种，1元元1本的本的3种种. 小张用小张用10元钱买杂志（每种至多买一本，元钱买杂志（每种至多买一本，10元钱刚好用完），则不同买法的种数元钱刚好用完），则不同买法的种数是是 （用数字作答）（用数字作答） 266