分类计数原理与分步计数原理上课精讲.ppt

分类计数原理与分步计数原理,狐狸想从草地逃到小岛，可以走水路,也可以走陆路，走水路有2艘船，走陆路有3辆车，问：乘坐这些交通工具,共有多少种不同的方法，可以从草地逃到小岛？,狐狸总共有多少种方法逃到小岛？,草地到小岛,2类,能,2种、3种,2+3=5种,水路2种,陆路3种,如果狐狸还有4辆自行车可以选择呢?,2+3+4=9种,草地,小岛,如果狐狸还有m3辆自行车可以选择呢？,N=m1+m2+m3,如果狐狸从草地到小岛的交通工具有n类，第一类m1种，第二类有m2种，.，第n类有mn种不同的方法，那么狐狸到安全地有多少种不同的方法？,N=m1+m2+mn,狐狸总共有多少种方法逃到小岛？,水路m1种,陆路m2种,草地,小岛,N=m1+m2,那么完成这件事共有N=m1+m2+mn种不同的方法。,(注:本原理又称加法原理),分类计数原理:,完成一件事情,有n类办法,在第一类办法中有m1种不同的方法,在第二类办法中有m2种不同的方法，,，在第n类办法中有mn种不同的方法.,关于分类计数原理的几点注意：,各类办法之间相互独立，都能完成这件事，且办法总数是各类办法相加；,狐狸有一共有多少种不同的方法，可以从草地逃回到自己的家（安全地）？,草地到安全地,2步,不能,5种、2种,52=10种,a1a2a3a4a5,b1b2,别墅,如果狐狸还有4种方法到别墅压惊呢?,524=40种,分步计数原理完成一件事情,需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法,那么完成这件事共有N=m1m2mn种不同的方法。,(注:本原理又称乘法原理.),关于分步计数原理的几点注意：,各个步骤之间相互依存，且方法总数是各个步骤的方法数相乘；,做一件事情，完成它可以有n类，在第一类办法中有m1种不同的方法，在第二类中有m2种不同的法，在第n类方法中有mn类不同的方法，那么完成这件事情共有,种不同的方法,做一件事情，完成它需要分成n个步骤，在第一步有m1种不同的方法，在第二步有m2种不同的法，在第n步有mn种不同的方法，那么完成这件事情共有,（加法原理）,（乘法原理）,分类计数原理,分步计数原理,N=m1+m2+mn,N=m1m2mn,种不同的方法,相互联系，分步到达.,相互独立，直达目的.,比较两个原理：,分类计数原理与分步计数原理的几点说明,共同点：,它们都是研究完成一件事情,共有多少种不同的方法。,不同点：,分步计数原理是“分步完成”的,这些方法需要几个分步骤,各个步骤顺次相依,且只有依次完成所有各步，才能达到完成这件事情的目的。,因此：在处理具体问题时，必须关注以下这些问题：,分类计数原理是“分类完成”的,这些方法间是彼此独立的，即任何一类办法中的任何一个方法都能达到完成这件事的目的。,1.要完成一件什么事情?,2.完成这件事情有什么要求?,3.考虑用分类计数原理与还是分步计数原理?,有三类方法,能,4种、3种、2种,4+3+2=9种,从书架上取一本书,例1书架的第1层放有4本不同的计算机书，第2层放有3本不同的文艺书，第3层放有2本不同的体育书。(1)从书架上任取1本书，有多少种不同的取法。,例1书架的第1层放有4本不同的计算机书，第2层放有3本不同的文艺书，第3层放有2本不同的体育书。,解：从书架上任意取一本书，,第1类办法是从第1层取1本计算机书，有4种方法,第2类办法是从第2层取1本文艺书，有3种方法,第3类办法是从第3层取1本体育书，有2种方法,由分类计数原理知,共有4+3+2=9种取法。,（1）从书架上任取一本书，有多少种取法？,有3类方法：,有三个步骤,4种、3种、2种,432=24种,从书架上每层取一本书,不能,例1书架的第1层放有4本不同的计算机书，第2层放有3本不同的文艺书，第3层放有2本不同的体育书。,(2)从书架的第1、2、3层各取1本书,有多少种取法？,例1书架的第1层放有4本不同的计算机书，第2层放有3本不同的文艺书，第3层放有2本不同的体育书。,(2)从书架的第1、2、3层各取一本书,有多少种取法？,需要分三步完成,第1步,从第1层取1本书,有4种方法,第2步,从第2层取1本书,有3种方法,第3步,从第3层取1本书,有2种方法.,由分步计数原理知,共有432=24种取法,解：从书架的第1、2、3层各取一本书,例2一种号码锁有4个拨号盘,每个拨号盘上有从0到9共10个数字,这4个拨号盘可以组成多少个四位数字的号码?,N=10101010=104,解：要在4个拨号盘上各取1数字组成一个四位数字的号码，,由分步计数原理，4个拨号盘上各取1数字组成四位数字的号码个数是,需要分四步完成:,第1步,从第1个拨号盘内拨一个数字，有10种方法,第2步,从第2个拨号盘内拨一个数字，有10种方法,第3步,从第3个拨号盘内拨一个数字，有10种方法,第4步,从第4个拨号盘内拨一个数字，有10种方法,3.分类计数原理和分步计数原理的共同点：都是把一个事件分解成若干个分事件来完成；不同点：前者分类，后者分步；如果分事件相互独立，分类完备，就用分类计数原理；如果分事件相互关联，缺一不可，就用分步计数原理。,分类计数原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第一类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法。那麽完成这件事共有N=m1+m2+mn种不同的方法。,2.分步计数原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法。那麽完成这件事共有N=m1m2mn种不同的方法。,复习,分类加法计数原理,练习2：要从甲、乙、丙3名工人中选出2名分别上日班和晚班，有多少种不同的选法？,解：从3名工人中选出2名分别上日班和晚班，,可以看成是经过先选1名上日班，再选1名上晚班这两个步骤完成：,先选1名上日班，共有3种选法；,上日班的工人选定后再选1名上晚班，上晚班的工人有2种选法，,根据分步计数原理,所求的不同的选法数是,（先定班，再安排人）,也可以看成是先定人，再安排班这两个步骤完成：,3人中选两人，有3种方法,两个人分别上日班和晚班，有2种方法,根据分步计数原理,所求的不同的选法数是,分步乘法计数原理,1、把四封不同的信任意投入三个信箱中,不同投法种数是()A.12B.64C.81D.7,2、火车上有10名乘客，沿途有5个车站，乘客下车的可能方式有（）种A.510B.105C.50D.以上都不对,练习,C,A,35个高中应届毕业生报考3所重点院校，每人报且仅报一所院校，则不同的报名方法共有（）种。（A）35（B）53（C）15（D）6,A,4A=1，2，3，4，B=5，6，7，则从A到B的映射有个。,81,6.四名研究生各从A、B、C三位教授中选一位作自己的导师，共有_种选法；三名教授各从四名研究生中选一位作自己的学生，共有_种选法。,43,5.某中学的一幢5层教学楼共有3处楼梯口,问从1楼到5楼共有多少种不同的走法?,答：3333=34=81（种）,34,7乘积(a1+a2+a3)(b1+b2+b3+b4)(c1+c2+c3+c4+5)展开后共有项？,10由壹元币3张，伍元币1张，拾元币2张，可以组成种不同的币值。,23,9从1，2，3，4，7，9中任取不相同的两个数，分别作为对数的底数和真数，可得到个不同的对数值,17,A,两个计数原理的综合应用,易错防范,如图,要给地图A、B、C、D四个区域分别涂上红，黄，蓝种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？,共3211=6（种）,3种,2种,1种,1种,理论分析：,题型四：涂色问题,实际操作：,解:按地图A、B、C、D四个区域依次分四步完成,第一步,m1=3种,第二步,m2=2种,第三步,m3=1种,第四步,m4=1种,所以根据乘法原理,得到不同的涂色方案种数共有N=3211=6种。,变式：如图,要给地图A、B、C、D四个区域分别涂上红，黄，蓝种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？,3种,2种,1种,2种,共3212=12（种）,练习1、用红、黄、蓝3种颜色给下图中五个区域涂色，要求相邻两个区域的颜色不同，有多少种不同的涂法？,解：涂色可分5步进行：第一步：涂区域，有3种选择；,第二步：涂区域，有2种选择；,第三步：涂区域，有1种选择；,第四步：涂区域，有1种选择；,第五步：涂区域，有2种选择；,由分步