高考数学中解排列组合问题的17种策略2.ppt

《高考数学中解排列组合问题的17种策略2.ppt》由会员分享，可在线阅读，更多相关《高考数学中解排列组合问题的17种策略2.ppt（52页珍藏版）》请在三一文库上搜索。

1、,解排列组合问题的常用策略,王振涛,1、基本概念和考点,2、合理分类和准确分步,3、特殊元素和特殊位置问题,4、相邻相间问题,5、定序问题,6、分房问题,7、环排、多排问题,12、小集团问题,10、先选后排问题,9、平均分组问题,11、构造模型策略,8、实验法（枚举法）,13、其它特殊方法,排列组合应用题解法综述（目录）,基 本 原 理,组合,排列,排列数公式,组合数公式,组合数性质,应 用 问 题,知识结构网络图：,返回目录,两个原理的区别与联系：,做一件事或完成一项工作的方法数,直接（分类）完成,间接（分步骤）完成,做一件事，完成它可以有n类办法， 第一类办法中有m1种不同的方法， 第二类

2、办法中有m2种不同的方法， 第n类办法中有mn种不同的方法， 那么完成这件事共有 N=m1+m2+m3+mn 种不同的方法,做一件事，完成它可以有n个步骤， 做第一步中有m1种不同的方法， 做第二步中有m2种不同的方法， 做第n步中有mn种不同的方法， 那么完成这件事共有 N=m1m2m3mn 种不同的方法.,回目录,1.排列和组合的区别和联系：,从n个不同元素中取出m个元 素，按一定的顺序排成一列,从n个不同元素中取出m个元 素，把它并成一组,所有排列的的个数,所有组合的个数,回目录,判断下列问题是组合问题还是排列问题?,(1)设集合A=a,b,c,d,e，则集合A的含有 3个元素的子集有多

3、少个?,(2)某铁路线上有5个车站，则这条铁路线上 共需准备多少种车票?,有多少种不同的火车票价？,组合问题,排列问题,(3)10名同学分成人数相同的数学和 英语两个学习小组，共有多少种分法?,组合问题,(4)10人聚会，见面后每两人之间要 握手相互问候，共需握手多少次?,组合问题,(5)从4个风景点中选出2个安排游览,有多少种不同的方法?,组合问题,(6)从4个风景点中选出2个,并确定这2个风景点的游览顺序,有多少种不同的方法?,排列问题,组合问题,回目录,合理分类和准确分步,解排列（或）组合问题，应按元素的性质进行分类，分类标准明确，不重不漏；按事情的发生的连续过程分步，做到分步层次清楚.

4、,回目录,合理分类与分步策略,例.在一次演唱会上共10名演员,其中8人能唱歌,5人会跳舞,现要演出一个2人唱歌2人伴舞的节目,有多少选派方法?,解：,10演员中有5人只会唱歌，2人只会跳舞 3人为全能演员。,回目录,元素相同问题隔板策略,应用背景：相同元素的名额分配问题 不定方程的正整数解问题,隔板法的使用特征： 相同的元素分成若干部分，每部分至少一个,元素相同问题隔板策略,例.有10个运动员名额，在分给7个班，每 班至少一个,有多少种分配方案？,解：因为10个名额没有差别，把它们排成 一排。相邻名额之间形成个空隙。,在个空档中选个位置插个隔板， 可把名额分成份，对应地分给个 班级，每一种插板

5、方法对应一种分法 共有_种分法。,将n个相同的元素分成m份（n，m为正整数）,每份至少一个元素,可以用m-1块隔板，插入n个元素排成一排的n-1个空隙中，所有分法数为,回目录,例 高二年级8个班,组织一个12个人的年级学生分会,每班要求至少1人,名额分配方案有多少种?,解 此题可以转化为:将12个相同的白球分成8份,有多少种不同的分法问题,因此须把这12个白球排成一排,在11个空档中放上7个相同的隔板,每个空档最多放一个,即可将白球分成8份,显然有 种不同的放法,所以名额分配方案有 种.,结论 转化法:对于某些较复杂的、或较抽象的排列组合问题，可以利用转化思想,将其化归为简单的、具体的问题来求

