第一节分类加法计数原理与分步乘法计数原理

第一章计数原理第一节分类加法计数原理与分步乘法计数原理1.分类加法计数原理完成一件事有两类不同方案，在第1类方案中有m种不同的方法，在第2类方案中有n种不同的方法.那么完成这件事共有nmN种不同的方法.例1.在填写高考志愿表时，一名高中毕业生了解到，A,B两所大学各有一些自己感兴趣的强项专业，具体情况如下：A大学B大学生物学数学化学会计学医学信息技术学物理学法学工程学如果这名同学只能选一个专业，那么他共有多少种选择呢？分析：由于这名同学在A,B两所大学中只能选择一所，而且只能选择一个专业，又由于两所大学没有共同的强项专业，因此符合分类加法计数原理的条件．解：这名同学可以选择A,B两所大学中的一所．在A大学中有5种专业选择方法，在B大学中有4种专业选择方法．又由于没有一个强项专业是两所大学共有的，因此根据分类加法计数原理，这名同学可能的专业选择共有5+4=9（种）.一般归纳：完成一件事情，有n类办法，在第1类办法中有1m种不同的方法，在第2类办法中有2m种不同的方法……在第n类办法中有nm种不同的方法.那么完成这件事共有nmmmN21种不同的方法.理解分类加法计数原理：分类加法计数原理针对的是“分类”问题，完成一件事要分为若干类，各类的方法相互独立，各类中的各种方法也相对独立，用任何一类中的任何一种方法都可以单独完成这件事.2.分步乘法计数原理完成一件事有两类不同方案，在第1类方案中有m种不同的方法，在第2类方案中有n种不同的方法.那么完成这件事共有nmN种不同的方法.例2.设某班有男生30名，女生24名.现要从中选出男、女生各一名代表班级参加比赛，共有多少种不同的选法？分析：选出一组参赛代表，可以分两个步骤．第l步选男生．第2步选女生．解：第1步，从30名男生中选出1人，有30种不同选择；第2步，从24名女生中选出1人，有24种不同选择．根据分步乘法计数原理，共有30×24=720种不同的选法．一般归纳：完成一件事情，需要分成n个步骤，做第1步有1m种不同的方法，做第2步有2m种不同的方法……做第n步有nm种不同的方法.那么完成这件事共有nmmmN21种不同的方法.理解分步乘法计数原理：分步计数原理针对的是“分步”问题，完成一件事要分为若干步，各个步骤相互依存，完成任何其中的一步都不能完成该件事，只有当各个步骤都完成后，才算完成这件事.3．理解分类加法计数原理与分步乘法计数原理异同点①相同点：都是完成一件事的不同方法种数的问题②不同点：分类加法计数原理针对的是“分类”问题，完成一件事要分为若干类，各类的方法相互独立，各类中的各种方法也相对独立，用任何一类中的任何一种方法都可以单独完成这件事，是独立完成；而分步乘法计数原理针对的是“分步”问题，完成一件事要分为若干步，各个步骤相互依存，完成任何其中的一步都不能完成该件事，只有当各个步骤都完成后，才算完成这件事，是合作完成.4.综合应用例3.书架的第1层放有4本不同的计算机书，第2层放有3本不同的文艺书，第3层放2本不同的体育书.①从书架上任取1本书，有多少种不同的取法？②从书架的第1、2、3层各取1本书，有多少种不同的取法？③从书架上任取两本不同学科的书，有多少种不同的取法？【分析】①要完成的事是“取一本书”，由于不论取书架的哪一层的书都可以完成了这件事，因此是分类问题，应用分类计数原理.②要完成的事是“从书架的第1、2、3层中各取一本书”，由于取一层中的一本书都只完成了这件事的一部分，只有第1、2、3层都取后，才能完成这件事，因此是分步问题，应用分步计数原理.③要完成的事是“取2本不同学科的书”，先要考虑的是取哪两个学科的书，如取计算机和文艺书各1本，再要考虑取1本计算机书或取1本文艺书都只完成了这件事的一部分，应用分步计数原理，上述每一种选法都完成后，这件事才能完成，因此这些选法的种数之间还应运用分类计数原理.解：(1)从书架上任取1本书，有3类方法：第1类方法是从第1层取1本计算机书，有4种方法；第2类方法是从第2层取1本文艺书，有3种方法；第3类方法是从第3层取1本体育书，有2种方法．根据分类加法计数原理，不同取法的种数是123Nmmm=4+3+2=9;(2）从书架的第1,2,3层各取1本书，可以分成3个步骤完成：第1步从第1层取1本计算机书，有4种方法；第2步从第2层取1本文艺书，有3种方法；第3步从第3层取1本体育书，有2种方法．根据分步乘法计数原理，不同取法的种数是123Nmmm=4×3×2=24.（3）26232434N。例4.要从甲、乙、丙3幅不同的画中选出2幅，分别挂在左、右两边墙上的指定位置，问共有多少种不同的挂法？解：从3幅画中选出2幅分别挂在左、右两边墙上，可以分两个步骤完成：第1步，从3幅画中选1幅挂在左边墙上，有3种选法；第2步，从剩下的2幅画中选1幅挂在右边墙上，有2种选法．根据分步乘法计数原理，不同挂法的种数是N=3×2=6.6种挂法可以表示如下：分类加法计数原理和分步乘法计数原理，回答的都是有关做一件事的不同方法的种数问题．区别在于：分类加法计数原理针对的是“分类”问题，其中各种方法相互独立，用其中任何一种方法都可以做完这件事，分步乘法计数原理针对的是“分步”问题，各个步骤中的方法互相依存，只有各个步骤都完成才算做完这件事．例5.给程序模块命名，需要用3个字符，其中首字符要求用字母A～G或U～Z,后两个要求用数字1～9．问最多可以给多少个程序命名？分析：要给一个程序模块命名，可以分三个步骤：第1步，选首字符；第2步，选中间字符；第3步，选最后一个字符．而首字符又可以分为两类．解：先计算首字符的选法．由分类加法计数原理，首字符共有7+6=13种选法．再计算可能的不同程序名称．由分步乘法计数原理，最多可以有13×9×9==1053个不同的名称，即最多可以给1053个程序命名．一、如何正确的理解两个原理呢？⑴分类计数原理：该原理是对涉及完成某一件事的不同类方法种数的计数方法，每一种方法都可以完成这件事；每一类的各种方法都是相互独立的。⑵分步计数原理：该原理是对涉及完成某一件事的各个步骤不同种方法的计数方法，完成一件事有n个步骤，各个步骤相互依存，一个步骤的任何一种方法都不能独立完成这件事；完成这件事的每一中方法都应视为有n个步骤。⑶两个基本原理都是涉及完成一件事的不同方法种数的计数方法，它们的区别在于：分类计数原理与“分类”有关，各种方法相互独立，用任何一种方法都可以完成这件事；分步计数原理与“分布”有关，各个步骤是相互依存的，只有各个步骤都完成了，这件事才算完成。二、如何选用分类计数原理与分布计数原理呢？在处理应用问题时，必须先分清是“分类”还是“分布”，确切的说，要根据元素的不同性质进行“分类”，首先要根据问题的特点，确定分类的标准，分类应满足：完成一件事的任何一种方法，必属于某一类而仅属于某一类，即：“类”与“类”间的确定性与并列性；根据事件发生的过程进行“分布”时，要确定好分布的标准，必须满足：完成一件事必须且只需连续完成这几步，即：各个步骤是相互依存的，各个步骤都完成了，这件事才算完成，注意“步”与“步”的连续性；然后根据两个计数原理去计算。解题方法与技巧：1、分类计数原理的应用：例1、在所有的两位数中，个位数字大于十位数字的两位数有多少个？解：根据题意，将十位数上的数字分别是1，2，3，4，5，6，7，8的情况分成8类，在每一类中满足题目条件的两位数分别是8个，7个，6个，5个，4个，3个，2个，1个。由分类计数原理可知：符合题意的两位数的个数共有8+7+6+5+4+3+2+1=36个答：这样的两位数共有36个。评注：解决具体问题时，如何分类或分布，开始学习时可能会遇到一点困难，因此需要不断学习中注意积累经验，掌握思维方法，逐步就会做到恰当分类，合理分布；请同学们思考，你能换一种分类方法给出另外的解法吗？2、分布计数原理的应用：例2、现要排一份5天的值班表，每天有一个人值班，共有5个人，每个人都可以值多天班或不值班，但相邻两天不准由同一个人值班，问此值班表共有多少种不同的排法？分析：该问题是计数问题，完成的一件事是排值日表，因而需一天一天地排，用分步计数原理，分步进行，理清思路，按事件发生的过程合理分步；。解：先排第一天，可排5人中的任一人，有5种排法；再排第二天，此时不能排第一天已排的人，有4种排法，；在排第三天，此时不能第二天已排的人，仍有4种排法；同理，第四，第五天均有4种排法，由分步计数原理可得值班表共有不同的排法数为：544441280种。答：值班表共有1280种不同的排法；3、两个计数原理的综合应用：两个原理一起应用时，要明确是先分类还是先分步，应用时，应目的明确，层次分明，先后有序。例3、某外语组有9人，每人至少会英语和日语中的一门，其中7人会英语，3人会日语，从中选出会英语和日语的各一人，有多少种不同的选法；分析：由题意知有1人既会英语又会日语，在选择2个人时，可根据只会英语的人进行分类完成；解：有题意得有1人既会英语又会日语，6人只会英语，2人只回日语第一类：从只会英语的6人中选1人说英语，共有6种方法；则说日语的有213种；此时共有6318种；第二类：不从只会英语的6人中选1人说英语，则只有1种方法；此时选会日语的有2种；此时共有122中；所以有分类计数原理知共有18+2=20种选法；例4、同室四人各写一张贺卡，先集中起来，然后每人从中拿一张别人送出的贺卡，在四张贺卡的不同分配方式有多少中？解法1：第一步：四个人中的任意一人（例如A）先取一张，则由题意知共有3种取法；第二步：由第一人取走的贺卡的供卡人取，也有3种取法；第三步：由剩余的两人中的任一人取，只有一种取法；第四步：最后一人取，只有一种取法。有分步记述原理，共有33119种方法。解法2：设四张贺卡分别记为A、B、C、D，由题意，某人（不妨设A卡的供卡人）取卡的情况有3种，据此将卡的不同分配方式分为三类，对于每一类，其他人依次取卡分步进行，为了避免重复或遗漏现象，我们用“树图”表示如下：+所以：共有9种不同的分配方式；典例分析１．明确题目要完成什么事情，如何去完成例1甲同学有若干本课外参考书，其中有5本不同的数学书，4本不同的物理书，3本不同的化学书，现在乙同学向甲同学借书．（1）若借一本书，则有多少种不同的借法？（2）若每科各借一本，则有多少种不同的借法？（3）若借两本不同学科的书，则有多少种不同的借法？解：（1）因为需完成的事情是“借一本”书，所以借给他数学、物理、化学书中的任何一本，都可以完成这件事情．故用分类加法计数原理，共有5+4+3=12种不同的借法；（2）需完成的事情是“每科各借一本”书，意味着要借给乙3本书，只有从数学、物理、化学三科中各借一本，才能完成这件事情，故用分步乘法计数原理，共有5×4×3=60种不同的借法；（3）需完成的事情是“从三种学科的书中借两本不同学科的书”，要分三种情况：①借一本数学书和一本物理书，只有两本书都借，事情才能完成，由分步计数原理，知有5×4=20种借法；BA—D—CC—D—AD—A—CCA—D—BD—B—AD—A—BDA—B—CC—A—BC—B—A②借一本数学书和一本化学书，同理由分步乘法计数原理，知有5×3=15种借法；③借一本物理书和一本化学书，同理由分步计数原理，知有4×3=12种借法．而上述的每一种借法都可以独立完成这件事情，由分类计数原理，知共有20+15+12=47种不同的借法．2．“类与类”之间相互独立且并列，分类过程不重不漏例2用4种不同的颜色对右图中5个区域涂色（4种颜色全部使用），每个区域涂一种颜色，相邻的区域不能同色，则共有多少种不同的涂色方法？解：由题意知，必有两个区域涂相同的颜色，从图形的形状可知1与3；1与5；2与5；3与5的区域可涂相同的颜色．这样可将问题分成四类，每一类均有4×3×2×1=24种涂色方法．所以共有4×24=96种涂色方法．3．“步与步”之间相依且连续，但不能交