分类加法计数原理与分布乘法计数原理(2)课件高二下学期数学人教A版选择性

6.1分类加法计数原理与分步乘法计数原理第六章计数原理2024/4/14高二数学备课组引

入

完成一件事,如果有n类方案,第1类方案中有m1种不同的方法，第2类方案中有m2种不同的方法，……，第n类方案中有mn种不同的方法，那么完成这件事共有N=m1+m2+…+mn种不同的方法.1.分类加法计数原理2.分步乘法计数原理

如果完成一件事需要n个步骤，做第1步有m1种不同的方法，做第2步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N＝m1×m2×…×mn种不同的方法.引

入分类加法计数原理分步乘法计数原理相同点不同点注意点用来计算完成一件事的方法种数每类方案中的每一种方法都能独立完成这件事每步依次完成才算完成这件事情（每步中的每一种方法不能独立完成这件事）相加相乘类类独立步步关联不重不漏缺一不可分类、分步、探究新知解：从3幅画中选出2幅分别挂在左、右两边墙上，可以分两个步骤完成：

第1步，从3幅画中选1幅挂在左边墙上，有3种选法；

第2步，从剩下的2幅画中选1幅挂在右边墙上，有2种选法.根据分步乘法计数原理，不同挂法的种数为

N＝3×2=6.这6种挂法如右图所示.例4要从甲、乙、丙3幅不同的画中选出2幅，分别挂在左、右两边墙上的指定位置，共有多少种不同的挂法?.乙乙丙甲右边丙乙甲左边得到的挂法甲乙甲丙乙甲乙丙丙甲丙乙甲丙例题讲解例5给程序模块命名，需要用3个字符，其中首字符要求用字母A~G或U~Z，后两个要求用数字1~9，最多可以给多少个程序命名？解2:

首字符用A~G给程序命名的个数为7×9×9＝567.

首字符用U~Z给程序命名的个数为6×9×9＝486.

∴总的不同名称的个数是567＋486＝1053.问题1你还能给出不同的解法吗?解:由分类加法计数原理，首字符不同选法的种数为7＋6＝13.

后两个字符从1~9中选，因为数字可以重复，所以不同选法的种数都为9.

由分步乘法计数原理，不同名称的个数是13×9×9＝1053，

即最多可以给1053个程序模块命名.例题讲解例6电子元件很容易实现电路的通与断、电位的高与低等两种状态，而这也是最容易控制的两种状态.因此计算机内部就采用了每一位只有0或1两种数字的记数法，即二进制.为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用1个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由8个二进制位构成.(1)1个字节(8位)最多可以表示多少个不同的字符?(2)计算机汉字国标码包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示?解:(1)由分步乘法计数原理，1个字节最多可以表示不同的字符个数是2×2×2×2×2×2×2×2＝28＝256.(2)由(1)知，1个字节最多可以表示256个不同的字符，则2个字节最多就可以表示256×256＝65536>6763，所以每个汉字至少要用2个字节表示.课堂练习1.某电话局管辖范围内的电话号码由8位数字组成，其中前4位的数字是不变的，后4位数字都是0~9中的一个数字，这个电话局不同的电话号码最多有多少个?解：104＝10000(个).2.从5名同学中选出正、副组长各1名，有多少种不同的选法?解：5×4＝20(种).3.从1,2,

‧‧‧,19,20中任选一个数作被减数，再从1,2,

‧‧‧,10中任选一个数作减数，然后写成一个减法算式，共可得到多少个不同的算式?解：20×10＝200(个).例题讲解例7

五名学生报名参加四项体育比赛，每人限报一项，报名方法的种数为多少？又他们争夺这四项比赛的冠军，获得冠军的可能性有多少种？解:（1）5名学生中任一名均可报其中的任一项，因此每个学生都有4种报名方法，5名学生都报了项目才能算完成这一事件故报名方法种数为4×4×4×4×4=45种.（2）每个项目只有一个冠军，每一名学生都可能获得其中的一项获军，因此每个项目获冠军的可能性有5种故有n=5×5×5×5=54种.课堂练习1.某教学楼有四个不同的楼梯，3名学生要下楼，共有多少种不同的下楼方法?2.有4名同学要争夺3个比赛的冠军，冠军获得者共有多少可能?3.四封信投入三个信箱，有多少种投法?4.某公共汽车上有10名乘客，沿途有5个车站，乘客下车的可能方式有多少种?4343345105.75600有多少个正约数?有多少个奇约数?120课堂练习5.75600有多少个正约数?有多少个奇约数?解:由于75600=24×33×52×775600的每个约数都可以写成2i·3j·5k·7l的形式,其中0≤i≤4，0≤j≤3，0≤k≤2，

