1分类计数原理与分步计数原理.ppt

1、,一轮复习讲义,分类计数原理与分步计数原理,忆 一 忆 知 识 要 点,忆 一 忆 知 识 要 点,1.从甲地到乙地，可以乘火车，可以乘汽车，也可以乘轮船，还可以坐飞机.一天中，火车有4班，汽车有2班，轮船有3班，飞机有1班，那么一天中乘坐这些交通工具，从甲地到乙地共有 种不同的走法.,填10.乘坐每一种交通工具都可由甲地到达乙地，故共有423110种走法.,分类计数原理,50,分步计数原理,分步计数原理,两个计数原理的综合应用,(2003年全国高考题)如图所示,一个地区分为5个行政区域,现给地图着色,要求相邻区域不得使用同一颜色,现有4种颜色可供选择,则不同的着色方法有_种.(以数字作答),

2、两个计数原理的综合应用,(2003年全国高考题)如图所示,一个地区分为5个行政区域,现给地图着色,要求相邻区域不得使用同一颜色,现有4种颜色可供选择,则不同的着色方法有_种.(以数字作答),同类变式,解:因区域1与其他四个区域都相邻,宜先考虑区域1,有4种涂法.,排列、组合,计数原理,计 数 原 理,二项式定理,组合,通项,二项式定理,二项式系数性质,分类计数原理,分步计数原理,排列,排列的定义,排列数公式,组合的定义,组合数公式,组合数性质,应 用,做一件事或完成一项工作的方法数,直接(分类)完成,间接(分步骤)完成,做一件事,完成它可以有n类办法,第一类办法中有m1种不同的方法,第二类办法

3、中有m2种不同的方法,第n类办法中有mn种不同的方法,那么完成这件事共有N=m1+m2+m3+mn种不同的方法.,做一件事,完成它可以有n个步骤,做第一步中有m1种不同的方法,做第二步中有m2种不同的方法,第n步中有mn种不同的方法,那么完成这件事共有N=m1m2m3mn 种不同的方法.,1.两个原理的区别于联系,【结论】集合A中有m个元素，集合B中有n个元素，那么从A到B可以构造nm个映射.,解:第一步，给a找对应元素，有3种方法； 第二步，给b找对应元素，有3种方法； 第三步，给c找对应元素，有3种方法； 第四步，给d找对应元素，有3种方法； 第五步，给e找对应元素，有3种方法.,例1.设

4、 A=a, b, c, d, e , B=x, y, z, 从A到B共有多少 种不同的映射?,一 映射个数问题,形成一个映射,就是让A中所有元素都找到对应元素.,则共有方法种数N=35.,例1.设A=a, b, c, d, e, f , B=x, y, z, 从A到B共有多少种不同的映射?,【1】设A=1, 2, 3, B=4, 5, 6,从A到B满足1的象是4的映射有多少种?,【2】设集合A =x, y, z, B =-1, 0, 1, 映射f:AB满足f (x)+f (y) + f (z)=0的映射有多少种?,练一练,【3】已知集合Aa,b,c,d ,集合B1, 2, 3, 4, 5,集合

5、C= e, f, g, h . (1)从集合B 到集合A可以建立多少个不同的映射? (2)在集合A到集合B的映射中,若要求集合A中的不同元素的象也不同,这样的映射有多少个? (3)从集合A到集合C可以建立多少个一一映射?,练一练,例2.集合A=a, b, c, d, e,它的子集个数为_,真子集个数为_,非空子集个数为_,非空真子集个数为_.,二 子集问题,【1】集合M满足1, 2M0, 1, 2, 3, 4, 5, 则这样的集合M有多少个？,变式练习,真子集有_个， 非空子集个数为_， 非空真子集个数有_.,【规律】n元集合a1, a2, , an,的不同子集有个_个.,2n,二 子集问题,

6、解: 按地图A, B, C, D四个区域依次分四步完成, 第一步, m1 = 3 种, 第二步, m2 = 2 种, 第三步, m3 = 1 种, 第四步, m4 = 1 种,三、着色问题,例3.如图,要给地图A, B, C, D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？,所以根据乘法原理, 得到不同的涂色方案种数共有,N = 3211 = 6 种.,例3.如图,要给地图A, B, C, D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？,三、着色问题,

7、用红,黄,绿,黑四种不同的颜色涂入下图中的五个区域内,要求相邻的两个区域的颜色都不相同,则有多少种不同的涂色方法？,当B与D不同色时, 有43211=24种.,解:当B与D同色时, 有43212=48种;,故共有48+24=72种不同的涂色方法.,练一练,点评:像这类给区域涂色的问题,我们应该给区域依次标上相应的序号,以便分析问题,在给各区域涂色时,要注意不同的涂色顺序其解题就有繁简之分.,如本例若按A、B、E、D、C顺序涂色时,在最后给区域C涂色时,就应考虑A与E是否同色,B与D是否同色这两种情况.因此在分析解决这类问题时,应按不同的涂色顺序多多尝试,看那一个最简单.本例易错点:未考虑B与D

