第1课时 两个原理

§10.1分类计数原理与分步计数原理

一、知识精讲

分类计数原理与分步计数原理

分类计数原理：做一件事，完成它可以有n 类办法，在第一类办法中有1m 种不同的方法 ，

在第二类办法中有2m 种不同的方法，……，在第n 类办法中有n m 种不同的方法，那么完成这件事共有n m m m N +++= 21种不同的办法。

分步计数原理：做一件事，完成它需要分成n 个步骤，做第一步有1m 种不同的方法，做第

二步有2m 种不同的方法，……，做第n 步有n m 种不同方法，那么完成这件事共有n m m m N ???= 21种不同的方法。

特别注意:两个原理的共同点是把一个原始事件分解成若干个分事件来完成。不同点在于，一个与分类有关，一个与分步有关，如果完成一件事情共有n 类办法，这n 类办法彼此之间相互独立的，无论哪一类办法中的哪一种方法都能单独完成这件事情，求完成这件事情的方法种数，就用分类计数原理；如果完成一件事情需要分成n 个步骤，各个步骤都是不可缺少的，需要依次完成所有的步骤，才能完成这件事，而完成 每一个步骤各有若干种不同的方法，求完成这件事情的方法种数就用分步计数原理。

二、题型剖析

例2、（1）如图为一电路图，从A 到B 共有-

___________条不同的线路可通电。

解：按上中下通电可分三类，第一类有3种通法，

第二类1种，第三类分2步，每步又可分2种,

所以，共有3+1+2?2=8种通电方法。

（2）三边均为整数，且最大边长为11的三角形

的个数是 。

解：另两边用x 、y 表示，且不妨设111≤≤≤y x ，

要构成三角形，必须12≥+y x

当y 取值11时，11,,3,2,1 =x ，可有11个三角形；当y 取值10时，10,,3,2 =x ，可有9个三角形……当y 取值6时，x 只能取6，只有一个三角形

所以所求三角形的个数为11+9+7+5+3+1=36，故选C 。

（3）甲、乙、丙、丁四个公司承包8项工程，甲公司承包3项工程，乙公司承包1项，丙、丁各承包2项，问共有_____________种承包方式？

解：由分步计数原理有：168022241538=C C C C 种。思维点拔

【思维点拔】解决这类题首先要明确：“完成一件事”指什么？如何完成这件事（即分步还是分类）？进而确定应用分类计数原理还是分步计数原理。

分步计数原理中的“分步”程序要正确。“步”与“步”之间是连续的,不间断的,缺一不可。分类计数原理中的“分类”要全面, 不能遗漏。“类”与“类之间是并列的、互斥的、独立的,也就是说,完成一件事情,每次只能选择其中的一类办法中的某一种方法。

例3(优化设计P172例1)、电视台在”欢乐今宵”节目中拿出两个信箱,其中存放着先后两次竞猜中成绩优秀的观众来信,甲信箱中有30封,乙信箱中有20封.现有主持人抽奖确定幸运观众,若先确定一名幸运之星,再从两信箱中各确定一名幸运伙伴,有多少种不同的结果?

解: (1) 幸运之星在甲箱中抽,再在两箱中各定一名幸运伙伴,有30×29×20=1740种结果;

(1)幸运之星在乙箱中抽,同理有20×19×30=11400种结果。

由分类计数原理,共有17400+11400=28800 种不同结果。

【评述】在综合运用两个原理时，一般先分类再分步。

例4(优化设计P173例2)、从集合{1，2，3，∝，10}中，选出由5个数组成的子集，使得这5个数中的任何两个数的和不等于11，这样的子集共有多少个？

解：和为11的数共有5组：1与10，2与9，3与8，4与7，5与6，子集中的元素不能取自同一组的两数，，即子集中的元素取自5个组中的一个数，而每个数的取法有2种，所以子集个数为2?2?2?2?2=25=32

【评述】本题的关键是先找出和为11的5组数，然后利用分步计数原理求出结果。例5(优化设计P173例3)、某城市在中心广场造一个

花圃，花圃分为6个部分(如图).现要栽种4种不同

颜色的花，每部分栽种一种且相邻部分不能栽种同样颜

色的花，不同的栽种方法有________ 种.(以数字作答)

解法1: 因为区域1与其它5个区域都有公共边，所

以当区域1栽种一种颜色的花之后，该颜色的花就不

