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

分类加法计数原理:完成一件事有两类不同方案,在第1类方案中有m种不同的方法,在第2类方案中有n种不同的方法,那么完成这件事共有N＝m＋n(种)不同方法．

分步乘法计数原理:完成一件事需要两个步骤,在第1个步骤中有m种不同的方法,在第2个步骤中有n种不同的方法,那么完成这件事共有N＝m×n(种)不同的方法．

方法简述

1．基本定义法

例1　在填写高考志愿表时,一名高中毕业生了解到,A,B两所大学各有一些自己感兴趣的强项专业,具体情况如下:

如果这名同学只能选一个专业,那么他共有多少种选择呢?

点拨　由于这名同学在A,B两所大学中只能选择一所,而且只能选择一个专业,又由于两所大学没有共同的强项专业,因此符合分类加法计数原理的条件．

解答　这名同学可以选择A,B两所大学中的一所．在A大学中有5种专业选择方法,在B大学中有4种专业选择方法．又由于没有一个强项专业是两所大学共有的,因此根据分类加法计数原理,这名同学可能的专业选择共有5＋4＝9(种)．

反思　加法原理的基本应用．

例2答图

例2　一只蚂蚁沿着长方体的棱,从一个顶点爬到相对的另一个顶点的最近路线共有多少条?

点拨　要分整体与局部考虑．

解答　如图所示,从总体上看,蚂蚁从顶点A爬到顶点C1有三类方法,从局部上看每类又需两步完成,所以,第一类,m1＝1×2＝2(条);第二类,m2＝1×2＝2(条);第三类,m3＝1×2＝2(条)．所以,根据加法原理,从顶点A到顶点C1最近路线共有N＝2＋2＋2＝6(条)．

反思　不需要求所有的最近线路．

例3　设某班有男生30名,女生24名．现要从中选出男、女生各一名代表班级参加比赛,共有多少种不同的选法?

点拨　选出一组参赛代表,可以分两个步骤．第1步选男生,第2步选女生．

解答　第1步,从30名男生中选出1人,有30种不同选择;

第2步,从24名女生中选出1人,有24种不同选择．

根据分步乘法计数原理,共有30×24＝720(种)不同的选法．

反思　乘法原理基本应用．

例4图

例4　如图所示,要给地图A,B,C,D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种?

点拨　可以先确定A区域的涂色,进而完成所有涂色．

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

第一步:m1＝3种;第二步:m2＝2种;

第三步:m3＝1种;第四步:m4＝1种．

所以根据乘法原理,得到不同的涂色方案种数共有N＝3×2×1×1＝6(种)．

反思　注意相邻区域颜色不同的选择．

2．列举法

例5　求三边长均为整数,且最大边长为11的三角形的个数．

点拨　该问题与计数有关,故考虑选用两个基本原理来解决,完成这件事,应注意最大边长为11,且两边之和大于第三边,因此可考虑对边长进行分类讨论．

解答　设较小的两边长为x,y且x≤y,

则

当x＝1时,y＝11;

当x＝2时,y＝10,11;

当x＝3时,y＝9,10,11;

当x＝4时,y＝8,9,10,11;

当x＝5时,y＝7,8,9,10,11;

当x＝6时,y＝6,7,8,9,10,11;

当x＝7时,y＝7,8,9,10,11;

…

当x＝11时,y＝11．

所以不同三角形的个数有1＋2＋3＋4＋5＋6＋5＋4＋3＋2＋1＝36(个)．

反思　分类加法计数原理是涉及完成一件事情的不同方法的计数种类,第一类中的各种方法都是相互独立的,且第一类方法中的每一种方法都可以独立地完成这件事．解决这类问题应从简单的分类入手进行讨论,做到不重不漏,尽可能做到一题多解,从不同的角度进行思考问题．

例6　书架的第1层放有4本不同的计算机书,第2层放有3本不同的文艺书,第3层放有2本不同的体育书．

(1)从书架上任取1本书,有多少种不同的取法?

(2)从书架的第1,2,3层各取1本书,有多少种不同的取法?

(3)从书架上任取两本不同学科的书,有多少种不同的取法?(www.xing528.com)

点拨　(1)要完成的事是“取一本书”,由于不论取书架的哪一层的书都可以完成了这件事,因此是分类问题,应用分类加法计数原理．

(2)要完成的事是“从书架的第1,2,3层中各取一本书”,由于取一层中的一本书都只完成了这件事的一部分,只有第1,2,3层都取后,才能完成这件事,因此是分步问题,应用分步乘法计数原理．

(3)要完成的事是“取2本不同学科的书”,先要考虑的是取哪两个学科的书,如取计算机和文艺书各1本,再要考虑取1本计算机书或取1本文艺书都只完成了这件事的一部分,应用分步乘法计数原理．上述每一种选法都完成后,这件事才能完成,因此这些选法的种数之间还应运用分类加法计数原理．

解答　(1)从书架上任取1本书,有3类方法:第1类方法是从第1层取1本计算机书,有4种方法;第2类方法是从第2层取1本文艺书,有3种方法;第3类方法是从第3层取1本体育书,有2种方法．根据分类加法计数原理,不同取法的种数是