0≤l≤1要确定75600的一个约数,可分四步完成,即i，j，k，l分别在各自的范围内任取一个值，这样i有5种取法，j有4种取法，k有3种取法，l有2种取法，根据分步计数原理得约数的个数为5×4×3×2=120个.探究新知1．如果完成一件事有两类方案,这两类方案彼此之间是相互独立的,无论哪一类方案中的哪一种方法都能单独完成这件事,求能完成这件事的方法种数就用分类加法计数原理．2．如果完成一件事需要分成多个步骤,各个步骤都是不可缺少的,需要依次完成所有步骤,才能完成这件事，而完成每一个步骤有若干种不同的方法,求能完成这件事的方法种数就用分步乘法计数原理．

用两个计数原理解决具体问题时，首先，要分清是“分类”还是“分步”，其次，要清楚“分类”或“分步”的具体标准，在“分类”时要做到“不重不漏”，在“分步”时要正确设计“分步”的程序，注意步与步之间的关联（连续性）．方法总结例题讲解例8计算机编程人员在编写好程序以后需要对程序进行测试.程序员需要知道到底有多少条执行路径(程序从开始到结束的路线)，以便知道需要提供多少个测试数据.一般地，一个程序模块由许多子模块组成.下图是一个具有许多执行路径的程序模块，它有多少条执行路径?

另外，为了减少测试时间，程序员需要设法减少测试次数.你能帮助程序员设计一个测试方法，以减少测试次数吗?解：由程序模块可得，执行路径条数有(18＋45＋28)×(38＋43)＝7371.

为了减少测试次数，可单独测试5个模块和模块1,2,3与模块4,5之间的信息交流是否正常即可，这样测试的次数只有(18＋45＋28＋38＋43)+(3×2)＝178(次).例题讲解例9通常，我国民用汽车号牌的编号由两部分组成:第一部分为用汉字表示的省、自治区、直辖市简称和用英文字母表示的发牌机关代号，第二部分为由阿拉伯数字和英文字母组成的序号，如图所示.其中，序号的编码规则为:(1)由10个阿拉伯数字和除O，I之外的24个英文字母组成；(2)最多只能有2个英文字母.

如果某地级市发牌机关采用5位序号编码，那么这个发牌机关最多能发放多少张汽车号牌?解：当序号中没有字母时，号牌张数为105＝100000.当序号中有1位字母时，号牌张数为5×24×104＝1200000.当序号中有2位字母时，号牌张数为10×242×103＝5760000.所以这个发牌机关最多能发的汽车号牌张数为7060000.探究新知用两个计数原理解决计数问题时，最重要的是在开始计算之前要仔细分析两点:

(1)要完成的“一件事”是什么;

(2)需要分类还是需要分步.

分类要做到“不重不漏”.分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数.

分步要做到“步骤完整”，即完成了所有步骤，恰好完成任务.分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数.归纳：例题讲解组数问题:例10

从数字0,1,2,3,4,5中取出4个数字组成四位数，(1)能组成多少个四位数？(2)能被5整除的四位数有多少个？分析：(1)要完成的一件事是组成四位数，所以首位数字不能是0;

(2)要使所组成的四位数能被5整除，则末位数字必须是0和5中的1个．解：(1)第1步，千位上的数不能取0，只能取1,2,3,4,5中的一个，有5种选择；

第2步，由于取了1个数放千位上，故可从剩下的5个数中选1个放百位上，所以有5种选择；

第3步，从剩下的4个数中选1个放十位上，有4种选择；

第4步，从剩下的3个数中选1个放个位上，有3种选择．根据分步乘法计数原理，组成的四位数的个数为5×5×4×3=300.例题讲解组数问题:例10

从数字0,1,2,3,4,5中取出4个数字组成四位数，(1)能组成多少个四位数？(2)能被5整除的四位数有多少个？解：(2)如果组成的四位数能被5整除，那么四位数个位上的数字只能是0或5.根据分类加法计数原理，能被5整除的四位数的个数为60+48=108.第1类，当个位上的数字为0时，依次取千位、百位、十位上的数字，分别有5种选择、4种选择、3种选择，所以满足要求的四位数的个数为5×4×3=60;第2类，当个位上的数字为5时，依次取千位、百位、十位上的数字，分别有4种选择、4种选择、3种选择，所以满足要求的四位数的个数为4×4×3=48.探究新知2．解决组数问题时，应特别注意其限制条件，有些条件是隐藏的，要善于挖掘．排数时，要注意特殊元素、特殊位置优先的原则.[提醒]数字“0”不能排在两位数字或两位数字以上的数的最高位.1．对于组数问题，一般按特殊位置（一般指末位和首位）由谁占领分类，分类中再按特殊位置（或者特殊元素）优先的方法分步完成．如果正面分类较多，可采用间接法从反面求解．解决组合数问题的方法例题讲解变式：

