1、第十章 排列、组合、二项式定理和概率第 讲 考 点搜 索分类计数原理的特点和算法分步计数原理的特点和算法高 考猜 想利用分类计数原理和分步计数原理求方法数1.完成一件事，有n类办法，在第1类办法中有m1种不同的方法，在第2类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法，那么完成这件事共有N=_种不同的方法.12nmmm2.完成一件事，需要分成n个步骤，做第1步有m1 种不同的方法，做第2步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事共有N=_种不同的方法.3.如果完成一件事有n类办法，其中第一类办法中的 _都能完成这件事，求完成这件事的方法种数就用 _原理，它可
2、用物理中的“并联”电路来理解，是一种加法原理.12nmmm任一种方法分类计数4.如果完成一件事需要分成n个步骤，其中每一步均 _这件事，只有依次完成所有步骤才能完成这件事，求完成这件事的方法种数就用 _原理，它可用物理中的“串联”电路来理解，是一种乘法原理.不能完成分步计数1.十字路口来往的车辆，如果不允回头，共有种行车路线（）A.24 B.16C.12 D.10解：起点有C41种可能，终点有C31种可能，因此，行车路线共有C41C31=12种.C2.从正方体的6个面中选取3个面，其中有2个面不相邻的选法共有()A.8种B.12种C.16种D.20种解：有2个面不相邻即有一组对面，所以选法为1
3、2种.B3411C C 3.某城市的电话号码，由六位升为七位(首位数字均不为零)，则该城市可增加的电话部数是()A.9876543 B.896C.9106 D.81105解：电话号码是六位数字时，该城市可安装电话9105部，同理升为七位时为9106，所以可增加的电话部数是9106-9105=81105.D题型1 利用分类计数原理求方法数 1.某中学高三年级有三个班，01班有学生50人，其中男生30人；02班有学生60人，其中男生30人；03班有学生55人，其中男生35人.(1)从这三个班中选一名学生任学生会主席，求共有多少种不同的选法？(2)从01班或02班的男生中，或从03班的女生中选一名学
4、生任学生会学习部长，求共有多少种不同的选法？解：(1)分三类：从01班选1名有50种；从02班选1名有60种；从03班选1名有55种.由分类计数原理，共有不同的选法506055165(种).(2)分三类：从01班男生中选1名有30种；从02班男生中选1名有30种；从03班女生中选1名有20种.由分类计数原理，共有不同的选法30302080(种).点评：利用分类进行计数时，主要是找到一个分类的标准.有时分类的划分标准有多个，但不论是以哪一个为标准，都应遵循“不重不漏”，求得的各类方法数的和就是最后的方法总数.在所有的两位数中，个位数字大于十位数字的两位数共有多少个？解：根据题意，将十位数上的数字
5、分别为1，2，3，4，5，6，7，8的情况分成八类，在每一类中满足题目条件的两位数分别有8个，7个，6个，5个，4个，3个，2个，1个.由分类计数原理知，符合题意的两位数共有87+6+5+4+3+2+136个.2.用5种不同的颜色给图中A、B、C、D四个区域涂色，规定每个区域只涂一种颜色，相邻区域颜色不同，求共有多少种不同的涂色方法？题型2 利用分步计数原理求方法数解：分四步：涂A有5种方法；涂B有种方法；涂C有3种方法；涂D有3种方法(D与A可以同色).由分步计数原理，共有5433=180(种).点评：分步计数就是把一件复杂的事件划分成几个步骤来完成，各步骤之间有一定的连续性，只有当全部步骤
6、完成了，整个事件才算完成，这是分步的基础，也是关键.从计数上来看，各步的方法数的积就是事件的方法数.(1)将4封信投入3个邮箱，有多少种不同的投法？(2)3位旅客到4个旅店住宿，有多少种不同的住宿方法？(3)4人各写一张贺卡，先集中起来，然后每人从中拿一张别人送出的贺卡，四张贺卡共有多少种不同的分配方式？解：(1)分四步：每一封信都有3种不同的投法，由分步计数原理，共有333381(种).(2)分三步：每位旅客都有4种不同的住宿方法,由分步计数原理,共有444=64(种).(3)分四步：四个人中的任意一人先取1张，有3种取法；由前一人取走的贺卡的供卡人取张，有3种取法；由余下的两人中的任一人取
7、，只有一种取法；最后一人取，只有一种取法.由分步计数原理，共有33119(种).3.某城市在中心广场建造一个花圃，花圃分为6个部分(如图).现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有种.(用数字作答).题型3 两个计数原理的综合应用 解法1：从题意来看，6部分种4种颜色的花，又从图形看，知必有2组同颜色的花，从同颜色的花入手分类求.(1)与同色，则也同色或也同色，所以共有N1=43221=48种；(2)与同色，则或同色，所以共有N2=43221=48种；(3)与且与同色，所以共有N3=4321=24种.所以，共有N=N1+N2+N3=48+48+2
8、4=120种.解法2：记颜色为A、B、C、D四色，先安排1、2、3有432种不同的栽法，不妨设1、2、3已分别栽种A、B、C，则4、5、6栽种方法共5种，由以下树状图清晰可见.根据分步计数原理，不同的栽种方法有N=4325=120种.点评：解法1是常规解法，解法2安排4、5、6时又用了分类和列举的方法.复杂事件的计数问题需要用到两种计数原理，一般采用的是先分类，后分步，各步中又可能涉及到分类，注意两个计数原理的综合应用.在编号为1、2、3、4的四块土地上分别种植编号为1，2，3，4的四个品种的小麦，但1号地不能种1号小麦，2号地不能种2号小麦，3号地不能种3号小麦，求共有多少种不同的种植方案?
9、解:分两类：若4号地种4号小麦，则1号地有2种种植方法，2、3号地都只有1种种植方法，所以共有211=2种方法若4号地不种4号小麦，则每块土地上种植的小麦的编号与土地的编号都不相同，第1号土地有3种种植方法，设1号地种i号小麦，则i号地有3种种植方法，余下的两块地各只有一种种法，所以共有3311=9种方法由分类计数原理，共有2+9=11种.1.将一个四棱锥的每个顶点染上一种颜色，并使同一条棱上的两端点颜色不同，如果只有5种颜色可供使用，求共有多少种不同的染色方案?解:记四棱锥为S-ABCD，五种颜色的编号为1，2，3，4，5分两步：第一步，对S、A、B三点染色，共有543=60种方法参 考 题
10、参 考 题第二步：对C、D两点染色当S、A、B已染好色时，不妨设其颜色分别为1，2，3，则C点可染2、4、5号色中的一种，分为三类若C染2号色，则D点可染3、4、5号色中的任一种，有3种方法；若C染4号色，则点D可染3、5号色中的任一种，有2种方法；若C染5号色，则点D可染3、4号色中的任一种，有2种方法由两个计数原理，共有60(3+2+2)=420种2.在任意两个正整数m和n间定义某种运算，用表示运算符号，并规定：当m和n都为奇数或都为偶数时,m n=m+n；当m和n中有一个为奇数，另一个为偶数时，mn=mn.设集合M=(a,b)|ab=36，a、bN*，求集合M中共有多少个元素？解：分两类
11、：当a、b都为正奇数或正偶数时,ab=a+b=36.所以a=1，b=35;或a=2，b=34或a=35，b=1，共有35个元素.当a、b中有一个为正奇数，另一个为正偶数时，ab=ab=36.所以a=1，b=36;或a=3，b=12;或a=4，b=9;或a=36，b=1;或a=12，b=3;或a=9，b=4，共有个元素.由分类计数原理知,共有35+641个元素.3.若m，nx|x=a2102+a110+a0，其中ai(i=0，1，2)1，2，3，4，5，6，并且m+n=606，则实数对(m，n)表示平面上不同点的个数为()A.32 B.30C.62 D.60D解：由m+n=606，其个位数字为6
12、，所以 a0 可有(1、5)，(5、1)，(2、4)，(4、2)，(3、3)共5种组成方法；十位数字为0，可有(4、6)，(6、4)、(5、5)共3种组成方法；百位数字为6，可由十位进上来1，余下5可有(1、4)，(4、1)，(2、3)，(3、2)共4种组成方法；由分步计数原理，实数对(m，n)的个数为53460，故选D.1利用两个计数原理解决实际问题时，先要弄清这是做一件什么事，这件事是怎么做的，再将“事件”进行分类或分步，然后分别计算各类或各步中的方法数，最后结合相应的原理得出结论2分类和分步的标准不是唯一的，不同的标准对应不同的解法，但在同一种解法中，必须采用同一个标准进行分类或分步，否则就会出现重复、遗漏、跳步、缺步等现象，从而产生错误结论3对既要分类又要分步的计数问题，一般先分类，将每一类问题看作一个“事件”，再通过分步来计算这一类的方法数；如果反面情况较简单，则可用间接法求解，即去掉不合要求的方法数，剩下的就是符合要求的方法数4对某些较简单的计数问题也可直接列举“事件”的各种可能情形，再数出方法种数.