计数原理与排列组合课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,-,*,计数原理与排列组合,-,基,本,原,理,组合,排列,排列数公式,组合数公式,应,用,问,题,1、知识结构,一。复习回顾,-,2。分类记数原理，分步记数原理,分类记数原理,分步记数原理,原理,完成一件事可以有n类办法，在第一类中有m,1,种不同的方法，在第二类中有m,2,种不同的方法，在第n类办法中有m,n,种不同的方法，那么完成这件事共N=m,1,+m,2,+m,n,有种不同的方法。,完成一件事需要分成n个步骤，第一步有m,1,种不同的方法，第二步有m,2,种不同的方法，第n步有m,n,种不同的方法，那么完成这件事共N=m,1,m,2,m,n,有种不同的方法,。,区别,分类记数原理针对的是“分类”问题，其中各种方法相互独立，用其中任何一种方法都可完成这件事。,分步记数原理针对的是“分步”问题，各步方法相互依存，只有各步都完成才能完成这件事。,-,排列,组合,定义,从n个,不同,元素中，任取m(m,n)个,不同,元素按照一定顺序排成一列，叫做从n个不同元素中取出m个不同元素的一个,排列,。,从n个,不同,的元素中，任取m（mn）个,不同,的元素并成一组，叫做从n个不同的元素中取出m个不同的元素的一个,组合,。,区别,与顺序有关,与顺序无关,判定,看取出的两个元素互换位置是否为同一种方法，若不是，则是排列问题；若是，则是组合。,公式,3。排列与组合,-,4。解排列组合问题基本思路,排列组合问题,有序,无序,排列,组合,分类或分步,分类或分步,直接法,直接法,间接法,不易解,不易解,-,题型2 可重复元素排列问题,【例2】五名学生报名参加四项体育比赛，每人限报一项，报名方法的种数为多 少？五名学生争夺四项比赛的冠军(冠军不并列)，获得冠军的可能性有多少种？,解答：报名的方法种数为4,4,4,4,44,5,(种),获得冠,军的可能情况有5,5,5,55,4,(种).,方法小节：,解决“允许重复排列问题”常用“住店法”，要注意区分两类元素：,一类元素可以重复，另一类不能重复，把不能重复的元素看作“客”，能重复的元素看作“店”，再利用乘法原理直接求解。,-,基础知识梳理,二、题型与方法,【例3】如图，用5种不同的颜色给图中,A,、,B,、,C,、,D,四个区域涂色，规定每个区域只涂一种颜色，相邻区域颜色不同，求有多少种不同的涂色方法？,题型3 涂色问题,解法一,（分步法）如题图分四个步骤来完成涂色这件事需分为四步，第一步涂,A,区有5种涂法；第二步涂,B,有4种方法；第三步涂,C,有3种方法；第四步涂,D,有3种方法(还可以使用涂,A,的颜色)，根据分步计数原理共有5433180种涂色方法,-,2011,高考导航,解法二（分类法）：完成涂色的方法分为两类，第一类：四个区域涂四种不同的颜色共有 120种涂法；,第二类：四个区域涂三种不同的颜色，由于,A,、,D,不相邻只能是,A,、,D,两区域颜色一样，将A、D看做一个区域，共 60种涂法,由分类计数原理知共有涂法12060180(种),方法总结：,对涂色问题，有两种解法，法1是逐区图示法，注意不相邻可同色.,法2根据用色多少分类法.,-,题型4 排列中的“相邻”、“不相邻问题”,【例,4】,a,1,，,a,2,，,，,a,8,共八个元素，分别计算满足下列条件的排列数,(1),八个元素排成一排，且,a,1,，,a,2,，,a,3,，,a,4,四个元素排在一起；,(2)八个元素排成一排，且,a,1,，,a,2,，,a,3,，,a,4,四个元素互不相邻；,(3)八个元素排成一排，且,a,1,，,a,2,，,a,3,，,a,4,四个元素互不相邻，并且,a,5,，,a,6,，,a,7,，,a,8,也互不相邻；,(4)排成前后两排每排四个元素,-,解答：(1)（,捆绑法,）,先将,a,1,，,a,2,，,a,3,，,a,4,四个元素看成一个元素与,a,5,，,a,6,，,a,7,，,a,8,排列一排，有 种排法，再排,a,1,，,a,2,，,a,3,，,a,4,有 不同排法，根据,分步计数原理知满足条件的排列数为 2 880.,(2)(,插空法,）先排,a,5,，,a,6,，,a,7,，,a,8,四个元素排成一排，有 种排法；再将元素,a,1,，,a,2,，,a,3,，,a,4,插入由,a,5,，,a,6,，,a,7,，,a,8,间隔及两端的五个位置中的四个，有 种排法，根据分步计数原理知：满足条件的排列数为 2 880.,(3)先排,a,5,，,a,6,，,a,7,，,a,8,，,；共有 种排法；然后排,a,1,，,a,2,，,a,3,，,a,4,排在,或,中的,共有2 种排法；根据分步计数原理共有,2,1 152种排法,(4)前排有 种排法，后排有 种排法，由分步计数原理知共有 8！种排法,-,方法总结,（1）若某些元素必须相邻,，,常用,捆绑法,，,即先把这几个相邻元素捆在一起看成一个元素，再与其他元素全排列，最后再考虑这几个相邻元素的顺序。,（2）,若某些元素不相邻，常用,插空法,，,即先将普通元素全排列，然后再从排就的每两个元素之间及两端选出若干个空挡插入这些特殊元素,。,(3)前后排问题，,直排法.,-,变式4,4个男同学，3个女同学站成一排,(1)3个女同学必须排在一起，有多少种不同的排法？,(2)任何两个女同学彼此不相邻，有多少种不同的排法？,(3)其中甲、乙两同学之间必须恰有3人，有多少种不同的排法？,(4)甲、乙两人相邻，但都不与丙相邻，有多少种不同的排法？,(5)女同学从左到右按高矮顺序排，有多少种不同的排法？(3个女生身高互不相等),-,解答：(1)3个女同学是特殊元素，我们先把她们排好，共有 种排法；由于3个女同学必须排在一起，我们可视排好的女同学为一整体，再与男同学排队，这时是5个元素的全排列，应有 种排法，由分步计数的原理,有 720种不同排法,(2)先将男生排好，共有 种排法，再在这4个男生的中间及两头的5个空档中插入3个女生有 种方案，故符合条件的排法共有 1 440种不同排法,(3)甲、乙2人先排好，有 种排法，再从余下5人中选3人排在甲、乙2人中间，有 种排法，这时把已排好的5人视为一整体，与最后剩下的2人再排，又有 种排法，这样总共有 720种不同排法,-,(4)先排甲、乙和丙3人以外的其他4人，有 种排法；由于甲、乙要相邻，故再把甲、乙排好，有 种排法；最后把甲、乙排好的这个整体与丙分别插入原先排好的4人的空档中有 种排法这样，总共有 960种不同排法,(5)从7个位置中选出4个位置把男生排好，则有 种排法然后再在余下的3个空位置中排女生，由于女生要按身体高矮排列，故仅有一种排法这样总共有 840种不同排法.,-,