分类加法计数原理与分步乘法计数原理（3）课件高二下学期数学人教A版选择性

6.1分类加法计数原理与分步乘法计数原理

(3)例1：

计算机编程人员在编写好程序以后需要对程序进行测试.程序员需要知道到底有多少条执行路径(程序从开始到结束的路线)，以便知道需要提供多少个测试数据.一般地，一个程序模块由许多子模块组成.下图是一个具有许多执行路径的程序模块，它有多少条执行路径?另外，为了减少测试时间，程序员需要设法减少测试次数.你能帮助程序员设计一个测试方法，以减少测试次数吗?例题课本P8分析：整个模块的任意一条执行路径都分两步完成：第1步是从开始执行到A点；第2是从A点执行到结束.而第1步可由子模块1、子模块2、子模块3中任何一个来完成；第2步可由子模块4、子模块5中任何一个来完成.因此，分析一条指令在整个的模块执行路径需要用到两个计数原理.解：由分类加法计数原理，子模块1、子模块2、子模块3中的子路径条数共为

18+45+28=91；子模块4、子模块5中的子路径条数共

38+43=81.又由分步乘法计数原理，整个模块的执行路径条数共为

91×81=7371.再测试各个模块之间的信息交流是否正常，只需要测试程序第1步中的各个子模块和第2步中的各个子模块之间的信息交流是否正常，需要的测试次数为3×2=6.如果每个子模块都工作正常，并且各个子模块之间的信息交流也正常，那么整个程序模块就工作正常，这样，测试整个模块的次数就变为172+6=178.显然，178与7371的差距是非常大的.在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块，这样，他可以先分别单独测试5个模块，以考察每个子模块的工作是否正常，总共需要的测试次数为18+45+28+38+43=172.你看出了程序员是如何实现减少测试次数的吗？？解：根据多项式乘法法则，要得到展开式的项数，可以分3步完成：第1步，从第一个因式中任取一项，有3种方法；第2步，从第2个因式中任取一项，有3种方法；第3步，从第3个因式中任取一项，有5种方法．根据分步乘法计数原理，展开后共有的项数为N＝3×3×5＝45.1.乘积(a1+a2+a3)(b1+b2+b3)(c1+c2+c3+c4+c5)展开后共有多少项?课本P11练习2.某商场有6个门，如果某人从其中的任意一个门进人商场，并且要求从其他的门出去，那么共有多少种不同的进出商场的方式?解：要完成这件事，可以分2步完成：先从6个门中选一个进入，再从其余5个门中选一个出去，故共有6×5＝30种不同的进出商场的方式．课本P11例2：通常，我国民用汽车号牌的编号由两部分组成:第一部分为用汉字表示的省、自治区、直辖市简称和用英文字母表示的发牌机关代号，第二部分为由阿拉伯数字和英文字母组成的序号，如图所示.其中，序号的编码规则为:(1)由10个阿拉伯数字和除O，I之外的24个英文字母组成；(2)最多只能有2个英文字母.如果某地级市发牌机关采用5位序号编码，那么这个发牌机关最多能发放多少张汽车号牌?例题0冀AJR005省、自治区、直辖市简称发牌机关代号序号课本P9分析：由号牌编号的组成可知:序号的个数决定了发牌机所能发放的最多号牌数.按序号编码规则可知，每个序号中的数字、字母都是可重复的，并且可将序号分为三类：没有字母，有1个字母，有2个字母.以字母所在位置为分类标准，可将有1个字母的序号分为五个子类，将有2个字母的序号分为十个子类.0冀AJR005省、自治区、直辖市简称发牌机关代号序号解:由号牌编号的组成可知，这个发牌机关所能发放的最多号牌数就是序号的个数.根据序号编码规则，5位序号可以分为三类：没有字母，有1个字母，有2个字母.(1)当没有字母时，序号的每一位都是数字，确定一个序号可以分5个步骤，每一步都可以从10个数字中选1个，各有10种选法，根据分步乘法计数原理，这类号牌张数为10×10×10×10×10=100000.(2)当有1个字母时，这个字母可以分别在序号的第1位、第2位、第3位、第4位或第5位，这类序号可以分为五个子类.当第1位是字母时,分5个步骤确定一个序号中的字母和数字:第1步,从24个字母中选1个放在第1位,有24种选法;第2～5步都是从10个数字中选1个放在相应的位置,各有10种选法,根据分步乘法计数原理,号牌张数为24×10×10×10×10=240000.同样，其余四个子类号牌也各有240000张.根据分类加法计数原理，这类号牌张数一共为