6、解.,分析 此题若直接去考虑的话,就会比较复杂.但如果我们将其转换为等价的其他问题,就会显得比较清楚,方法简单,结果容易理解.,回目录,练 习,（1）将10个学生干部的培训指标分配给7个不同的班级，每班至少分到一个名额，不同的分配方案共有 （ ）种。,（2）不定方程 的正整数解共有（ ）组,回目录,练习题,10个相同的球装5个盒中,每盒至少一 有多少装法？,2 .x+y+z+w=100求这个方程组的自然数解 的组数,回目录,小结：把n个相同元素分成m份每份,至少1个元素,问有多少种不同分法的问题可以采用“隔板法”得出共有 种.,回目录,平均分组问题除法策略,“分书问题”,平均分组问题除法策略,

7、例12. 6本不同的书平均分成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)一种分法,故共 有 种分法。,平均分成的组,不管它们的顺序如何,都是一种情况,所以分组后要一定要除以 (n为均分的组数)避免重复计数。,回目录,1 将13个球队分成3组,一组5个队,其它两组4 个队, 有多

8、少分法？,2.10名学生分成3组,其中一组4人, 另两组3人 但正副班长不能分在同一组,有多少种不同 的分组方法,（1540）,3.某校高二年级共有六个班级，现从外地转 入4名学生，要安排到该年级的两个班级且每班安排2名，则不同的安排方案种数为_,回目录,分清排列、组合、等分的算法区别,例 (1)今有10件不同奖品,从中选6件分给甲一件,乙二件和丙三件,有多少种分法? (2) 今有10件不同奖品, 从中选6件分给三人,其中1人一件1人二件1人三件, 有多少种分法? (3) 今有10件不同奖品, 从中选6件分成三份,每份2件, 有多少种分法?,解：（1）,（2）,(3),回目录,练习 (1)今有

9、10件不同奖品,从中选6件分成三份, 二份各1件,另一份4件, 有多少种分法? (2) 今有10件不同奖品,从中选6件分给甲乙丙三人,每人二件有多少种分法?,解: (1),(2),回目录,小结：排列与组合的区别在于元素是否有序; m等分的组合问题是非等分情况的;而元素相同时又要另行考虑.,回目录,构造模型策略,例. 马路上有编号为1,2,3,4,5,6,7,8,9的 九只路灯,现要关掉其中的3盏,但不能关 掉相邻的2盏或3盏,也不能关掉两端的2 盏,求满足条件的关灯方法有多少种？,解：把此问题当作一个排队模型在6盏 亮灯的5个空隙中插入3个不亮的灯 有_ 种,一些不易理解的排列组合题如果能转化

10、为 非常熟悉的模型，如占位填空模型，排队 模型，装盒模型等，可使问题直观解决,回目录,练习题,某排共有10个座位，若4人就坐，每人左右 两边都有空位，那么不同的坐法有多少种？,120,回目录,先选后排问题,八.排列组合混合问题先选后排策略,例.有5个不同的小球,装入4个不同的盒内, 每盒至少装一个球,共有多少不同的装 法.,解:第一步从5个球中选出2个组成复合元共 有_种方法.再把5个元素(包含一个复合 元素)装入4个不同的盒内有_种方法.,根据分步计数原理装球的方法共有_,解决排列组合混合问题,先选后排是最基本 的指导思想.此法与相邻元素捆绑策略相似 吗?,回目录,练习题,一个班有6名战士,