N＝m1＋m2＋m3＝4＋3＋2＝9(种)．

(2)从书架的第1,2,3层各取1本书,可以分成3个步骤完成:第1步从第1层取1本计算机书,有4种方法;第2步从第2层取1本文艺书,有3种方法;第3步从第3层取1本体育书,有2种方法．根据分步乘法计数原理,不同取法的种数是

N＝m1×m2×m3＝4×3×2＝24(种)．

(3)N＝4×3＋4×2＋3×2＝26(种)．

反思　分步计数与分类计数考虑必须全面．

例7图

易错解读

例7　某城市在中心广场建造一个花圃,花圃分为6个部分(如图所示)．现要栽种4种不同颜色的花,每部分栽种一种且相邻部分不能栽种同样颜色的花,不同的栽种方法有多少种?

解答　从题意来看6部分种4种颜色的花,又从图形看知必有2组同颜色的花,从同颜色的花入手分类求解．

(1)②与⑤同色,则③⑥同色或④⑥同色,所以共有N1＝4×3×2×2×1＝48(种);

(2)③与⑤同色,则②④或⑥④同色,所以共有N2＝4×3×2×2×1＝48(种);

(3)②与④且③与⑥同色,则共有N3＝4×3×2×1＝24(种)．

所以,共有N＝N1＋N2＋N3＝48＋48＋24＝120(种)．

易错点　由于6部分栽种4种颜色不同的花,故必有两部分或两部分以上的区域种同种颜色的花,因此从同颜色的花进行分类,讨论不能遗漏．

例8　用0,1,2,3,4,5这六个数字,

(1)可以组成多少个不能有重复数字的三位数?

(2)可以组成多少个允许重复的三位数?

(3)可以组成多少个不重复的三位奇数?

(4)可以组成多少个数字不重复且小于1000的自然数?

(5)可以组成多少个数字不重复的大于3000小于5421的四位数?

解答　(1)分三步:①先选百位数字,由于0不能作为百位数,因此有5种不同的选法;②十位数字有5种选法;③个位数字有4种不同的选法．由分步乘法计数原理知,所求的三位数共有5×5×4＝100(个)．

(2)分三步:①先选百位数字,由于0不能作为百位数字,因此有5种不同的选法;②十位数字有6种不同的选法;③个位数字有6种不同的选法．由分步乘法计原理可知,所求的三位数共有5×6×6＝180(个)．

(3)分三步:①先选个位数字,由于组成的三位数是奇数,因此有3种不同的选法;②再选百位数字有4种选法;③十位数字也有4种选法．由分步乘法计数原理知,所求的三位数3×4×4＝48(个)．

(4)分三类:①一位数,共有6个;②两位数,共有5×5＝25(个);③三位数,共有5×5×4＝100(个)．因此,由分类加法计数原理知,所求自然数共有6＋25＋100＝131(个)．

(5)分四类:①千位数为3,4之一时,共有2×5×4×3＝120(个);②千位数字为5,百位数字为0,1,2,3之一时,共有4×4×3＝48(个);③千位数字为5,百位数字为4,十位数字为0,1之一时,共有2×3＝6(个);④还有5420也满足条件,此时有1个．故所求的自然数共有120＋48＋6＋1＝175(个)．

易错点　限制条件优先考虑,0不能作为数字的首位．

经典训练

1．某班有男生26人,女生24人,从中选一位同学为数学课代表,则不同的选法有(　)．

A．50　B．60　C．24　D．616

2．5个高中毕业生报考三所重点院校,每人报且只报一所,则不同的报名方法有(　)种．

A．35　B．53　C．5×4×3　D．5×3

3．如果把两条异面直线看成是“一对”,则六棱锥的几条棱所在的直线中,异面直线共有(　)对．

A．12　B．24　C．36　D．48

4．已知a∈{0,3,4},b∈{1,2,7,8},r∈{8,9},则方程(x－a)2＋(y－b)2＝r2表示不同的圆的个数是_________．

5．从高三的四个班中共抽出学生22人,其中一、二、三、四班分别为4人、5人、6人、7人,他们自愿组成数学课外小组,选其中一人为组长,有_________种不同的选法．

6．有0,1,2,…,8这9个数字．

(1)用这9个数字组成四位数,共有多少个不同的四位数?

(2)用这9个数字组成四位密码,共有多少个这样的密码?

7．某外语组有9人,每人至少会英语和日语中的一门,其中7人会英语,3人会日语．从中选出会英语和日语的各一人,有多少种不同的选法?

8．要从甲、乙、丙3幅不同的画中选出2幅,分别挂在左、右两边墙上的指定位置,问共有多少种不同的挂法?

9．随着人们生活水平的提高,某城市家庭汽车拥有量迅速增长,汽车牌照号码需要扩容,交通管理部门出台了一种汽车牌照组成办法,每一个汽车牌照都必须有3个不重复的英文字母和3个不重复的阿拉伯数字,并且3个字母必须合成一组出现,3个数字也必须合成一组出现．那么这种办法共能给多少辆汽车上牌照?

10．给程序模块命名,需要用3个字符,其中首字符要求用字母A~G或U~Z,后两个要求用数字1~9．则最多可以给多少个程序命名?