240000+240000+240000+240000+240000=1200000.(3)当有2个字母时，根据这2个字母在序号中的位置，可以将这类序号分为十个子类：第1位和第2位，第1位和第3位，第1位和第4位，第1位和第5位，第2位和第3位，第2位和第4位，第2位和第5位，第3位和第4位，第3位和第5位，第4位和第5位.当第1位和第2位是字母时，分5个步骤确定一个序号中的字母和数字：第1,2步都是从24个字母中选1个分别放在第1位、第2位，各有24种选法；第3~5步都是从10个数字中选1个放在相应的位置，各有10种选法，根据分步乘法计数原理，号牌张数为

24×24×10×10×10=576000.同样，其余九个子类号牌也各有576000张.于是，这类号牌张数一共为

576000×10=5760000.综合(1)(2)(3),根据分类加法计数原理，这个发牌机关最多能发放的汽车号牌张数为

100000+1200000+5760000=7060000.思考：乘法运算是特定条件下加法运算的简化，分步乘法计数原理和分类加法计数原理也有这种类似的关系吗？(1)有些计数问题既需要进行“分类”，又需要进行“分步”，此时就要注意综合运用两个计数原理来解决问题.解决这类问题时，首先要明确是先“分类”后“分步”，还是先“分步”后“分类”；其次，在“分类”和“分步”的过程中，均要有明确的分类标准和分步程序．(2)在既需要分类又需要分步的题目中，可以先根据对题意的理解，合理地画出示意图（如树形图）或列出表格，使问题的实质能直观地表示出来.任意画一条直线，在直线上任取n个分点.(1)从这n个分点中任取2个点形成一条线段，可得到多少条线段?课本P11练习任意画一条直线，在直线上任取n个分点.(2)从这n个分点中任取2个点形成一个向量，可得到多少个向量?课本P11例3：用0、1、2、3、4这5个数字可组成多少个无重复数字的：（1）四位数？例题分析：完成“组成无重复数字的四位数”这件事需要分4步，我们将完成这件事用图表示出来：千位百位十位个位其中的“千位”能不能取“0”？

.“0”是特殊元素，“千位”是特殊位置，特殊元素特殊位置要优先考虑.不能解：完成“组成无重复数字的四位数”这件事需要分4步：千位百位十位个位第1步,安排千位有

种选择；

种44

种

种

种第2步,安排百位有

种选择；44第3步,安排十位有

种选择；33第4步,安排个位有

种选择.22根据分步乘法计数原理，一共有

种方法.4×4×3×2=96例3：用0、1、2、3、4这5个数字可组成多少个无重复数字的：（2）四位奇数？千位百位十位个位分析：完成“组成无重复数字的四位奇数”这件事，既要注意“千位”不能取“0”，还要注意“个位”只能取数字

，因此，完成这件事可以分两类.1，3特殊元素特殊位置要优先考虑.解法1：完成“组成无重复数字的四位奇数”这件事可以分两类：千位百位十位个位第1类,个位数字是1，则安排千位有

种选择，

种33

种

种

种安排百位有

种选择，33安排十位有

种选择.221根据分步乘法计数原理，一共有

种方法.3×3×2=18第2类,个位数字是3，同理一共有

种方法.3×3×2=18根据分类加法计数原理，总共有

种方法.18＋18=36解法2：完成“组成无重复数字的奇四位数”这件事需要分4步：千位百位十位个位第1步,安排个位有

种选择，

种23

种

种

种第2步,安排千位有

种选择；33第3步,安排百位有

种选择；23第4步,安排十位有

种选择.22根据分步乘法计数原理，一共有