8、是否同色.,(2003年全国高考题)如图所示,一个地区分为5个行政区域,现给地图着色,要求相邻区域不得使用同一颜色,现有4种颜色可供选择,则不同的着色方法有_种.(以数字作答),同类变式,解:因区域1与其他四个区域都相邻,宜先考虑区域1,有4种涂法.,同类变式,(2)若区域2,4不同色,先涂区域2有3种方法,再涂区域4有2种方法,此时区域3,5也都只有1种涂法,涂法总数为4321=24种,因此涂法共有72种.,(1)若区域2,4同色,有3种涂法,此时区域3,5均有两种涂法,涂法总数为4322=48种;,例4.用0, 1, 2, 3, 4, 5这六个数字, (1)可以组成多少个各位数字不允许重复

9、的六位的自然数？ (2)可以组成多少个各位数字不允许重复的三位的奇数? (3)可以组成多少个各位数字不重复的小于1000的自然数? (4)可以组成多少个大于3000,小于5421且各位数字不允许重复的四位数?,四、排数字问题,【1】1, 2, 3, 4数字可以组成多少个没有重复数字能被3整除的三位数？,【2】随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容.交通管理部门出台了一种汽车牌照组成办法，每一个汽车牌照都必须有个不重复的英文字母和个不重复的阿拉伯数字,并且个字母必须合成一组出现,个数字也必须合成一组出现，那么这种办法共能给多少辆汽车上牌照?,练一练,第二步:让

10、与甲取走的卡片相对应的人来拿,有3种拿法.(例如甲拿的是2，则乙有3种拿法.),总的方法数 N=3311=9.,方法一:采用”分步”处理,第一步:甲先拿,按规定甲可拿2，3，4当中的一张,有3种方法.,第三步:让剩余的两个人拿，都均有1种拿法.,例5.同室4人各写1张贺年卡，先集中起来，然后每人从中各拿1张别人送出的贺年卡，则4张贺年卡不同的分配方式有 种.,五、综合问题,9,树图法,甲 乙 丙 丁,2,1 3 4,4 4 1,3 1 3,3,1 4 4,2 2 1,4 1 2,4,1 3 3,2 1 2,3 2 1,解:四名同学分别为: 甲、乙、丙、丁, 所写贺卡依次为 1， 2， 3， 4

11、.,例6.自然数4320有多少个正约数？,解：432025335,其正约数的结构式为,其中可取0,1,2,3,4, 5;可取0, 1, 2, 3;可取0,1.,即在,所形成的取值集合中,各取一个元素填入上式, 就得4320的一个约数.,第一步：取20，21，22，23，24，25有6种; 第二步：取30，31，32，33有4种； 第三步：取50，51有2种.,由分步计数原理，共有64248种.,【1】630的不同的正约数的个数是_.,练一练,解:63023257,【2】5张1元币，4张1角币，1张5分币，2张2分币，可组成_种不同的币值？(1张不取，即0元0分0角不计在内),元：0，1，2，3

12、，4，5 角：0，1，2，3，4 分：0，2，4，5，7，9,6561179,179,【3】三边长均为整数,且最大边长为11的三角形共有多少个?,解:另两边长用x,y表示,且不妨设1xy11,要构成三角形,必须x+y12.,当 y=11时,有11个三角形;,当 y=10时,有9个三角形;,当 y=6时,有1个三角形;,所以,所求三角形的个数共有,练一练,【3】在所有的两位数中,个位数字大于十位数字的两位数共有多少个？,分析1:按个位数字是2,3,4,5,6,7,8,9分成8类,在每一类中满足条件的两位数分别是 1个,2个,3个,4个,5个,6个,7 个,8 个. 则根据加法原理共有 1 +2

13、+3 +4 + 5 + 6 + 7 + 8 =36 (个).,分析2:按十位数字是1,2,3,4,5,6,7,8分成8类,在每一类中满足条件的两位数分别是 8个,7个,6个,5个,4个,3个,2个,1个. 则根据加法原理共有 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 (个),例7 .一种号码锁有4个拨号盘，每个拨号盘上有从0到9共10个数字，这4个拨号盘可以组成多少个四位数字的号码？,解：1010101010 000.,用0, 1 , 2, ，9可以组成多少个8位码；,1010101010101010108.,9101010101010109107.,练一练,用0,

14、 1 , 2, ，9可以组成多少个8位整数；,91010109 000,99874 536,练一练,用0, 1 , 2, ，9可以组成多少个无重复数字的4位整数；,用0, 1 , 2, ，9可以组成多少个有重复数字的4位整数；,例7 .一种号码锁有4个拨号盘，每个拨号盘上有从0到9共10个数字，这4个拨号盘可以组成多少个四位数字的号码？,例8.4个人各写一张贺年卡,放在一起,然后每个人取一张不是自己写的贺年卡,共有多少种不同的取法?,解:把4个人编号为甲、乙、丙、丁,他们写的4张贺年卡依次为、，则取贺年卡的各种方法全部列举出来为,例4.4个人各写一张贺年卡,放在一起,然后每个人取一张不是自己写的贺年卡,共有多少种不同的取法?,解:把4个人编号为甲、乙、丙、丁,他们写的4张贺年卡依次为、，则取贺年卡的各种方法全部列举出来为,个位数字大于十位数字的两位数共有多少个？,分析1:按个位数字是2,3,4,5,6,7,8,9分成8类,在每一类中满足条件的两位数分别是 1个,2个,3个,4个,5个,6个,7 个,8 个. 则根据加法原理共有 1 +2 +3 +4 + 5 + 6 + 7 + 8 =36 (个).,分析2:按十位数字是1,2,