从数字1,2,3,4,5中取出3个数字（允许重复）,组成三位数，各位数字之和等于6,则这样的三位数的个数为()

A.7

B.9

C.10

D.13解：从数字1,2,3,4,5中取出3个数字（允许重复）,组成三位数，各位数字之和等于6,可分为三类情况：(1)当三个数为1,1,4时，4可以在个位、十位、百位，共有3个这样的三位数；(2)当三个数为1,2,3时，共有3×2×1=6个这样的三位数；(3)当三个数为2,2,2时，只有1个这样的三位数.由分类加法计数原理可得，共有3+6+1=10个，即这样的三位数共有10个.C例题讲解例11

如图,要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？染色与种植问题:解:

按地图A、B、C、D四个区域依次分四步完成,

所以根据乘法原理,得到不同的涂色方案种数共有N=3×2×1×1=6种.第一步涂D,m1=3种,第二步涂B,m2=2种,第三步涂C,m3=1种,第四步涂A,m4=1种,例题讲解变式1：若用2色、4色、5色等,结果又怎样呢？

答:它们的涂色方案种数分别是：2色：0种,4色：4×3×2×2=48种,5色：5×4×3×3=180种等.变式2：将一个四棱锥的每个顶点染上一种颜色，使同一条棱的两端点异色，如果只有五种颜色可供使用，那么不同的染色方法总数是多少？SABCD例题讲解解1：变式2：将一个四棱锥的每个顶点染上一种颜色，使同一条棱的两端点异色，如果只有五种颜色可供使用，那么不同的染色方法总数是多少？SABCD第1类：顶点A,C同色.顶点P有5种颜色可供选择，顶点A有4种颜色可供选择，顶点B有3种颜色可供选择，此时顶点C与顶点A同色，只有1种颜色可选，顶点D有3种颜色可供选择，不同的涂法5×4×3×1×3=180种.(2)第2类：顶点A,C不同色，顶点P有5种颜色可供选择，顶点A有4种颜色可供选择顶点B有3种颜色可供选择，此时顶点C顶点A不同色，有2种颜色可选，顶点D有2种颜色可供选择，不同的涂法有5×4×3××2=240种..所以不同的染色方法共有180＋240＝420(种).例题讲解解2：变式2：将一个四棱锥的每个顶点染上一种颜色，使同一条棱的两端点异色，如果只有五种颜色可供使用，那么不同的染色方法总数是多少？SABCD从颜色的种数进行分类：若染5种颜色，则不同的染色方法有5×4×3×2×1＝120(种).(2)若染4种颜色，则不同的染色方法有5×4×3×2×2＝240(种).(3)若染3种颜色，则不同的染色方法有5×4×3＝60(种).所以不同的染色方法共有120＋240＋60＝420(种).探究新知(3)对于空间涂色问题，将空间问题平面化，转化为平面区域涂色问题.解决涂色与种植问题的一般思路一般是直接利用两个计数原理求解，常用方法有：(1)按区域的不同，以区域为主分步计数，用分步乘法计数原理求解；(2)以颜色（种植作物）为主分类讨论，适用于“区域、点、线段”问题，用分类加法计数原理求解；课堂练习解：只满足相邻试验田种植不同作物，则从左往右5块试验田分别有3,2,2,2,2种种植方法，不同种植方法数为3×2×2×2×2=48，变式3：将3种作物全部种植在如下图所示的5块试验田里，每块种植1种作物且相邻的试验田不能种植同一种作物，不同的种植方法共有

