高中数学排列组合问题的几种方法课件.ppt

2017-4-23 1 2017 年4月 23 日星期日从n个不同元素中,任取 m个元素,按照一定的顺序排成一列,叫做从 n个不同元素中取出 m 个元素的一个排列. : 从n个不同元素中,任取 m个元素,并成一组, 叫做从 n个不同元素中取出 :: : )!( ! )1()2 )(1(mn n mnnnnA mn????????排列与组合的区别与联系:与顺序有关的为排列问题,与顺序无关的为组合问题. )!(! ! ! )1()2 )(1(mnm n m mnnnnA AC mm mn mn????????? 2017-4-23 3 ④要明确组的顺序时,必须先分组后再把组数当作元素个数作全排列. ②若干个不同的元素局部“等分”有m个均等组, 要将选取出每一个组的组合数的乘积除以 m! ①若干个不同的元素“等分”为m个组,要将选取出每一个堆的组合数的乘积除以 m! ③非均分组问题,只要按比例取出分完再用乘法原理作积. 分组问题的六个模型: ①无序不等分; ②无序等分; ③无序局部等分; (④有序不等分; ⑤有序等分; ⑥有序局部等分.) 处理问题的原则: 1. 分组问题 2017-4-23 4 ,要分包给三个工程队,要求每个工程队至少要得到一项工程. 共有多少种不同的发包方式? 解: 要完成发包这件事,可以分为两个步骤: ⑴先将四项工程分为三“组”,有 2 1 1 4 2 1 226 C C C A ?种分法; ⑵再将分好的三“组”依次给三个工程队, 有3!=6种给法.∴共有 6×6=36种不同的发包方式. 1. 分组问题 2017-4-23 5 例2 . 7 、乙两人不相邻,有多少种不同的排法? ♀♀♀♀♀解: 分两步进行: ♀♀几个元素不能相邻时,先排一般元素,再让特殊元素插孔. 第1步,把除甲乙外的一般人排列: 55A有=120 种排法第2步,将甲乙分别插入到不同的间隙或两端中(插孔): 26A有=30 种插入法 120 30 3600 ? ?共有=种排法↑↑↑↑↑↑ 解决一些不相邻问题时,可以先排“一般”元素然后插入“特殊”元素,使问题得以解决. : 2017-4-23 6 相邻元素的排列,可以采用“局部到整体”的排法,即将相邻的元素局部排列当成“一个”元素,然后再进行整体排列. . 6 、乙两人必须相邻,有多少种不的排法?♀♀♀♀♀♀解: (1)分两步进行: 甲乙第一步,把甲乙排列(捆绑): 55A有= 120 种排法第二步,甲乙两个人的梱看作一个元素与其它的排队: 22A有=2种捆法 2 120 240 ? ?共有=种排法♀♀几个元素必须相邻时,先捆绑成一个元素,再与其它的进行排列. 2017-4-23 7 ,甲总站在乙的右侧的有多少种站法? 几个元素顺序一定的排列问题,一般是先排列,,先让其它元素选取位置排列,留下来的空位置自然就是顺序一定的了. (留空法)解法 1:将5个人依次站成一排,有解法 2:先让甲乙之外的三人从 5个位置选出 3个站好, 有 55A种站法, 然后再消去甲乙之间的顺序数 22A ∴甲总站在乙的右侧的有站法总数为 53 55 22 5 4 3 AA A ? ??? 35A种站法,留下的两个位置自然给甲乙有 1种站法∴甲总站在乙的右侧的有站法总数为 3 3 5 5 1 A A ? ? 2017-4-23 8 变式: 如下图所示,有5横8竖构成的方格图,从 A到B只能上行或右行共有多少条不同的路线? 解:如图所示→1 ↑①→2 ↑②↑③→3 →4 →5 ↑④→6 →7 将一条路经抽象为如下的一个排法(5-1)+(8-1)=11 格: 其中必有四个↑和七个→组成!所以, 四个↑和七个→一个排序就对应一条路经, 所以从 A到B共有 5 1 4 (5 1) (8 1) 11 C C ?? ???条不同的路径. (留空法)也可以看作是 1,2,3,4,5,6,7, ①,②,③,④顺序一定的排列, 有种排法. 11 11 4 7 4 7 A A A ? 2017-4-23 9 n 个相同小球放入 m(m ≤ n)个盒子里,要求每个盒子里至少有一个小球的放法等价于 n个相同小球串成一串从间隙里选 m-1 个结点剪截成 m段. ,把16个选手名额分配到高三年级的 4 个教学班,每班至少一个名额, 则不同的分配方案共有___ 种.