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

《分类计数原理与分步计数原理》由会员分享，可在线阅读，更多相关《分类计数原理与分步计数原理（23页珍藏版）》请在金锄头文库上搜索。

1、分类计数原理与分步计数原理实际问题实际问题 从甲地到乙地有3条路，从乙地到丁地有2条路；从甲地到丙地有3条路，从丙地到丁地有4条路，问：从甲地到丁地有多少种走法？要回答这个问题，就要用到计数的两个基本原理分类计数原理与分步计数原理分类计数原理与分步计数原理分类计数原理与分步计数原理分类计数原理与分步计数原理导入新课甲地乙地丙地丁地 问题一：问题一：问题一：问题一：从甲地到乙地，可以乘火车，也可从甲地到乙地，可以乘火车，也可以乘汽车，一天中，火车有以乘汽车，一天中，火车有3班，汽车有班，汽车有2班那班那么一天中，乘坐这些交通工具从甲地到乙地共有么一天中，乘坐这些交通工具从甲地到乙地共有多少种不同

2、的走法多少种不同的走法？ 因为一天中乘火车有因为一天中乘火车有3种走法，乘汽车有种走法，乘汽车有2种走法，每一种走法，每一种走法都可以从甲地到乙地，所以共有：种走法都可以从甲地到乙地，所以共有：325（种）（种） 10.1分类计数原理与分步计数原理1、分类计数原理、分类计数原理定义：定义：如果计数的对象可以分成若干类，使得每两类没有公共如果计数的对象可以分成若干类，使得每两类没有公共元素，则分别对每一类里的元素计数，然后把各类的元素数目元素，则分别对每一类里的元素计数，然后把各类的元素数目相加，便得出所要计数的对象的总数。相加，便得出所要计数的对象的总数。（加法原理）即：做一件事情，完成它可以

3、有即：做一件事情，完成它可以有n类办法类办法,在第一类办法中有在第一类办法中有m1种种不同的方法不同的方法,在第二类办法中有在第二类办法中有m2种不同的方法，种不同的方法，在第在第n类办法中有类办法中有mn种不同的方法。那么完成这件事共有种不同的方法。那么完成这件事共有 N=m1+m2+mn种不同的方法。种不同的方法。解：取一个球的方法可以分成两类：解：取一个球的方法可以分成两类：一类是从装白球的袋子里取一个球一类是从装白球的袋子里取一个球60个个40个个例例1：两个袋子里分别装有两个袋子里分别装有40个红球，个红球，60个白球，个白球，从中任取一个球，有多少种求法？从中任取一个球，有多少种求

4、法？例例1：两个袋子里分别装有两个袋子里分别装有40个红球，个红球，60个白球，个白球，从中任取一个球，有多少种求法？从中任取一个球，有多少种求法？解：取一个球的方法可以分成两类：解：取一个球的方法可以分成两类：一类是从装白球的袋子里取一个球一类是从装白球的袋子里取一个球60个个40个个例例1：两个袋子里分别装有两个袋子里分别装有40个红球，个红球，60个白球，个白球，从中任取一个球，有多少种求法？从中任取一个球，有多少种求法？解：取一个球的方法可以分成两类：解：取一个球的方法可以分成两类：一类是从装白球的袋子里取一个白球一类是从装白球的袋子里取一个白球60个个40个个有有40种取法；种取法；

5、另一类是从装红球的袋子里取一个红球另一类是从装红球的袋子里取一个红球例例1：两个袋子里分别装有两个袋子里分别装有40个红球，个红球，60个白球，个白球，从中任取一个球，有多少种求法？从中任取一个球，有多少种求法？解：取一个球的方法可以分成两类：解：取一个球的方法可以分成两类：一类是从装白球的袋子里取一个白球一类是从装白球的袋子里取一个白球40个个60个个有有40种取法；种取法；另一类是从装红球的袋子里取一个红球另一类是从装红球的袋子里取一个红球有有60种取法。种取法。因此取法种数共有因此取法种数共有40+60=100（种）（种）例例1：两个袋子里分别装有两个袋子里分别装有40个红球，个红球，6

6、0个白球，个白球，从中任取一个球，有多少种求法？从中任取一个球，有多少种求法？解：取一个球的方法可以分成两类：解：取一个球的方法可以分成两类：一类是从装白球的袋子里取一个白球一类是从装白球的袋子里取一个白球有有40种取法；种取法；另一类是从装红球的袋子里取一个红球另一类是从装红球的袋子里取一个红球40个个60个个 问题问题2：如图,由A村去B村的道路有3条，由B村去C村的道路有2条。从A村经B村去C村，共有多少种不同的走法?A村B村C村北南中北南 解： 从A村经 B村去C村有2步, 第一步, 由A村去B村有3种方法, 第二步, 由B村去C村有3种方法, 所以 从A村经 B村去C村共有 3 2

