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

,分类计数原理与分步计数原理,实际问题,从甲地到乙地有3条路，从乙地到丁地有2条路；从甲地到丙地有3条路，从丙地到丁地有4条路， 问：从甲地到丁地有多少种走法？,要回答这个问题，就要用到计数的两个基本原理 分类计数原理与分步计数原理,导入新课,问题一：从甲地到乙地，可以乘火车，也可以乘汽车，一天中，火车有3班，汽车有2班那么一天中，乘坐这些交通工具从甲地到乙地共有多少种不同的走法？,因为一天中乘火车有3种走法，乘汽车有2种走法，每一种走法都可以从甲地到乙地，所以共有：325（种）, 10.1分类计数原理与分步计数原理,1、分类计数原理,定义：如果计数的对象可以分成若干类，使得每两类没有公共 元素，则分别对每一类里的元素计数，然后把各类的元素数目 相加，便得出所要计数的对象的总数。,（加法原理）,即：做一件事情，完成它可以有n类办法,在第一类办法中有m1种 不同的方法,在第二类办法中有m2种不同的方法， 在第n类办法中有mn种不同的方法。那么完成这件事共有 N=m1+m2+mn 种不同的方法。,解：取一个球的方法可以分成两类：,一类是从装白球的袋子里取一个球,60个,40个,例1： 两个袋子里分别装有40个红球，60个白球， 从中任取一个球，有多少种求法？,例1： 两个袋子里分别装有40个红球，60个白球， 从中任取一个球，有多少种求法？,解：取一个球的方法可以分成两类：,一类是从装白球的袋子里取一个球,60个,40个,例1： 两个袋子里分别装有40个红球，60个白球， 从中任取一个球，有多少种求法？,解：取一个球的方法可以分成两类：,一类是从装白球的袋子里取一个白球,60个,40个,有40种取法；,另一类是从装红球的袋子里取一个红球,例1： 两个袋子里分别装有40个红球，60个白球， 从中任取一个球，有多少种求法？,解：取一个球的方法可以分成两类：,一类是从装白球的袋子里取一个白球,40个,60个,有40种取法；,另一类是从装红球的袋子里取一个红球,有60种取法。,因此取法种数共有,40+60=100（种）,例1： 两个袋子里分别装有40个红球，60个白球， 从中任取一个球，有多少种求法？,解：取一个球的方法可以分成两类：,一类是从装白球的袋子里取一个白球,有40种取法；,另一类是从装红球的袋子里取一个红球,40个,60个,问题2：如图,由A村去B村的道路有3条，由B村去C村的道路有2条。从A村经B村去C村，共有多少种不同的走法?,解： 从A村经 B村去C村有2步, 第一步, 由A村去B村有3种方法, 第二步, 由B村去C村有3种方法, 所以 从A村经 B村去C村共有 3 2 = 6 种不同的方法。,2、分步计数原理,定义：如果计数的对象可以分成若干步骤来完成，并且对于 前面几步的每一种完成方式，下一步有相同数目的做法， 则依次计算第一步的做法数目，第二步的做法数目，, 最后一步的做法数目，然后把各步的做法数目相乘，便 得出所要计数的对象的总数。,即：做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事有 N=m1m2mn 种不同的方法。,（乘法原理）,例2： 两个袋子里分别装有40个红球与60个白球， 从中取一个白球和一个红球，有多少种取法？,60个,40个,解：取一个白球和一个红球可以分成两步 来完成：,第一步从装白球的袋子里取一个白球，,例2： 两个袋子里分别装有40个红球与60个白球， 从中取一个白球和一个红球，有多少种取法？,60个,40个,解：取一个白球和一个红球可以分成两步 来完成：,第一步从装白球的袋子里取一个白球，,有60种取法；,对于这每一种取法，第二步从装红球的 袋子里取一个红球，都有40种取法。,因此取一个白球和一个红球的方法共有,60 40=2400（种）,思考：分类计数原理与分步计数原理的区别与联系？,联系：分类计数原理与分步计数原理都是涉及完成一件事的不 同方法的种数的问题 。,区别：分类计数原理与“分类”有关，各种方法相互独立，用 其中任何一种方法都可以完成这件事；分步计数原理 与“分步”有关， 各个步骤相互依存，只有各个步骤都 完成了，这件事才算完成 。,例3： 某班级有男三好学生5人,女三好学生4人。 (1)从中任选一人去领奖, 有多少种不同的选法？ (2) 从中任选男、女三好学生各一人去参加座谈会,有多少种不同的选法？,解: (1) 完成从三好学生中任选一人去领奖这件事,共有2类办法, 第一类办法, 从男三好学生中任选一人, 共有 m1 = 5 种 不同的方法; 第二类办法, 从女三好学生中任选一人, 共有 m2 = 4 种不 同的方法; 所以, 根据加法原理, 得到不同选法种数共有 N = 5 + 4 = 9 种。,例3： 某班级有男三好学生5人,女三好学生4人。 (1)从中任选一人去领奖, 有多少种不同的选法？ (2) 从中任选男、女三好学生各一人去参加座谈会,有多少种不同的选法？,解:,(2) 完成从三好学生中任选男、女各一人去参加座谈会这件事, 需分2步完成, 第一步, 选一名男三好学生,有 m1 = 5 种方法; 第二步, 选一名女三好学生,有 m2 = 4 种方法; 所以, 不同选法种数共有 N = 5 4 = 20 种。,点评: 解题的关键是从总体上看这件事情是“分类完成”,还是“分步完成”，“分类完成”用“加法原理”，“分步完成”用“乘法原理”。,1、书架的第1层放有4本不同的计算机书，第2层放有3本不同 的文艺书，第3层放有2本不同的体育书 （1）从书架上任取1本书，有多少种不同的取法？ （2）从书架的第1、2、3层各取1本书，有多少种不同的取法？,4+3+2=9（种）,4 3 2=24（种）,2、由数字1，2，3，4，5，6可以组成多少个四位数？ （各位上的数字允许重复）,6 5 4 3=360（个）,3、一种号码锁有4个拨号盘，每个拨号盘上有从0到9共10个 数字， 这4个拨号盘可以组成多少个四位数字的号码？,练习1,有些较复杂的问题往往不是单纯的“分类”“分步”可以解决的，而要将“分类”“分步”结合起来运用一般是先“分类”，然后再在每一类中“分步”， 综合应用分类计数原理和分步计数原理请看下面的例题：,注意,例4： 某城市电话号码由8位组成，其中从左边算起的第1位只用 6或8，其余7位可以从前10个自然数0，1，2，,9中任意 选取，允许数字重复。试问：该城市最多可装电话多少门？,1,2,3,4,5,6,7,8,第1类,6,解：装一门电话需要指定一个 电话号码，由题意电话号码可以 分成两类：,第1类电话号码第1位用6，,确定其余7位号码可以分7步完成。,10,10,10,10,10,10,10,因此第一类电话号码共有,1,2,3,4,5,6,7,8,第2类,8,某中学的一幢5层教学楼共有3处楼梯，问从1楼到 5楼共有多少 种不同的走法？,3 3 3 3=81（种）,练习2,实际问题,从甲地到乙地有3条路，从乙地到丁地有2条路；从甲地到丙地有3条路，从丙地到丁地有4条路， 问：从甲地到丁地有多少种走法？,小结,请同学们回答下面的问题 :,1. 本节课学习了那些主要内容？,答: 分类计数原理和分步计数原理。,2. 分类计数原理和分步计数原理的共同点是什么？不同点什么？,答