排列组合(加乘、排列、组合、捆绑、插空、隔板)_第1页
排列组合(加乘、排列、组合、捆绑、插空、隔板)_第2页
排列组合(加乘、排列、组合、捆绑、插空、隔板)_第3页
排列组合(加乘、排列、组合、捆绑、插空、隔板)_第4页
排列组合(加乘、排列、组合、捆绑、插空、隔板)_第5页
已阅读5页,还剩2页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、计数专题学习目标1.正确理解“标数”法计算路径数目;2.正确理解“加法原理”、“乘法原理”的意义和运用场景;2.正确理解“排列”、“组合”的意义、区别和计算公式;3.正确掌握“优选法”“捆绑法”、“插空法”、“隔板法”这些排列组合解题技巧,理解各种排列组合解题技巧的原理,所解决的问题类型及其解题方法;一.标数法例题:在左下图中,从A点沿实线走最短路径到B点,共有多少条不同路线?                   分

2、析与解:题目要求从左下向右上走,所以走到任一点,例如右上图中的D点,不是经过左边的E点,就是经过下边的F点。如果到E点有a种走法(此处a6),到F点有b种走法(此处b4),根据加法原理,到D点就有(ab)种走法(此处为64=10)。我们可以从左下角A点开始,按加法原理,依次向上、向右填上到各点的走法数(见右上图),最后得到共有35条不同路线。二. 加乘原理加法原理: 分情况、分类计数;乘法原理:分步骤完成,各步骤单独计数,再连乘;加乘混合:加法、乘法混合使用; (1)一个步骤内有多种情况时,在计算本步骤时用加法,再总体用乘法计算出所有情况; (2)总体分几种情况,分别计算各种情况时分步骤用乘法

3、,再将各种情况汇总用加法 加法原理与乘法原理的区别:乘法原理和加法原理是两个重要而常用的计数法则,在应用时一定要注意它们的区别。乘法原理是把一件事分几步完成,这几步缺一不可,所以完成任务的不同方法数等于各步方法数的乘积;加法原理是把完成一件事的方法分成几类,每一类中的任何一种方法都能完成任务(一步完成任务),所以完成任务的不同方法数等于各类方法数之和。ABC例题:由A村去B村有2条路可走,由B村去C村有4条路可走,问从A村经B村去C村,共有多少种不同的走法? 三.排列组合排列:有顺序要求(交换顺序,就产生新的计数)à乘法原理;A52=5×4 从个不同的元素中取出()个元素,

4、按照一定的顺序排成一列,叫做从个不同元素中取出个元素的一个排列(1)两个排列相同,指的是两个排列的元素完全相同,并且元素的排列顺序也相同(2)如果两个排列中,元素不完全相同,它们是不同的排列;(3)如果两个排列中,虽然元素完全相同,但元素的排列顺序不同,它们也是不同的排列计算:乘法原理:从个不同元素中取出个元素的排列数是,即,这里,且等号右边从开始,共有个因数相乘。组合:无顺序要求(交换顺序,不产生新的计数)à除法原理;C52=(5×4)÷(2×1) 从个不同元素中取出个()元素组成一组不计较组内各元素的次序,叫做从个不同元素中取出个元素的一个组合 (1

5、)从排列和组合的定义可以知道,排列与元素的顺序有关,而组合与顺序无关(2)如果两个组合中,元素不完全相同,它们是不同的组合;(3)如果两个组合中的元素完全相同,那么不管元素的顺序如何,都是相同的组合计算:除法原理:从个不同元素中取出个元素()的所有组合的个数,叫做从个不同元素中取出个不同元素的组合数记作。一般地,求从个不同元素中取出的个元素的排列数可分成以下两步:第一步:从个不同元素中取出个元素组成一组,共有种方法; 第二步:将每一个组合中的个元素进行全排列,共有种排法根据乘法原理,得到因此,组合数(运用除法,将元素完全相同,元素顺序不同的多种排列合并成一种组合)【例 1】 小新、阿呆等七个同

6、学照像,分别求出在下列条件下有多少种站法?(1)七个人排成一排; (2)七个人排成一排,小新必须站在中间.(3)七个人排成一排,小新、阿呆必须有一人站在中间.(4)七个人排成一排,小新、阿呆必须都站在两边.(5)七个人排成一排,小新、阿呆都没有站在边上.(6)七个人战成两排,前排三人,后排四人.(7)七个人战成两排,前排三人,后排四人. 小新、阿呆不在同一排。(1)(种)。(2)只需排其余6个人站剩下的6个位置(种).(3)先确定中间的位置站谁,冉排剩下的6个位置2×=1440(种)(4)先排两边,再排剩下的5个位置,其中两边的小新和阿呆还可以互换位置 (种)(5)先排两边,从除小新

