§10.1分类计数原理与分步计数原理一、知识精讲分类计数原理与分步计数原理分类计数原理：做一件事，完成它可以有类办法，在第一类办法中有种不同的方法，在第二类办法中有种不同的方法，……，在第类办法中有种不同的方法，那么完成这件事共有种不同的办法。分步计数原理：做一件事，完成它需要分成个步骤，做第一步有种不同的方法，做第二步有种不同的方法，……，做第步有种不同方法，那么完成这件事共有种不同的方法。特别注意:两个原理的共同点是把一个原始事件分解成若干个分事件来完成。不同点在于，一个与分类有关，一个与分步有关，如果完成一件事情共有类办法，这类办法彼此之间相互独立的，无论哪一类办法中的哪一种方法都能单独完成这件事情，求完成这件事情的方法种数，就用分类计数原理；如果完成一件事情需要分成个步骤，各个步骤都是不可缺少的，需要依次完成所有的步骤，才能完成这件事，而完成每一个步骤各有若干种不同的方法，求完成这件事情的方法种数就用分步计数原理。二、题型剖析例1、把一个圆分成3块扇形，现在用5种不同的颜色给3块扇形涂色，要求相邻扇形的颜色互不相同，问有多少钟不同的涂法？若分割成4块扇形呢？dcab解：（1）不同涂色方法数是：（种）（2）如右图所示,分别用a,b,c,d记这四块,a与c可同色,也可不同色,先考虑给a,c两块涂色,分两类给a,c涂同种颜色共种涂法,再给b涂色有4种涂法,最后给d涂色也有4种涂法,由乘法原理知,此时共有种涂法给a,c涂不同颜色共有种涂法,再给b涂色有3种方法,最后给d涂色也有3种，此时共有种涂法故由分类计数原理知，共有+=260种涂法。例2、（1）如图为一电路图，从A到B共有___________条不同的线路可通电。解：按上中下通电可分三类，第一类有3种通法，第二类1种，第三类分2步，每步又可分2种,所以，共有3+1+22=8种通电方法。AB（2）三边均为整数，且最大边长为11的三角形的个数是。解：另两边用x、y表示，且不妨设，要构成三角形，必须当y取值11时，，可有11个三角形；当y取值10时，，可有9个三角形……当y取值6时，x只能取6，只有一个三角形所以所求三角形的个数为11+9+7+5+3+1=36，故选C。（3）甲、乙、丙、丁四个公司承包8项工程，甲公司承包3项工程，乙公司承包1项，丙、丁各承包2项，问共有_____________种承包方式？解：由分步计数原理有：种。思维点拔【思维点拔】解决这类题首先要明确：“完成一件事”指什么？如何完成这件事（即分步还是分类）？进而确定应用分类计数原理还是分步计数原理。分步计数原理中的“分步”程序要正确。“步”与“步”之间是连续的,不间断的,缺一不可。分类计数原理中的“分类”要全面,不能遗漏。“类”与“类之间是并列的、互斥的、独立的,也就是说,完成一件事情,每次只能选择其中的一类办法中的某一种方法。例3(优化设计P172例1)、电视台在”欢乐今宵”节目中拿出两个信箱,其中存放着先后两次竞猜中成绩优秀的观众来信,甲信箱中有30封,乙信箱中有20封.现有主持人抽奖确定幸运观众,若先确定一名幸运之星,再从两信箱中各确定一名幸运伙伴,有多少种不同的结果?解:(1)幸运之星在甲箱中抽,再在两箱中各定一名幸运伙伴,有30×29×20=1740种结果;幸运之星在乙箱中抽,同理有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类，