能栽于其它区域．因而可分两步走，考虑如下：

第一步，在区域1中，栽上一种颜色的花，有4种栽法；

第二步，在剩下的五个区域中，栽种其它三种颜色的花．为此，可将2至6号五个区域分成3组，使同一组中的不同区域没有公共边．这样的分组法有且只有5类，如下表(表中数字为区域号)：

对每一类分得的3个组，将3种颜色的花分别栽于各组，共有

3

3

P种栽法．

应用乘法原理和加法原理，得合乎题意要求的不同栽种方法的种数为

.120P 54N 33=?=

.1205P C )2111111(P C N 331

4333

4=?=??+?+?=

解法2 分两类情况考虑：

第1类：第1、2、3、5四个区域栽种不同颜色的4种花，共有44P 种栽法．对于每一种

栽法，第4、6区分别都只有1种颜色的花可栽．

第2类：第1、2、3、5四个区域栽种不同颜色的3种花，共有3334P C 2种栽法．对于每

一种栽法，要么2、5区栽同色花，要么3、5区栽同色花．对于前者，第6区有2种颜色的花可供选栽，第4区只能栽第4种颜色的花；对于后者，第4区有2种颜色的花可供选栽，第6区只能栽第4种颜色的花．即无论何种情形，第4、6区的栽法都是2种．

综合上述情形，应用加法原理与乘法原理，得不同栽种方法的种数为

.120P C 22P N 333

444=?+=

【评述】本题需抓住花圃布局的要求，看清图形中6个部分的关系；明确每个部分只种同一种颜色的花，相邻部分应种不同颜色的花；而且4种颜色的花都要种上，缺一不可．对这些条件要求，稍有疏忽、遗漏或曲解，都会引致解答出错．其次，应设计好周全而又不出现重复计数的推算程序，关键是推算过程中分步、分类的安排要合理且严密；此外，在每一分步或分类中，计数不出错；最后，乘法原理和加法原理的运用，以及数值计算还得无误，方能得出正确的答数．

练习题：在一个正六边形的六个区域栽种观赏植物（如图），要求同

一块中种同一种植物，相邻的两块种不同的植物，现有4种不

同的植物可供选择，则有多少种栽种方案？

解：考虑A 、C 、E 种同一种植物，此时共有1083334=???种方法。

考虑A 、C 、E 种二种植物，此时共有432223324=????A 种方法。

考虑A 、C 、E 种同三种植物，此时共有19222234=???A 种方法。

故总计有108+432+192=732种方法。

备用题：

例6、已知集合A=},,,{4321a a a a ,B=}3,2,1,0{,f 是从A 到B 的映射.(1) 从A 到B 总共有几个映射?(2)若B 中每个元素都有原象,则可建立几个不同的映射?(3)若B 中的元素0没有原象,则这样的f 有几个?(4)若B 中有一个元素没有原象,则这样的映射有几个?(5)若f 满足4)()()()(4321=+++a f a f a f a f ,则这样的f 又有几个?

解 (1)由乘法原理知有4

4个; (2) f 必为一一映射,故有2444=A 个; (3)8134

=个; (4)144332414=?A C C 个; (5) 因4=1+1+1+1=1+1+2+0=1+3+0+0=2+2+0+0,

故可分四类讨论,得满足要求的映射f 共有

=+++=2224131412241C C C C C C N 31612121=+++个

例7、四面体的顶点和各棱中点共有10个点，在其中取4个不共面的点，不同的取法共有（ ）

A 、150种

B 、147种

C 、144种

D 、141种

解：从10个点中任取4个点有410C 种取法，其中4点共面的情况有三类。第一类，取

出的4个点位于四面体的同一个面内，有46C 4种；第二类，取任一条棱上的3个点及该棱对

棱的中点，这4点共面，有6种；第三类，由中位线构成的平行四边形（其两组对边分别平行于四面体相对的两条棱），它的4个点共面，有3种。以上三种情况不合要求应减掉，所

以不同的取法共有14136C 4C 46410=---（种）

三、课堂小结：

1．分类计数原理和分步计数原理是解决排列、组合问题的理论基础。这两个原理的本质区别在于分类与分步，分类用分类计数原理，分步用分步计数原理 。

2．元素能重复的问题往往用计数原理。

3．注意：类”间相互独立，“步”间相互联系。

四、【布置作业】 优化设计P173