7、= 6 种不同的方法。2、分步计数原理、分步计数原理定义：定义：如果计数的对象可以分成若干步骤来完成，并且对于如果计数的对象可以分成若干步骤来完成，并且对于 前面几步的每一种完成方式，下一步有相同数目的做法，前面几步的每一种完成方式，下一步有相同数目的做法，则依次计算第一步的做法数目，第二步的做法数目，则依次计算第一步的做法数目，第二步的做法数目，,最后一步的做法数目，然后把各步的做法数目相乘，便最后一步的做法数目，然后把各步的做法数目相乘，便得出所要计数的对象的总数。得出所要计数的对象的总数。即：做一件事情，完成它需要分成即：做一件事情，完成它需要分成n个步骤，做第一步有个步骤，做第一步有m

8、1种不同的方法，做第二步有种不同的方法，做第二步有m2种不同的方法，种不同的方法，做第，做第n步有步有mn种不同的方法，那么完成这件事有种不同的方法，那么完成这件事有 N=m1m2mn种不同的方法种不同的方法。（乘法原理）（乘法原理）例例2： 两个袋子里分别装有两个袋子里分别装有40个红球与个红球与60个白球，个白球，从中取一个白球和一个红球，有多少种取法？从中取一个白球和一个红球，有多少种取法？60个个40个个解：取一个白球和一个红球可以分成两步解：取一个白球和一个红球可以分成两步来完成：来完成：第一步从装白球的袋子里取一个白球，第一步从装白球的袋子里取一个白球，例例2： 两个袋子里分别装有

9、两个袋子里分别装有40个红球与个红球与60个白球，个白球，从中取一个白球和一个红球，有多少种取法？从中取一个白球和一个红球，有多少种取法？60个个40个个解：取一个白球和一个红球可以分成两步解：取一个白球和一个红球可以分成两步来完成：来完成：第一步从装白球的袋子里取一个白球，第一步从装白球的袋子里取一个白球，有有60种取法；种取法；对于这每一种取法，第二步从装红球的对于这每一种取法，第二步从装红球的袋子里取一个红球，都有袋子里取一个红球，都有40种取法。种取法。因此取一个白球和一个红球的方法共有因此取一个白球和一个红球的方法共有60 40=2400（种）种）思考：分类计数原理与分步计数原理的区

10、别与联系？思考：分类计数原理与分步计数原理的区别与联系？联系：分类计数原理与分步计数原理都是涉及完成一件事的不联系：分类计数原理与分步计数原理都是涉及完成一件事的不 同方法的种数的问题同方法的种数的问题 。区别：分类计数原理与区别：分类计数原理与“分类分类”有关，各种方法相互独立，有关，各种方法相互独立，用用 其中任何一种方法都可以完成这件事；分步计数原理其中任何一种方法都可以完成这件事；分步计数原理 与与“分步分步”有关，有关， 各个步骤相互依存，只有各个步骤各个步骤相互依存，只有各个步骤都都 完成了，这件事才算完成完成了，这件事才算完成 。例例3： 某班级有男三好学生某班级有男三好学生5人

11、人,女三好学生女三好学生4人。人。 (1)从中任选一人去领奖从中任选一人去领奖, 有多少种不同的选法？有多少种不同的选法？ (2) 从中任选男、女三好学生各一人去参加座谈会从中任选男、女三好学生各一人去参加座谈会,有有多少种不同的选法？多少种不同的选法？解解: (1) 完成从三好学生中任选一人去领奖这件事完成从三好学生中任选一人去领奖这件事,共有共有2类办类办法法, 第一类办法第一类办法, 从男三好学生中任选一人从男三好学生中任选一人, 共有共有 m1 = 5 种种 不同的方法不同的方法; 第二类办法第二类办法, 从女三好学生中任选一人从女三好学生中任选一人, 共有共有 m2 = 4 种种不不

12、 同的方法同的方法; 所以所以, 根据加法原理根据加法原理, 得到不同选法种数共有得到不同选法种数共有 N = 5 + 4 = 9 种。种。例例3： 某班级有男三好学生某班级有男三好学生5人人,女三好学生女三好学生4人。人。 (1)从中任选一人去领奖从中任选一人去领奖, 有多少种不同的选法？有多少种不同的选法？ (2) 从中任选男、女三好学生各一人去参加座谈会从中任选男、女三好学生各一人去参加座谈会,有有多少种不同的选法？多少种不同的选法？解解: (2) 完成从三好学生中任选男、女各一人去参加座谈完成从三好学生中任选男、女各一人去参加座谈会这件事会这件事, 需分需分2步完成步完成, 第一步第一