11、其中正副班长各1人 现从中选4人完成四种不同的任务,每人 完成一种任务,且正副班长有且只有1人 参加,则不同的选法有_ 种,192,回目录,3 名医生和 6 名护士被分配到 3 所学校为学生体检,每校分配 1 名医生和 2 名护士,不同的分配方法共有多少种?,先选后排问题的处理方法,解法一：先组队后分校（先分堆后分配）,回目录,解法二：依次确定到第一、第二、第三所学校去的医生和护士.,回目录,为支援西部开发,有3名教师去银川市三所学校任教,每校分配1人,不同的分配方法共有_种(用数字作答).,练习,改为4名教师？,改为5名教师？,回目录,有甲、乙、丙三项任务,甲需2人承担,乙、丙各需1人承担.

12、从10人中选派4人承担这三项任务,不同的选法共有多少种?,回目录,四名同学分配到三个办公室去搞卫生,每个办公室至少去一名学生,不同的分配方法有多少种?,回目录,基础训练,回目录,练习 某学习小组有5个男生3个女生，从中选3名男生和1名女生参加三项竞赛活动，每项活动至少有1人参加，则有不同参赛方法_种.,解：采用先组后排方法:,回目录,小结：本题涉及一类重要问题：问题中既有元素的限制，又有排列的问题，一般是先元素（即组合）后排列。,回目录,实验法（穷举法），（枚举法） 应用举例,实验法（穷举法）,题中附加条件增多，直接解决困难时，用实验逐步寻求规律有时也是行之有效的方法。,例 将数字1，2，3，

13、4填入标号为1，2，3，4的四个方格内，每个方格填1个，则每个方格的标号与所填的数字均不相同的填法种数有（ ）,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种方法。,不难得到，当第一格填3或4时也各有3种，所以共有9种。,回目录,实际操作穷举策略,例.设有编号1,2,3

14、,4,5的五个球和编号1,2 3,4,5的五个盒子,现将5个球投入这五 个盒子内,要求每个盒子放一个球，并且 恰好有两个球的编号与盒子的编号相同,. 有多少投法？,解：从5个球中取出2个与盒子对号有_种 还剩下3球3盒序号不能对应，,回目录,实际操作穷举策略,例.设有编号1,2,3,4,5的五个球和编号1,2 3,4,5的五个盒子,现将5个球投入这五 个盒子内,要求每个盒子放一个球，并且 恰好有两个球的编号与盒子的编号相同,. 有多少投法？,解：从5个球中取出2个与盒子对号有_种 还剩下3球3盒序号不能对应，,同理3号球装5号盒时,4,5号球有也 只有1种装法,由分步计数原理有2 种,回目录,

15、练 习 ：（不对号入座问题）,（1）（2004湖北）将标号为1，2，3，10的 10个球放入标号为1，2，3，10的10个盒子中， 每个盒内放一个球，恰好有3个球的标号与其所在盒子 的标号不一致的放入方法有_种,（2）编号为1、2、3、4、5的五个球放入编号为1、2、3、4、5的五个盒子里，至多有2个对号入座的情形有_种,109,直接法：,间接法：,回目录,注意区别“恰好”与“至少”,从6双不同颜色的手套中任取4只，其中恰好有一双同色的手套的不同取法共有（ ） (A) 480种（B）240种 （C）180种 （D）120种,小结：“恰好有一个”是“只有一个”的意思。“至少有一个”则是“有一个或

16、一个以上”，可用分类讨论法求解，它也是“没有一个”的反面，故可用“排除法”。,解：,回目录,练习 从6双不同颜色的手套中任取4只，其中至少有一双同色手套的不同取法共有_种,解：,回目录,对于条件比较复杂的排列组合问题，不易用 公式进行运算，往往利用穷举法或画出树状 图会收到意想不到的结果,练习题,同一寝室4人,每人写一张贺年卡集中起来, 然后每人各拿一张别人的贺年卡，则四张 贺年卡不同的分配方式有多少种？,(9),2.给图中区域涂色,要求相邻区 域不同色,现有4种可选颜色,则 不同的着色方法有_种,72,回目录,其它特殊方法,分解与合成策略,例. 30030能被多少个不同的偶数整除,分析：先把