种方法.2×3×3×2=36即1或3；练习解：要确定所有的两位数中，个位数字小于十位数字的个数，可以分类完成：第1类，十位数字为1，有1个；第2类，十位数字为2，有2个；第3类，十位数字为3，有3个；第4类，十位数字为4，有4个；第5类，十位数字为5，有5个；第6类，十位数字为6，有6个；第7类，十位数字为7，有7个；第8类，十位数字为8，有8个；第9类，十位数字为9，有9个．根据分类加法计数原理，这样的两位数的个数为1＋2＋3＋4＋5＋6＋7＋8＋9＝45．2.在所有的两位数中，个位数字小于十位数字的有多少个?课本P11例4：如图所示，要给“创”、“新”、“设”、“计”四个区域分别涂上3种不同颜色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不同的颜色，有多少种不同的涂色方法？解：“创”、“新”、“设”、“计”四个区域依次涂色，分四步.第1步，涂“创”区域，有3种选择；第2步，涂“新”区域，有2种选择；第3步，涂“设”区域，由于它与“创”、“新”区域颜色不同，有1种选择；例题解：“创”、“新”、“设”、“计”四个区域依次涂色，分四步.第1步，涂“创”区域，有3种选择；第2步，涂“新”区域，有2种选择；第3步，涂“设”区域，由于它与“创”、“新”区域颜色不同，有1种选择；第4步，涂“计”区域，由于它与“创”“设”区域颜色不同，有1种选择.所以根据分步乘法计数原理，得不同的涂色方法共有3×2×1×1＝6(种).求解涂色(种植)问题一般是直接利用两个计数原理求解，常用方法有：(1)按区域的不同以区域为主分步计数，用分步乘法计数原理分析；(2)以颜色(种植作物)为主分类讨论，适用于“区域、点、线段”问题，用分类加法计数原理分析；(3)对于涂色(立方体)问题将空间问题平面化，转化为平面区域涂色问题.反思归纳1.长方形的两条对角线把长方形分成四部分，如图用五种不同的颜色给这四部分涂色，每一部分涂一种颜色，任何相邻（具有公共边）的两部分涂不同颜色，问有多少种不同的涂色方法？ABCD解：若A,C同色，则不同的涂色方法有5×4×4＝80(种).(2)若A,C不同色，则不同的涂色方法有5×4×3×3＝180(种).综上所述，由分类加法计数原理得：共有80＋180＝260(种).练习2.如图所示，一环形花坛分成A，B，C，D四块，现有四种不同的花供选种，要求在每块里种一种花，且相邻的两块种不同的花，则不同的种法种数为(

)A.96 B.84 C.60 D.48解析：依次种A，B，C，D4块，当C与A种同一种花时，有4×3×1×3＝36(种)种法；当C与A所种的花不同时，有4×3×2×2＝48(种)种法.由分类加法计数原理知，不同的种法种数为36＋48＝84.1.某市汽车牌照号码可以上网自编，但规定从左数第2个号码只能从字母B，C，D中选择，其他四个号码可以从0～9这10个数字中选择(数字可以重复).若某车主第1个号码(从左到右)只想在数字3,5,6,8,9中选择，其他号码只想在1,3,6,9中选择，则他可选的车牌号码的所有可能情况有（

）A.180种 B.360种

C.720种D.960种解析：按照车主的要求，从左到右第1个号码有5种选法，第2个号码有3种选法，其余3个号码各有4种选法，因此共有5×3×4×4×4＝960(种)情况.随堂检测2.从6名志愿者中选4人分别从事翻译、导游、导购、保洁四项不同的工作，若其中甲、乙2名志愿者不能从事翻译工作，则选派方案共有（

）A.280种 B.240种

C.180种 D.96种解析：由于甲、乙不能从事翻译工作，因此翻译工作从余下的4名志愿者中选1人，有4种选法.后面三项工作的选法有5×4×3种，因此共有4×5×4×3＝240(种)选派方案.解：(1)由分步计数原理得，所求三位数共有5×5×4＝100个．3.用0,1,2,3,4,5这6个数字：(1)可以组成______个数字不重复的三位数;(2)可以组成______个数字允许重复的三位数;(3)可以组成______个大于3000，小于5421的数字不重复的四位数．(2)由分步计数原理得，所求三位数共有5×6×6＝180个．3.用0,1,2,3,4,5这6个数字：(3)可以组成______个大于3000，小于5421的数字不重复的四位数．解：分四类：

①千位数字为3,4之一时，有2×5×4×3=120个；②千位数字为5，百位数字为0,1,2,3之一时，有4×4×3=48个；

③千位数字是5百位数字是4，十位数字是0,1之一时，有2×3=6个；

④千位数字是5百位数字是4，十位数字是2时，有1个；所以所求四位数共有120+48+6+1=175个．解法1：4.将一个四棱锥的每个顶点染上一种颜色，使同一条棱的两端点异色，如果只有五种颜色可供使用，那么不同的染色方法总数是多少？SABCD若A,C同色，则不同的染色方法有5×4×3×3＝180(种).(2)若A,C不同色，则不同的染色方法有5×4×3×2×2＝240(种).所以不同的染色方法共有180＋240＝420(种).SABCD解法2：从颜色的种数进行分类：若染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(种).4.将一个四棱锥的每个顶点染上一种颜色，使同一条棱的两端点异色，如果只有五种颜色可供使用，那么不同的染色方法总数是多少？5.现有高一四个班学生34个，其中一、二、三、四班各7人、8人、9人、10人，他们自愿组成数学课外小组．(1)选其中一人为负责人，有多少种不同的选法？(2)每班选一名组长，有多少种不同的选法？(3)推选二人作中心发言，这二人需来自不同的班级，有多少种不同的选法？解：

(1)分四类，第一类，从一班学生中选1人，有7种选法；第二类，从二班学生中选1人，有8种选法；第三类，从三班学生中选1人，有9种选法；第四类，从四班学生中选1人