7、、阿呆之外的5个人中选2人,再排剩下的5个人,(种).(6)七个人排成一排时,7个位置就是各不相同的现在排成两排,不管前后排各有几个人,7个位置还是各不相同的,所以本题实质就是7个元素的全排列(种).(7)可以分为两类情况:“小新在前,阿呆在后”和“小新在前,阿呆在后”,两种情况是对等的,所以只要求出其中一种的排法数,再乘以2即可4×3××2=2880(种)排队问题,一般先考虑特殊情况再去全排列。【巩固】 现有男同学3人,女同学4人(女同学中有一人叫王红),从中选出男女同学各2人,分别参加数学、英语、音乐、美术四个兴趣小组:(1)共有多少种选法?(2)其中参加美术

8、小组的是女同学的选法有多少种?(3)参加数学小组的不是女同学王红的选法有多少种?(4)参加数学小组的不是女同学王红,且参加美术小组的是女同学的选法有多少种?(1)从3个男同学中选出2人,有=3种选法。从4个女同学中选出2人,有=6种选法。在四个人确定的情况下,参加四个不同的小组有4×3×2×1=24种选法。3×6×24=432,共有432种选法。(2)在四个人确定的情况下,参加美术小组的是女同学时有2×3×2×1=12种选法。3×6×12=216,所以其中参加美术小组的是女同学的选法有216种。

9、(3)考虑参加数学小组的是王红时的选法,此时的问题相当于从3个男同学中选出2人,从3个女同学中选出1人,3个人参加3个小组时的选法。3×3×3×2×1=54,所以参加数学小组的是王红时的选法有54种,432-54=378,所以参加数学小组的不是女同学王红的选法有378种。(4)考虑参加数学小组的是王红且参加美术小组的是女同学时的选法,此时的问题相当于从3个男同学中选出2人参加两个不同的小组,从3个女同学中选出1人参加美术小组时的选法。3×2×3=18,所以参加数学小组的是王红且参加美术小组的是女同学时的选法有18种,216-18=19

10、8,所以参加数学小组的不是女同学王红,且参加美术小组的是女同学的选法有198种。四.优选法优选法:对于问题中的特殊元素、特殊位置要优先安排确定。在操作时,针对实际问题,有时“元素优先”,有时“位置优先”。注意:看特殊,分步、分类,限制完,自由排,注意“0”。难点:不管是位置优先还是元素优先,都要看清是分类还是分步来解决问题;注意“0”,题目中往往对于“0”有暗含的限制条件。例题.由数字1、2、3、4、5组成没有重复数字的五位数,其中小于50000的偶数共有多少个?解析一:利用位置优先方法。偶数则要求个位为偶数,小于50000则首位要小于5。:第一步,首先看个位,从2个偶数中选择有C12种选法;

11、第二步,看首位,从个数上已选数字和5之外的数字选,则有 C13种选法;第三步,对于剩下的三个位置没有限制,则可以随意选择剩下的三个数字排上去,则有A33 种选法。根据乘法计数原则,共有:C12×C13 ×A33=36。解析二:利用元素优先方法。第一步,从数字2、4中选一个放在个位上,有C12种选法;第二步,从个数上已选数字和5之外的数字选一个放在首位上,则有 C13种选法;第三步,对于剩下的三个数字没有限制,则可以随意安排到剩下的三个数位上去,则有A33 种选法。根据乘法计数原则,共有:C12×C13 ×A44=36。五.”捆绑法” 捆绑法:用于解决&q

12、uot;相邻问题",即在解决对于某几个元素要求相邻的问题时,先将其"捆绑"后整体考虑,也就是将相邻元素视作"一个"大元素进行排序,然后再考虑大元素内部各元素间排列顺序的解题策略。 注意:运用捆绑法解决排列组合问题时,一定要注意"捆绑"起来的大元素内部的顺序问题。解题过程是"先捆绑,再排列"。例题:若有A、B、C、D、E五个人排队,要求A和B两个人必须站在相邻位置,则有多少排队方法? 【解析】:题目要求A和B两个人必须排在一起,首先将A和B两个人"捆绑",视其为"一个人&quo

13、t;,也即 对"A,B"、C、D、E"四个人"进行排列,有 种排法。又因为捆绑在一起的A、B两人也要排序,有 种排法。根据分步乘法原理,总的排法有 种。 六.“插空法” 插空法:用于解决"不邻问题",即在解决对于某几个元素要求不相邻的问题时,先将其它元素排好,再将指定的不相邻的元素插入已排好元素的间隙或两端位置,从而将问题解决的策略。注意:运用插空法解决排列组合问题时,一定要注意插空位置包括先排好元素"中间空位"和"两端空位"。解题过程是"先排列,再插空"。例题:若有A、B、