13、步, 选一名男三好学生选一名男三好学生,有有 m1 = 5 种方法种方法; 第二步第二步, 选一名女三好学生选一名女三好学生,有有 m2 = 4 种方法种方法; 所以所以, 不同选法种数共有不同选法种数共有 N = 5 4 = 20 种。种。点评点评: 解题的关键是从总体上看这件事情是解题的关键是从总体上看这件事情是“分类完成分类完成”,还是还是“分步完成分步完成”，“分类完成分类完成”用用“加法原理加法原理”，“分步完成分步完成”用用“乘法原理乘法原理”。 1 1、书架的第、书架的第1 1层放有层放有4 4本不同的计算机书，第本不同的计算机书，第2 2层放有层放有3 3本不同本不同 的文艺书

14、，第的文艺书，第3 3层放有层放有2 2本不同的体育书本不同的体育书（1 1）从书架上任取）从书架上任取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个个 数字，数

15、字， 这这4个拨号盘可以组成多少个四位数字的号码？个拨号盘可以组成多少个四位数字的号码？ 10 10 10 10=104练习1 有些较复杂的问题往往不是单纯的有些较复杂的问题往往不是单纯的“分类分类”“分分步步”可以解决的，而要将可以解决的，而要将“分类分类”“分步分步”结合起来结合起来运用一般是先运用一般是先“分类分类”，然后再在每一类中，然后再在每一类中“分步分步”， 综合应用分类计数原理和分步计数原理请看下综合应用分类计数原理和分步计数原理请看下面的例题：面的例题： 注意注意例例4： 某城市电话号码由某城市电话号码由8位组成，其中从左边算起的第位组成，其中从左边算起的第1位只用位只用6或

16、或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因此第一类电话号码共有因此第一类电话号码共有10 10 10 10 10 10 10=1071

17、 2 3 4 5 6 7 8第第2类类8同理，第同理，第2类电话号码也有类电话号码也有10 个，个，7因此，该城市所用的电话号码共有因此，该城市所用的电话号码共有10 +10 =2 10 个个从而最多可装电话从而最多可装电话2 10 门，即两千万门。门，即两千万门。7777 某中学的一幢某中学的一幢5层教学楼共有层教学楼共有3处楼梯，问从处楼梯，问从1楼到楼到 5楼楼共有多少共有多少 种不同的走法？种不同的走法？ 3 3 3 3=81（种）种）练习2实际问题实际问题 从甲地到乙地有从甲地到乙地有3条路，从乙地到丁地有条路，从乙地到丁地有2条路；条路；从甲地到丙地有从甲地到丙地有3条路，从丙地到

18、丁地有条路，从丙地到丁地有4条路，条路，问：从甲地到丁地有多少种走法？问：从甲地到丁地有多少种走法？甲地乙地丙地丁地解：要完成从甲地到丁地这件事情有解：要完成从甲地到丁地这件事情有两种路线可以走，即可以分为两类：两种路线可以走，即可以分为两类：甲地甲地 乙地乙地 丁地丁地甲地甲地 丙地丙地 丁地丁地第一类又可以分为两步，第一步有第一类又可以分为两步，第一步有3种种方法，第二步有方法，第二步有2种方法，因此第一类种方法，因此第一类走法有走法有3 2=6（种）种）同理第二类走法有同理第二类走法有3 4=12（种）种）所以，从甲地到丁地有所以，从甲地到丁地有6+12=18种走法。种走法。小结请同学们

19、回答下面的问题请同学们回答下面的问题 :1. 本节课学习了那些主要内容？本节课学习了那些主要内容？ 答答: 分类计数原理和分步计数原理。分类计数原理和分步计数原理。 2. 分类计数原理和分步计数原理的共同点是什么？不同点什么分类计数原理和分步计数原理的共同点是什么？不同点什么？ 答答: 共同点是共同点是, 它们都是研究完成一件事情它们都是研究完成一件事情, 共有多少共有多少种不同的方法。种不同的方法。 不同点是不同点是, 它们研究完成一件事情的方式不同它们研究完成一件事情的方式不同, 分分类计数原理是类计数原理是“分类完成分类完成”, 即任何一类办法中的任何即任何一类办法中的任何一个方法都能完成这件事。分步计数原理是一个方法都能完成这件事。分步计数原理是“分步完分步完成成”, 即这些方法需要分步即这些方法需要分步,各个步骤顺次相依各个步骤顺次相依,且每一且每一步都完成了步都完成了,才能完成这件事情。这也是本节课的重点。才能完成这件事情。这也是本节课的重点。