17、30030分解成质因数的乘积形式 30030=235 7 1113依题 意可知偶因数必先取2,再从其余5个 因数中任取若干个组成乘积，所有 的偶因数为：,例17.正方体的8个顶点可连成多少对异面 直线,回目录,解：我们先从8个顶点中任取4个顶点构成四 体共有体共_,3,358=174,分解与合成策略是排列组合问题的一种最 基本的解题策略,把一个复杂问题分解成几 个小问题逐一解决,然后依据问题分解后的 结构,用分类计数原理和分步计数原理将问 题合成,从而得到问题的答案 ,每个比较复 杂的问题都要用到这种解题策略,回目录,化归策略,例. 25人排成55方队,现从中选3人,要 求3人不在同一行也不在

18、同一列,不同的 选法有多少种？,解：,将这个问题退化成9人排成33方队,现从中选3人,要求3人不在同一行也不在同一列,有多少选法.这样每行必有1人从其中的一行中选取1人后,把这人所在的行列都划掉，,回目录,从55方队中选取3行3列有_选法 所以从55方队选不在同一行也不在同 一列的3人有_选法。,处理复杂的排列组合问题时可以把一个问题退化成一个简要的问题，通过解决这个简要的问题的解决找到解题方法，从而进下一步解决原来的问题,如此继续下去.从33方队中选3人的方法 有_种。再从55方队选出33 方队便可解决问题,回目录,对应法,例11、在100名选手之间进行单循环淘汰赛（即一场比赛失败要退出比赛

19、），最后产生一名冠军，问要举行几场？,分析：要产生一名冠军，需要淘汰掉冠军以外的所有选手，即要淘汰99名选手，淘汰一名选手需要进行一场比赛，所以淘汰99名选手就需要99场比赛。,回目录,某城市的街区由12个全等的矩形区组成 其中实线表示马路，从A走到B的最短路 径有多少种？,练习题,回目录,特征分析,研究有约束条件的排数问题，须要紧扣题目所提供的数字特征，结构特征，进行推理，分析求解。,例 由1，2，3，4，5，6六个数字可以组成多少个无重复且是6的倍数的五位数？,分析数字特征：6的倍数既是2的倍数又是3的倍数。其中3的倍数又满足“各个数位上的数字之和是3的倍数”的特征。把6分成4组，（3，3

20、），（6），（1，5），（2，4），每组的数字和都是3的倍数。因此可分成两类讨论；,第一类：由1，2，4，5，6作数码；首先从2，4，6中任选一个作个位数字有 ，然后其余四个数在其他数位上全排列有 ，所以,第二类：由1，2，3，4，5作数码。依上法有,回目录,（1）练习:（徐州二检）从6人中选4人组成4100m接力赛，其中甲跑第一棒，乙不跑最后一棒，有多少种选法？ 分析：（一）直接法 （二）间接法,（2）从正方体的8个顶点中选4个作四面体，则不同的四面体的个数为 。,练 习,58,（3）一个三位数，其十位上的数字既 小于百位上的数字也小于个位上的数字 ， 且个位百位上的数字不重复（如等） 那么

21、这样的三位数有 个,回目录,144,240,例 袋中有5分硬币23个,1角硬币10个,如果从袋中取出2元钱,有多少种取法?,解 把所有的硬币全部取出来,将得到 0.0523+0.1010=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有 种取法.,结论 剩余法:在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法.,分析 此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理出头绪来.但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题.,回目录,小结 本节课，我们对有关排列组合的几种常见的解题策略加以复习巩固。排列组合历来是学习中的难点，通过我们平时做的练习题，不难发现排列组合题的特点是条件隐晦，不易挖掘，题目多变，解法独特，数字庞大，难以验证。同学们只有对基本的解题策略熟练掌握。根据它们的条件,我们就可以选取不同的技巧来解决问题.对于一些比较复杂的问题,我们可以将几种策略结合起来应用把复杂的问题简单化，举一反三，触类旁通，进而为后续学习打下坚实的基础。,