6.1 分类加法计数原理与分步乘法计数原理（第2课时）（培优教学课件）数学人教A版选择性必修第三册

6.1分类加法计数原理与分步乘法计数原理 （第2课时） 第六章 计数原理 人教A版选择性必修第三册·高二 章节导读 两个计数原理 排列与组合 二项式定理 分步乘法计数原理 分类加法计数原理 两个计数原理的综合运用 二项式定理 二项式系数的性质 排列 排列数 组合 组合数 两个计数原理的简单运用 学 习 目 标 1 2 3 进一步理解分类加法计数原理和分步乘法计数原 理的区别 能正确应用两个计数原理解决一些实际问题. 能正确理解“完成一件事”的正确含义，能根据事件完成的特征，正确选择“分类”加法、分步乘法进行计算 4 分类加法计数原理 分步乘法计数原理 相同点 不同点 注意点 用来计算“完成一件事”的方法种数 每类方案中的每一种方法都能_____完成这件事 每步_________才算完成这件事情（每步中的每一种方法不能独立完成这件事） 类类独立，不重不漏 步步相依，步骤完整 独立 依次完成 分类完成，类类相加 分步完成，步步相乘 知识回顾 4 新知探究 例4 要从甲、乙、丙3幅不同的画中选出2幅，分别挂在左、右两边墙上的指定位置，问共有多少种不同的挂法? 分析 要完成的一件事是:“从3幅画中选出2幅，并分别挂在左、右两边墙上” 思考 用分类加法计数原理还是用分步乘法计数原理解决呢？ (法一)分步乘法 第1步：选出2幅画(3种：甲乙、甲丙、乙丙) 第2步：对2幅画确定左右(各2种挂法) 不同的挂法种数为3×2=6 (法二)分步乘法 第1步：选1幅挂左边(3种：甲、乙、丙) 第2步：选1幅挂右边(各2种选择) 不同的挂法种数为3×2=6 新知探究 例4 要从甲、乙、丙3幅不同的画中选出2幅，分别挂在左、右两边墙上的指定位置，问共有多少种不同的挂法? (法三)分类加法 第1类：甲在左(2种方法：甲乙、甲丙) 第2类：乙在左(2种方法：乙丙、乙甲) 第3类：丙在左(2种方法：丙甲、丙乙) 不同的挂法种数为2+2+2=6 我们还可用树状图列举出这6种挂法，如右图： 左边 右边 相应的挂法 甲 乙 丙 乙 丙 左甲右乙 左甲右丙 左乙右甲 左乙右丙 左丙右甲 左丙右乙 甲 乙 甲 丙 新知探究 分类加法计数原理和分步乘法计数原理，回答的都是有关做一件事的不同方法种数的问题. 区别在于: 分类加法计数原理针对的是“分类”问题，其中各种方法相互独立，用其中任何一种方法都可以做完这件事，关键词是“分类”； 分步乘法计数原理针对的是“分步”问题，各个步骤中的方法互相依存，只有每一个步骤都完成才算做完这件事，关键词是“分步”. 典例分析 例5 给程序模块命名，需要用3个字符，其中首字符要求用字母A~G或U~Z，后两个要求用数字1 ~9，最多可以给多少个程序命名？ 分析：要完成的一件事是“给一个程序模块命名”.可以分三个步骤完成：第1步,选首字符；第2步,选中间字符;第3步,选最后一个字符．而首字符又可以分为两类． 解: 由分类加法计数原理，首字符不同选法的种数为 7＋6＝13. 后两个字符从1~9中选，因为数字可以重复，所以不同选法的种数都为9. 由分步乘法计数原理，不同名称的个数是 13×9×9＝1053， 即最多可以给1053个程序模块命名. 解2: 首字符用A~G给程序命名的个数为 7×9×9＝567. 首字符用U~Z给程序命名的个数为 6×9×9＝486. ∴总的不同名称的个数是 567＋486＝1053. 思考 你还能给出不同的解法吗? 典例分析 例6 电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态。因此计算机内部就采用了每一位只有0或1两种数字的计数法，即二进制，为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由8个二进制位构成，问 （1）一个字节（8位）最多可以表示多少个不同的字符？ （2）计算机汉字国标码（GB码）包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？ 分析：(1)要完成的一件事是“确定1个字节各二进制位上的数字”．由于每个字节有8个二进制位，每一位上的值都有0，1两种选择而且不同的顺序代表不同的字符，因此可以用分步乘法计数原理求解； (2)只要计算出多少个字节所能表示的不同字符不少于6763个即可． 典例分析 解：(1)用下图表示1个字节，每一格代表一位. 1个字节共有8位，每位上有2种选择．根据分步乘法计数原理，1个字节最多可以表示不同字符的个数是： 2×2×2×2×2×2×2×2＝28＝256. (2)由(1)知，1个字节所能表示的不同字符不够6763个，我们考虑2个字节能够表示多少个字符.前1个字节有256种不同的表示方法，后1个字节也有256种表示方法. 根据分步乘法计数原理，2个字节可以表示不同字符的个数是 256×256=65536 这已经大于汉字国标码包含的汉字个数6763. 因此要对这些汉字进行编码，每个汉字至少要用2个字节表示. 巩固练习 课本P7 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 (个). 巩固练习 课本P7 解1：被5除余2的正整数的个位是2或7. 当满足条件的数是一位数时，满足条件的个数有2个 ； 当满足条件的数是两位数时，满足条件的个数有9×2＝18个 ； 当满足条件的数是三位数时，满足条件的个数有4×10×2＝ 80个 . 所以满足条件的数共有100个. 解2：被5除余2的数可以表示为5k＋2 (k为整数). 由1≤5k＋2≤500，解得0≤k≤99， 满足条件的k值有100个， 所以满足条件的数共有100个. 解：满足条件的三位数有5×5×5＝ 125 个 . 5. 由数字1, 2, 3, 4, 5可以组成多少个三位数(各位上的数字可以重复)? 4. 在1, 2, ‧‧‧, 500中，被5除余2的数共有多少个? 典例分析 例7 计算机编程人员在编写好程序以后需要对程序进行测试. 程序员需要知道到底有多少条执行路径(程序从开始到结束的路线)，以便知道需要提供多少个测试数据. 一般地，一个程序模块由许多子模块组成. 下图是一个具有许多执行路径的程序模块，它有多少条执行路径? 另外，为了减少测试时间，程序员需要设法减少测试次数. 你能帮助程序员设计一个测试方法，以减少测试次数吗? 分析：整个模块的任意一条执行路径都分两步完成: 第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. 在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块，这样，他可以先分别单独测试5个模块，以考察每个子模块的工作是否正常，总共需要的测试次数为：18+45+28+38+43=172. 再测试各个模块之间的信息交流是否正常，只需要测试程序第1步中的各个子模块和第2步中的各个子模块之间的信息交流是否正常，需要的测试次数为：3×2=6. 如果每个子模块都工作正常，并且各个子模块之间的信息交流也正常，那么整个程序模块就工作正常，这样，测试整个模块的次数就变为：172+6=178. 典例分析 显然，178与7371的差距是非常大的. 反思 你看出了程序员是如何实现减少测试次数的吗？ 通过两种测试方案中测试总次数的计算过程不难发现： 第1种测试方案：整体分步测试， 整体使用了分步乘法计数原理计算出总的测试次数； 第2种测试方案：整体分类测试， 整体使用了分类加法计数原理计算出总的测试次数. 典例分析 例8 通常，我国民用汽车号牌的编号由两部分组成：第一部分为用汉字表示的省、自治区、直辖市简称和用英文字母表示的发牌机关代号，第二部分为由阿拉伯数字和英文字母组成的序号，如下图所示． 其中，序号的编码规则为： (1)由 10 个阿拉伯数字和除 O，I 之外的 24 个英文字母组成； (2)最多只能有 2 个英文字母． 　　如果某地级市发牌机关采用 5 位序号编码，那么这个发牌机关最多能发放多少张汽车号牌？ 对于省和自治区,发牌机关通常是指其地级市的公共交通管理部门,并用英文字母依次编码.例如,河北省石家庄市、唐山市的发牌机关代号分别为A,B.直辖市的发牌机关代号可备案后依次自行使用． 典例分析 分析：由号牌编号的组成可知，序号的个数决定了这个发牌机关所能发放的最多号牌数．按序号编码规则可知，每个序号中的数字、字母都是可重复的，并且可将序号分为三类：没有字母，有1个字母，有2个字母．以字母所在位置为分类标准，可将有1个字母的序号分为五个子类，将有2个字母的序号分为十个子类． 解:由号牌编号的组成可知，这个发牌机关所能发放的最多号牌数就是序号的个数.根据序号编码规则，5位序号可以分为三类：没有字母，有1个字母，有2个字母. (1)第1类：当序号中没有字母时，序号的每一位都是数字， 确定一个序号可以分5个步骤，每一步都可以从10个数字中选1个，各有10种选法，根据分步乘法计数原理，这类号牌张数为 10×10×10×10×10=100000 典例分析 (2)第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)第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）需要分类还是需要分步． 　　分类要做到“不重不漏”．分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数． 　　分步要做到“步骤完整”，即完成了所有步骤，恰好完成任务．分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数． 新知感悟 反思 乘法运算是特定条件下加法运算的简化，分步乘法计数原理和分类加法计数原理也有这种类似的关系吗？ (1)有些计数问题既需要进行“分类”，又需要进行“分步”，此时就要注意综合运用两个计数原理来解决问题解决这类问题时，首先要明确是先“分类”后“分步”，还是先“分步”后“分类”；其次，在“分类”和“分步”的过程中，均要有明确的分类标准和分步程序． (2)在既需要分类又需要分步的题目中，可以先根据对题意的理解，合理地画出示意图（如树形图）或列出表格，使问题的实质能直观地表示出来. 巩固练习 课本P11 解：展开后共有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个点形成一个向量，可得到多少个向量? 解： 组数问题 题型一 题型探究 【例1】 从 这10个数字中取出3个数字，试问： (1)能组成多少个没有重复数字的密码？ (2)能组成多少个没有重复数字的三位数？ (3)能组成多少个没有重复数字且是偶数的三位数？ [解析] 从 这10个数字中取出3个数字排成一列， 有 种情况，故能组成720个没有重复数字的密码. [解析] 百位不能为0，有9种选法，十位有9种选法，个位有8种选法， 故能组成 （个）没有重复数字的三位数. [解析] 若个位为0，则有 （种）情况； 若个位不是0，则有 （种）情况， 故能组成没有重复数字且是偶数的三位数的个数为 . 组数问题 题型一 题型探究 【例2】(1) 由1，2，3组成的不多于三位的自然数（可以有重复数字）的个数为( ) D A. 12 B. 27 C. 30 D. 39 [解析] 由1，2，3组成的一位自然数有3个，两位自然数有 个， 三位自然数有个，故共可以组成 个满足题意的自然数. 【例2】(2)回文联是我国对联中的一种，它是用回文形式写成的对联，既可顺读，也可 倒读，不仅意思不变，而且颇具趣味.相传，清代北京城里有一家饭馆叫“天然居”，曾 有一副有名的回文联：“客上天然居，居然天上客；人过大佛寺，寺佛大过人.”在数学 中也有这样一类顺读与倒读都是同一个数的正整数，被称为“回文数”，如22，575， 等,那么由数字1，2，3，4，5可以组成的4位“回文数”的个数为( ) A A. 25 B. 20 C. 30 D. 36 [解析] 1，2，3，4，5组成的4位“回文数”中， 由1个数字组成的4位“回文数”有5个， 由2个数字组成的4位“回文数”有 （个）， 所以由数字1，2，3，4，5可以组成的4位“回文数”的个数为 . 组数问题 题型一 题型探究 解题感悟 组数问题的解题思路 对于组数问题，一般按特殊位置（一般是末位和首位）由谁“占领” 分类，分类中再按特殊位置（或特殊对象）优先的方法分步完成. 抽取、分配问题 题型二 题型探究 【例3】(1)高三年级的四个班到甲、乙、丙、丁、戊五个工厂进行社会实践，每个班 去一个工厂，其中工厂甲必须有班级去，每班去哪个工厂可自由选择，则不同的分配 方案有( ) C A. 360种 B. 420种 C. 369种 D. 396种 [解析] 解法一（直接法）： 以甲工厂分配班级的情况进行分类，共分为四类： 第一类，四个班级都去甲工厂，此时分配方案只有1种； 第二类，有三个班级去甲工厂，剩下的一个班级去另外四个工厂中的一个， 此时分配方案有 （种）； 第三类，有两个班级去甲工厂，另外两个班级分别去另外四个工厂中的一个， 此时分配方案有 （种）； 第四类，有一个班级去甲工厂，其他三个班级分别去另外四个工厂中的一个， 此时分配方案有 （种）. 综上所述，不同的分配方案有 （种）. 抽取、分配问题 题型二 题型探究 解法二（间接法）： 先计算四个班自由选择去工厂的选法总数，再减去甲工厂无人去的情况，即共有 （种）分配方案. 【例3】(1)高三年级的四个班到甲、乙、丙、丁、戊五个工厂进行社会实践，每个班 去一个工厂，其中工厂甲必须有班级去，每班去哪个工厂可自由选择，则不同的分配 方案有( ) C A. 360种 B. 420种 C. 369种 D. 396种 抽取、分配问题 题型二 题型探究 【例3】(2)甲、乙、丙、丁4个人各写1张贺卡，放在一起，再分配给每人1张不是自 己所写的贺卡，共有___种不同的分配方法. 9 [解析] 解法一（列举法）： ①甲分得乙卡，此时乙有甲、丙、丁3种分配方法. 若乙分得甲卡，则丙分得丁卡，丁分得丙卡； 若乙分得丙卡，则丙分得丁卡，丁分得甲卡； 若乙分得丁卡，则丙分得甲卡，丁分得丙卡，故有3种分配方法. ②甲分得丙卡，分配方法按甲、乙、丙、丁4人依次可分得贺卡如下： 丙甲丁乙，丙丁甲乙，丙丁乙甲. ③甲分得丁卡，分配方法按甲、乙、丙、丁4人依次可分得贺卡如下： 丁甲乙丙、丁丙甲乙、丁丙乙甲. 由分类加法计数原理知，共有 （种）不同的分配方法. 抽取、分配问题 题型二 题型探究 【例3】(2)甲、乙、丙、丁4个人各写1张贺卡，放在一起，再分配给每人1张不是自 己所写的贺卡，共有___种不同的分配方法. 9 解法二（间接法）： 4个人各分得1张贺卡.甲先分1张贺卡有4种分法， 乙再分1张贺卡有3种分法，然后丙分1张贺卡有2种分法，最后丁仅有1种分法. 由分步乘法计数原理知，4个人各分1张贺卡共有 （种）分配方法. ①4个人都分配到自己所写的贺卡有1种分法； ②2个人分配到自己所写的贺卡,另2个人分配不到自己所写贺卡的分法有6种(即从4个人中选出分配到自 己所写的贺卡的2人有甲乙、甲丙、甲丁、乙丙、乙丁、丙丁,共6种情况); ③1个人分配到自己所写的贺卡,另3个人分配不到自己所写贺卡的分法有8种(从4个人中选出分配到自己 所写的贺卡的1个人有4种情况,而另3个人都分配不到自己所写的贺卡有2种情况， 根据分步乘法计数原理知，共有 种分法）. 因此，4个人都分配不到自己所写的贺卡的分配方法共有 （种）. 抽取、分配问题 题型二 题型探究 【例3】(2)甲、乙、丙、丁4个人各写1张贺卡，放在一起，再分配给每人1张不是自 己所写的贺卡，共有___种不同的分配方法. 9 解法三（分步法）： 第1步，甲分得1张不是自己所写的贺卡，有3种分法； 第2步，给甲分得的贺卡的供卡人分，有3种分法； 第3步，给剩余两个中任意1个人分，只有1种分法； 第4步，给最后1个人分，只有1种分法. 由分步乘法计数原理知，共有 （种）不同的分配方法. 抽取、分配问题 题型二 题型探究 提分笔记 求解抽取、分配问题的方法 （1）当涉及对象数目不大时，一般选用列举法、树状图法. （2）当涉及对象数目较大时，一般有两种方法：①直接法，直接使用 分类加法计数原理或分步乘法计数原理.②间接法，去掉限制条件，计 算所有的抽取方法数，然后减去所有不符合条件的抽取方法数. 涂色、种植问题 题型三 题型探究 【例4】(1)如图，要给，，， 四个区域分别涂上4种不同颜 色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不 同的颜色，则不同的涂法有____种. 48 [解析] 解法一：按 的顺序分步涂色. 第1步，涂 区域，有4种不同的涂法； 第2步，涂 区域，从剩下的3种颜色中任选一种颜色，有3种不同的涂法； 第3步，涂 区域，从剩下的2种颜色中任选一种颜色，有2种不同的涂法； 第4步，涂区域，可分两类：第1类，区域与 区域同色，有1种涂法， 第2类，区域与区域不同色，有1种涂法，共有 （种）涂法. 根据分步乘法计数原理，共有 （种）不同的涂法. 涂色、种植问题 题型三 题型探究 解法二：按所用颜色的种数分类涂色. 第1类，用3种颜色，有 （种）不同的涂法； 第2类，用4种颜色，有 （种）不同的涂法. 根据分类加法计数原理，共有 （种）不同的涂法. 【例4】(1)如图，要给，，， 四个区域分别涂上4种不同颜 色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不 同的颜色，则不同的涂法有____种. 48 涂色、种植问题 题型三 题型探究 【例4】(2)从黄瓜、白菜、油菜、扁豆4种蔬菜中选出3种，分别种在三块不同土质的 土地上，其中黄瓜必须种植，则有____种不同的种植方法. 18 [解析] 解法一（直接法）： 若黄瓜种在第一块土地上，则有 （种）不同的种植方法. 同理，黄瓜种在第二块、第三块土地上，均有 （种）不同的种植方法. 故不同的种植方法共有 （种）. 解法二（间接法）： 从4种蔬菜中选出3种,种在三块土地上,共有（种）不同的种植方法， 其中不种黄瓜有 （种）不同的种植方法， 故共有 （种）不同的种植方法. 涂色、种植问题 题型三 题型探究 提分笔记 求解涂色、种植问题的常用方法 （1）按区域的不同，分步计数，用分步乘法计数原理分析. （2）以颜色（种植作物）为主分类讨论，适用于“区域、点、线段”问题，用分类加法计数原理分析. 课堂达标 1.由数字0，1，2，3，4可组成无重复数字且是奇数的四位数的个数为( ) B A. 18 B. 36 C. 54 D. 72 [解析] 末位可选1或3，共2种选法， 首位排除0和末位数字后，有3种选法， 中间两位有 （种）选法， 故能组成无重复数字且是奇数的四位数的个数为 . 课堂达标 2.用3种不同的颜色给正三角形的3个顶点涂色，要求每个顶点涂一种颜色，且每条 边的两个端点涂不同颜色，则不同的涂色方法共有( ) A A. 6种 B. 9种 C. 3种 D. 5种 [解析] 三个顶点要涂三种不同的颜色， 则不同的涂色方法共有 （种）. 课堂达标 3.某市人民医院急诊科有3名男医生、3名女医生，内科有5名男医生、4名女医生， 现从该医院急诊科和内科各选派1名男医生和1名女医生组成一个4人小组参加省人 民医院组织的交流会，则不同的选派方案有( ) A A. 180种 B. 56种 C. 29种 D. 15种 [解析] 从急诊科选派1名男医生和1名女医生有 （种）方案， 从内科选派1名男医生和1名女医生有 （种）方案， 根据分步乘法计数原理知，该医院共有 （种）不同的选派方案. 课堂达标 4.如图，用4种不同的颜色涂所给图形中的4个区域，要求相邻区域的颜色不能相同， 则不同的涂色方法有____种. 84 [解析] 根据题意，分2种情况讨论： 若区域4和区域2涂不同颜色，则区域4有4种涂色方法，区域2有3种涂色方法， 区域1有2种涂色方法，区域3有2种涂色方法， 共有 （种）涂色方法； 若区域4和区域2涂相同颜色，则区域4有4种涂色方法，区域3有3种涂色方法， 区域1有3种涂色方法，共有 （种）涂色方法. 故共有 （种）不同的涂色方法. 课堂小结 感谢聆听! $