14、C、D、E五个人排队,要求A和B两个人必须不站在一起,则有多少排队方法?【解析】:题目要求A和B两个人必须隔开。首先将C、D、E三个人排列,有 种排法;若排成D C E,则D、C、E"中间"和"两端"共有四个空位置,也即是: D C E ,此时可将A、B两人插到四个空位置中的任意两个位置,有 种插法。由乘法原理,共有排队方法: 。 七.“隔板法”(插板法) 隔板法:有n个相同的元素,要求分到m组中,并且要求每组中至少有一个元素问有多少种分法?基本思路:将n个相同的元素排成一行,n个元素之间出现了(n-1)个空档,现在我们用(m-1)个“档板”插入(n-1

15、)个空档中,就把n个元素隔成有序的m份,每个组依次按组序号分到对应位置的几个元素(可能是1个、2个、3个、4个、.),这样不同的插入办法就对应着n个相同的元素分到m组的一种分法,这种借助于这样的虚拟“档板”分配元素的方法称之为插板法。【基本题型】【例1】 共有10完全相同的球分到7个班里,要求每个班至少要分到一个球,问有几种不同分法?解析一:我们首先用常规方法。若想将10个球分到7个班里,球的分法共三类:第一类:有3个班每个班分到2个球,其余4个班每班分到1个球。这样,第一步,我们从7个班中选出3个班,每个班分2个球;第二步,从剩下的4个班中选4个班,每班分1球。其分法种数为 :C(7,3)*

16、C(4,4)=35注明:由于排版的关系,我用C(n,m)和A(n,m)代替原来的组合与排列公式。第二类:有1个班分到3个球,1个班分到2个球,其余5个班每班分到1个球。其分法种数 :C(7,1)* C(6,1)* C(5,5)=42第三类:有1个班分到4个球,其余的6个班每班分到1个球。其分法种数 :C(7,1)* C(6,6)=7所以,10个球分给7个班,每班至少一个球的分法种数为: 35+42+7=87(种)。解析二:从上面的解题过程可以看出,用常规方法解这类题,需要分类计算,计算过程繁琐。并且如果元素个数较多的话处理起来就变得十分的困难了。因此我们需要寻求一种新的方法解决问题,也就是插板

17、法。我们可以将10个相同的球排成一行,10个球之间出现了9个空隙,现在我们用6个档板”插入这9个空隙中,就“把10个球隔成有序的7份,每个班级依次按班级序号分到对应位置的几个球(可能是1个、2个、3个、4个),这样,借助于虚拟“档板”就可以把10个球分到了7个班中。由上述分析可知,原问题就可以转化成:在9个空档之中插入6个“档板”(6个档板可把球分为7组)的问题,这是一个很简单的组合问题,其方法种数为 :C(9,6)=84【总结】:对于这种要求每组元素至少要分到一个的情况,则只需在n个元素的n-1个间隙中放置m-1块隔板把它隔成m份即可,共有C(n-1,m-1)种不同方法。【注意】: 

18、; 这种插板法解决相同元素分到不同组的问题非常简单,但同时也提醒各位考友,这类问题模型适用前提相当严格,必须同时满足以下3个条件:(1)所有要分的元素须完全相同; (2)所要分的元素必须分完,决不允许有剩余; (3)参与分元素的每组至少分到1个,决不允许出现分不到元素的组。     这样对于很多的问题,是不能直接利用插板法解题的。但,可以通过一定的转变,将其变成符合上面3个条件的问题,这样就可以利用插板法解决,并且常常会产生意想不到的效果。【基本题型的变形(一)】题型:有n个相同的元素,要求分到m组中,问有多少种不同的分法?解题思路:

19、这种问题是允许有些组中分到的元素为“0”,也就是组中可以为空的。对于这样的题,我们就首先将每组都填上1个,这样所要元素总数就m个,问题也就是转变成将(n+m)个元素分到m组,并且每组至少分到一个的问题,也就可以用插板法来解决。  【例2】有8个相同的球放到三个不同的盒子里,共有( )种不同方法.解析:这道题很多同学错选C,错误的原因是直接套用 “插板法”,而忽略了题中并没有说每个盒子至少要分到一个球,也就是可以出现空盒子。原题并不符合“插板法”的条件不过,此题只要我们多一个小变化,就可以将其转化为用“插板法”解题的类型了。我们可以人为地在每个盒子增加一个球,原有8个相同的球放到三个不同的盒子里这样这个

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论