种（以数字作答）.42而5块试验田只种植了2种作物的种植方法数为3×2×1×1×1=6，所以不同的种植方法数为48-6=42.例题讲解例127名学生中有3名会下象棋但不会下围棋，有2名学生会下围棋但不会下象棋，另2名既会下象棋又会下围棋，现从中选2人分别同时参加象棋比赛和围棋比赛，共有多少种不同的选法？解：分四类，第1类：从3名只会下象棋的学生中选1名参加象棋比赛，同时从2名只会下围棋的学生中选1名参加围棋比赛，由分步乘法计数原理N1＝3×2＝6(种)第2类：从3名只会下象棋的学生中选1名参加象棋比赛，同时从2名既会下象棋又会下围棋的学生中选1名参加围棋比赛，由分步乘法计数原理N2＝3×2＝6(种)．第3类：从2名只会下围棋的学生中选1名参加围棋比赛，同时从2名既会下象棋又会下围棋的学生中选1名参加象棋比赛，由分步乘法计数原理N3＝2×2＝4(种)．第4类：从2名既会下象棋又会下围棋的学生中各选1名参加围棋比赛和象棋比赛，有N4＝2(种)．综上，由分类加法计数原理可知，不同选法共有N＝N1＋N2＋N3＋N4＝6＋6＋4＋2＝18(种)．抽取、分配问题:探究新知2.当涉及对象数目很大时，一般有两种求解方法：3.在计数原理的实际应用中，有些问题涉及到两类元素主次划分，即以主元分步选取次元(或占据次元位置)的计数问题称为占位模型问题．选取问题与分配问题的解法：1.当涉及对象数目不大时，一般用枚举法、树状图法、框图法或图表法求解．(1)直接法：直接使用分类加法计数原理或分步乘法计数原理．(2)间接法：去掉限制条件，计算所有的抽取方法数，然后减去所有不符合条件的抽取方法数选择主元的标准为：(1)该类元素必须“用完”；(2)该类元素分步选取时能够“唯一”表示，次元可随主元多次重复．课堂练习解：展开后共有3×3×5＝45项.1.乘积(a1+a2+a3)(b1+b2+b3)(c1+c2+c3+c4+c5)展开后共有多少项?解：9＋8＋7＋6＋5＋4＋3＋2＋1＝45(个).2.在所有的两位数中，个位数字小于十位数字的有多少个?3.某商场有6个门，如果某人从其中的任意一个门进入商场，并且要求从其他的门出去，那么共有多少种不同的进出商场的方式?解：进出商场的不同方式有6×5＝30(种).4.任意画一条直线，在直线上任取n个分点.(1)从这n个分点中任取2个点形成一条线段，可得到多少条线段?(2)从这n个分点中任取2个点形成一个向量，可得到多少个向量?解：课堂练习练习2运动会有跳高、跑步、游泳三个比赛项目，某班有四名同学报名参赛，要求每名同学只能参加一个项目，不同的报名方式共有（）A.4种B.24种C.43种D.34种

练习1四名同学，争夺三项冠军(每项没有并列冠军)，则冠军获得者可能有的种类是（）A.4B.24C.43D.34

CD练习3现有高一学生9人，高二学生12人，高三学生7人，自发组织数学课外活动小组，从中推选两名来自不同年级的学生做一次活动的主持人，有_____种不同选法.解：推选两名来自不同年级的学生做一次活动主持人，有不同选法：9×12+12×7+9×7=255（种）.课堂练习4.假设今天是4月5日，某市未来六天的空气质量预报情况如下表所示.该市有甲、乙、丙三人计划在未来六天（4月5日~4月10日）内选择一天出游，在①甲只选择空气质量为优的一天出游；②乙不选择4月8日出游；③丙不选择4月5日出游；④甲与乙不选择同一天出游.这四个条件中任选其中三个，求这三人出游的不同方法数.4月5日4月6日4月7日4月8日4月9日4月10日优优优优良良未来六天空气质量预报解:若选择①②③,则三人出游的不同方法数N=4×5×5=100.

若选择①②④,则需分两类，第一类，若甲选择4月8日出游，则三人出游的不同方法数N1=5×6=30;第二类，若甲不选择4月8日出游，则三人出游的不同方法数N2=3×4×6=72..故这三人出游的不同方法数N=N1+N2=102

若选择①③④,则三人出游的不同方法数N=4×5×5=100

若选择②③④,则三人出游的不同方法数N=5×5×5=125.课堂练习5.汽车维修师傅在安装好汽车轮胎后，需要紧固轮胎上的五个螺栓，记为A、B、C、D、E(在正五边形的顶点上）,紧固时需要按一定的顺序固定每一个螺栓，但不能连续固定相邻的两个，则不同固定螺栓顺序的种数为()A.20B.15C.10D.5解:此题相当于在正五边形中，对五个字母排序，要求五边形的任意相邻两个字母不能排在相邻位置，考虑A放第一个位置，第二步只能是C或D,只有ACEBD和ADBEC两种情况；同理，分别让B、C、D、E放第一个位置，则各有两种情况，共2×5=10种情况.C课堂练习6.用红、黄、蓝三种颜色去涂图中标号为1,2,…，9的九宫格中的9个小正方形（如图）,使得任意相邻（有公共边）的小正方形所涂颜色都不相同，且标号为“1,5,9”的小正方形涂相同的颜色，则符合条件的所有涂法有

种.108解:分三步：第一步，先给标号1.5.9的正方形涂色，有3种涂法第二步，给标号2,3.6的小正方形涂色，又分两类：一是标号3与标号1.5.9涂色相同，则标号2.6各有2种涂法，共4种涂法；标号3与标号1.5.9涂色不同，则标号3有2种涂法，此时标号2,6只有1种涂法，种涂法，综上可知，标号2.3.6的小正第三的际法有4+2=6种然跟标号号标号4.7.8的小正方形涂色，显6的小正方形涂色方法一样，根据分步乘法计数原理，符合条件的所有涂法有3×6课堂练习7.如图,用5种不同颜色给图中