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

分类加法计数原理与分步乘法计数理第1页，共61页，2023年，2月20日，星期一山东省临沂一中学多媒体教学课件两大基本原理选修2-3第一章第2页，共61页，2023年，2月20日，星期一排列与组合计数原理二项式定理通项二项式系数性质排列数：组合数：分类计数原理分步计数原理性质对称性增减性与最大值各二项式系数的和两个原理第3页，共61页，2023年，2月20日，星期一

1.分类加法计数原理完成一件事有n类不同的方案,在第一类方案中有m1种不同的方法，在第二类方案中有m2种不同的方法,…,在第n类方案中有mn种不同的方法,则完成这件事情,共有N＝__________________种不同的方法.

2.分步乘法计数原理完成一件事情需要分成n个不同的步骤,完成第一步有m1种不同的方法,完成第二步有m2种不同的方法,…,完成第n步有mn种不同的方法,那么完成这件事情共有N＝__________________种不同的方法.忆一忆知识要点第4页，共61页，2023年，2月20日，星期一

3.分类加法计数原理与分步乘法计数原理,都涉及完成一件事情的不同方法的种数.它们的区别在于:分类加法计数原理与分类有关,各种方法相互独立,用其中的任一种方法都可以完成这件事;分步乘法计数原理与分步有关,各个步骤相互依存,只有各个步骤都完成了,这件事才算完成.忆一忆知识要点第5页，共61页，2023年，2月20日，星期一C16题号答案12345第6页，共61页，2023年，2月20日，星期一分类加法计数原理【例1】高三一班有学生50人,男生30人,女生20人;高三二班有学生60人,男生30人,女生30人;高三三班有学生55人,男生35人,女生20人．(1)从高三一班或二班或三班中选一名学生任学生会主席，有多少种不同的选法?(2)从高三一班、二班男生中，或从高三三班女生中选一名学生任学生会体育部长，有多少种不同的选法?解:(1)50＋60＋55＝165(种),即所求选法为165种.

(2)30＋30＋20＝80(种),即所求选法有80种.

分类时,首先要根据问题的特点确定一个适合于它的分类标准,然后在这个标准下进行分类;其次分类时要注意满足一个基本要求,就是完成这件事情的任何一种方法必须属于某一类,并且分别属于不同种类的两种方法是不同的方法,只有满足这些条件,才可以用分类加法计数原理.第7页，共61页，2023年，2月20日，星期一

同学衣服上左、右各有一个口袋，左边口袋装有30张英语单词卡片，右边口袋装有20张英语单词卡片，这些英语单词卡片都互不相同，则从两个口袋里任取一张英语单词卡片，有_____种不同的取法.从口袋中任取一张英语单词卡片的方法分两类:第一类：从左边口袋取一张英语单词卡片有30种不同的取法；第二类：从右边口袋取一张英语单词卡片有20种不同的取法；上述的其中任何一种取法都能独立完成取一张英语单词卡片这件事，应用分类加法计数原理,所以从中任取一张英语单词卡片的方法种数为30＋20＝50(种)．50第8页，共61页，2023年，2月20日，星期一分步乘法计数原理

【例2】已知集合M＝{－3,－2,－1,0,1,2},P(a,b)表示平面上的点(a,b∈M),问：(1)P可表示平面上多少个不同的点?(2)P可表示平面上多少个第二象限的点?(3)P可表示多少个不在直线y＝x上的点?解:(1)确定平面上的点P(a，b)可分两步完成：第一步确定a的值，共有6种确定方法；第二步确定b的值，也有6种确定方法．根据乘法原理,得到平面上的点的个数是6×6＝36.(2)确定第二象限的点，可分两步完成：第一步确定a，由于a<0,所以有3种确定方法；第二步确定b，由于b>0,所以有2种确定方法．由乘法原理,得到第二象限的点的个数是3×2＝6.第9页，共61页，2023年，2月20日，星期一分步乘法计数原理

(3)点P(a,b)在直线y＝x上的充要条件是a＝b.因此a和b必须在集合M中取同一元素,共有6种取法,即在直线y＝x上的点有6个.由(1)得不在直线y＝x上的点共有36－6＝30(个).利用分步乘法计数原理解决问题：①要按事件发生的过程合理分步，即分步是有先后顺序的；②各步中的方法互相依存，缺一不可，只有各个步骤都完成了才算完成这件事．【例2】已知集合M＝{－3,－2,－1,0,1,2},P(a,b)表示平面上的点(a,b∈M),问:(3)P可表示多少个不在直线y＝x上的点?第10页，共61页，2023年，2月20日，星期一已知集合M＝{－3,－2,－1,0,1,2},若a,b,c∈M,则(1)y＝ax2＋bx＋c可以表示多少个不同的二次函数;(2)y＝ax2＋bx＋c可以表示多少个图象开口向上的二次函数.解:(1)a的取值有5种情况,b的取值有6种情况,c的取值有6种情况,因此y＝ax2＋bx＋c可以表示5×6×6＝180(个)不同的二次函数.(2)y＝ax2＋bx＋c的开口向上时,a的取值有2种情况,

b,c的取值均有6种情况,因此y＝ax2＋bx＋c可以表示2×6×6＝72(个)图象开口向上的二次函数．第11页，共61页，2023年，2月20日，星期一两个计数原理的综合应用【例3】用0,1,2,3,4,5可以组成多少个无重复数字的比2000大的4位偶数?解:完成这件事可分为3类方法：第一类是用0做结尾的比2000大的4位偶数,它可以分三步去完成:第一步,选取千位上的数字,只有2,3,4,5可以选择,有4种选法；第二步，选取百位上的数字，除0和千位上已选定的数字以外，还有4个数字可供选择，有4种选法；第三步，选取十位上的数字，还有3种选法．依据分步乘法计数原理,这类数的个数有4×4×3＝48(个);第12页，共61页，2023年，2月20日，星期一两个计数原理的综合应用

第二类是用2做结尾的比2000大的4位偶数,它可以分三步去完成；第一步，选取千位上的数字，除去2,1,0只有3个数字可以选择，有3种选法；第二步，选取百位上的数字，在去掉已经确定的首尾两数字之后，还有4个数字可供选择，有4种选法;第三步，选取十位上的数字，还有3种选法．依据分步乘法计数原理，这类数的个数有3×4×3＝36(个)；

第三类是用4做结尾的比2000大的4位偶数，

其步骤同第二类，有3×4×3＝36(个)．对以上三类结论用分类加法计数原理，可得所求无重复数字的比2000大的4位偶数有48＋36＋36＝120(个).第13页，共61页，2023年，2月20日，星期一用两个计数原理解决计数问题时,关键是明确需要分类还是分步．(1)分类要做到“不重不漏”，分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数．(2)分步要做到“步骤完整”,只有完成了所有步骤,才完成任务，根据分步乘法计数原理,把完成每一步的方法数相乘,得到总数．(3)对于复杂问题，可同时运用两个计数原理或借助列表、画图的方法来帮助分析．第14页，共61页，2023年，2月20日，星期一解:方法一以S,A,B,C,D顺序分步染色．第一步,S点染色,有5种方法;第二步,A点染色,与S在同一条棱上，有4种方法;第三步,B点染色,与S,A分别在同一条棱上,有3种方法;第四步,C点染色,也有3种方法,但考虑到D点与S,A,C相邻,需要针对A与C是否同色进行分类.当A与C同色时,D点有3种染色方法;当A与C不同色时,因为C与S,B也不同色,所以C点有2种染色方法,D点也有2种染色方法.由分步乘法、分类加法计数原理得不同的染色方法共有5×4×3×(1×3＋2×2)＝420(种).如图所示,将一个四棱锥的每一个顶点染上一种颜色,并使同一条棱上的两端异色,如果只有5种颜色可供使用,求不同的染色方法总数.第15页，共61页，2023年，2月20日，星期一解:方法二可分为两大步进行，先将四棱锥一侧面三顶点染色，然后再分类考虑另外两顶点的染色数，用分步乘法计数原理即可得出结论．由题设,四棱锥S—ABCD的顶点S,A,B所染的颜色互不相同,它们共有5×4×3＝60(种)染色方法．当S,A,B染好时,不妨设其颜色分别为1,2,3,若C染2,则D可染3或4或5，有3种染法；若C染4，则D可染3或5，有2种染法；若C染5，则D可染3或4，有2种染法．可见，当S、A、B已染好时，C、D还有7种染法，故不同的染色方法有60×7＝420(种)．第16页，共61页，2023年，2月20日，星期一方法三按所用颜色种数分类．第一类:5种颜色全用,共有种不同的方法;第二类:只用4种颜色，则必有某两个顶点同色(A与C,或B

与D),共有2×种不同的方法；第三类:只用3种颜色,则A与C,B与D必定同色,共有种不同的方法．由分类加法计数原理,得不同的染色方法总数为

＝420(种)．如图所示,将一个四棱锥的每一个顶点染上一种颜色,并使同一条棱上的两端异色，如果只有5种颜色可供使用,求不同的染色方法总数.第17页，共61页，2023年，2月20日，星期一(5分)(2010·湖南)在某种信息传输过程中，用4个数字的一个排列(数字允许重复)表示一个信息，不同排列表示不同信息．若所用数字只有0和1，则与信息0110至多有两个对应位置上的数字相同的信息个数为()A．10B．11C．12D．152611分类不准、计数原理使用不当致误B第18页，共61页，2023年，2月20日，星期一11分类不准、计数原理使用不当致误解:方法一分0个相同、1个相同、2个相同讨论．(1)若0个相同,则信息为:1001.共1个．(2)若1个相同,则信息为:0001,1101,1011,1000.共4个.(3)若2个相同，又分为以下情况：①若位置一与二相同，则信息为：0101；②若位置一与三相同，则信息为：0011；③若位置一与四相同，则信息为：0000；④若位置二与三相同，则信息为：1111；⑤若位置二与四相同，则信息为：1100；⑥若位置三与四相同，则信息为：1010.共有6个.故与信息0110至多有两个对应位置上的数字相同的信息个数为1＋4＋6＝11.第19页，共61页，2023年，2月20日，星期一解:方法二若0个相同，共有1个；若1个相同，共有＝4(个)；若2个相同，共有＝6(个)．故共有1＋4＋6＝11(个)．第20页，共61页，2023年，2月20日，星期一(1)本题考查的是分类加法计数原理，难度不大,属中档题．(2)本题要求至多有两个对应位置上的数字相同,应按照0个相同、1个相同、2个相同进行讨论，本题易错点是易漏掉0个相同的情况.第21页，共61页，2023年，2月20日，星期一1.分类加法和分步乘法计数原理，都是关于做一件事的不同方法的种数的问题，区别在于：分类加法计数原理针对“分类”问题，其中各种方法相互独立，用其中任何一种方法都可以做完这件事；分步乘法计数原理针对“分步”问题，各个步骤相互依存，只有各个步骤都完成了才算完成这件事.2.混合问题一般是先分类再分步.3.分类时标准要明确，做到不重复不遗漏.4.要恰当画出示意图或树状图，使问题的分析更直观、清楚，便于探索规律.第22页，共61页，2023年，2月20日，星期一

应用两种原理解题：(1)分清要完成的事情是什么？(2)分清完成该事情是分类完成还是分步完成,“类”间互相独立，“步”间互相联系；(3)有无特殊条件的限制；(4)检验是否有重漏．第23页，共61页，2023年，2月20日，星期一作业布置作业纸:课时规范训练:P.1-2第24页，共61页，2023年，2月20日，星期一预祝各位同学，2013年高考取得好成绩!第25页，共61页，2023年，2月20日，星期一第26页，共61页，2023年，2月20日，星期一一、选择题二、填空题题号123答案CCDA组

专项基础训练题组第27页，共61页，2023年，2月20日，星期一三、解答题7.如图,用四种不同颜色给图中的A,B,

C,D,E,F六个点涂色,要求每个点涂一种颜色,且图中每条线段的两个端点涂不同颜色.则不同的涂色方法共有多少种?解:先涂A,D,E三个点,共有4×3×2=24(种)涂法,然后再按B,C,F的顺序涂色,分为两类：

一类是B与E或D同色,共有2×(2×1+1×2)=8(种)涂法;

另一类是B与E或D不同色,共有1×(1×1+1×2)=3(种)涂法.所以涂色方法共有24×(8+3)=264(种)．第28页，共61页，2023年，2月20日，星期一三、解答题8.某外语组有9人，每人至少会英语和日语中的一门,其中7人会英语，3人会日语，从中选出会英语和日语的各一人,有多少种不同的选法?解:由题意得有1人既会英语又会日语,6人只会英语,2人只会日语．第一类:从只会英语的6人中选1人说英语,共有6种方法,则说日语的有2＋1＝3(种),此时共有6×3＝18(种);第二类:从不只会英语的1人中选1人说英语,则只有1种方法,则选会日语的有2种,此时共有1×2＝2(种)；所以根据分类加法计数原理知共有18＋2＝20(种)选法.第29页，共61页，2023年，2月20日，星期一一、选择题二、填空题题号123答案BCBB组专项能力提升题组第30页，共61页，2023年，2月20日，星期一

解:(1)显然对应是一一对应的,即为a1找象有4种方法，a2找象有3种方法，a3找象有2种方法，a4找象有1种方法，所以不同的f共有4×3×2×1＝24(个)．(2)0必无原象,1,2,3有无原象不限，所以为A中每一元素找象时都有3种方法．所以不同的f共有34＝81(个)．三、解答题8.已知集合A＝{a1,a2,a3,a4},B＝{0,1,2,3},f是从A到B的映射.(1)若B中每一元素都有原象,这样不同的f有多少个?(2)若B中的元素0必无原象,这样的f有多少个?(3)若f满足f(a1)＋f(a2)＋f(a3)＋f(a4)＝4,这样的f又有多少个?第31页，共61页，2023年，2月20日，星期一第32页，共61页，2023年，2月20日，星期一第33页，共61页，2023年，2月20日，星期一排列、组合计数原理计数原理二项式定理组合通项二项式定理二项式系数性质分类计数原理分步计数原理排列排列的定义排列数公式组合的定义组合数公式组合数性质应用第34页，共61页，2023年，2月20日，星期一名称内容加法原理乘法原理定义相同点不同点做一件事或完成一项工作的方法数直接(分类)完成间接(分步骤)完成做一件事,完成它可以有n类办法,第一类办法中有m1种不同的方法,第二类办法中有m2种不同的方法,第n类办法中有mn种不同的方法,那么完成这件事共有N=m1+m2+m3+…+mn种不同的方法.做一件事,完成它可以有n个步骤,做第一步中有m1种不同的方法,做第二步中有m2种不同的方法…,第n步中有mn种不同的方法,那么完成这件事共有N=m1·m2·m3·…·mn种不同的方法.1.两个原理的区别于联系第35页，共61页，2023年，2月20日，星期一

【结论】集合A中有m个元素，集合B中有n个元素，那么从A到B可以构造nm个映射.解:第一步，给a找对应元素，有3种方法；第二步，给b找对应元素，有3种方法；第三步，给c找对应元素，有3种方法；第四步，给d找对应元素，有3种方法；第五步，给e找对应元素，有3种方法.例1.设A={a,

b,

c,

d,

e

},

B={x,

y,

z},从A到B共有多少种不同的映射?一映射个数问题形成一个映射,就是让A中所有元素都找到对应元素.则共有方法种数N=35.第36页，共61页，2023年，2月20日，星期一例1.设A={a,

b,

c,

d,

e,

f

},

B={x,

y,

z},从A到B共有多少种不同的映射?【1】设A={1,2,3},

B={4,

5,

6},从A到B满足1的象是4的映射有多少种?【2】设集合A={x,

y,

z},

B

={-1,0,1},映射f:A→B满足f(x)+f(y)+f(z)=0的映射有多少种?练一练第37页，共61页，2023年，2月20日，星期一【3】已知集合A＝{a,b,c,d},集合B＝{1,2,3,4,5},集合C={e,f,g,h}.(1)从集合B到集合A可以建立多少个不同的映射?(2)在集合A到集合B的映射中,若要求集合A中的不同元素的象也不同,这样的映射有多少个?(3)从集合A到集合C可以建立多少个一一映射?练一练第38页，共61页，2023年，2月20日，星期一例2.集合A={a,

b,

c,

d,

e},它的子集个数为___,真子集个数为______,非空子集个数为_____,非空真子集个数为_______.二子集问题【1】集合M满足{1,

2}⊆M⊆{0,

1,

2,

3,

4,

5},则这样的集合M有多少个？变式练习第39页，共61页，2023年，2月20日，星期一真子集有______个，非空子集个数为_________，非空真子集个数有__________.【规律】n元集合{a1,

a2,

···,

an},的不同子集有个_____个.2n二子集问题第40页，共61页，2023年，2月20日，星期一解:按地图A,B,C,D四个区域依次分四步完成,第一步,m1=3种,第二步,m2=2种,第三步,m3=1种,第四步,m4=1种,三、着色问题例3.如图,要给地图A,B,C,D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？所以根据乘法原理,得到不同的涂色方案种数共有N=3×2×1×1=6种.第41页，共61页，2023年，2月20日，星期一例3.如图,要给地图A,B,C,D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？三、着色问题第42页，共61页，2023年，2月20日，星期一用红,黄,绿,黑四种不同的颜色涂入下图中的五个区域内,要求相邻的两个区域的颜色都不相同,则有多少种不同的涂色方法？当B与D不同色时,有43211=24种.ABCDE解:当B与D同色时,有43212=48种;故共有48+24=72种不同的涂色方法.练一练第43页，共61页，2023年，2月20日，星期一点评:像这类给区域涂色的问题,我们应该给区域依次标上相应的序号,以便分析问题,在给各区域涂色时,要注意不同的涂色顺序其解题就有繁简之分.ABCDE如本例若按A、B、E、D、C顺序涂色时,在最后给区域C涂色时,就应考虑A与E是否同色,B与D是否同色这两种情况.因此在分析解决这类问题时,应按不同的涂色顺序多多尝试,看那一个最简单.本例易错点:未考虑B与D是否同色.第44页，共61页，2023年，2月20日，星期一(2003年·全国高考题)如图所示,一个地区分为5个行政区域,现给地图着色,要求相邻区域不得使用同一颜色,现有4种颜色可供选择,则不同的着色方法有___种.(以数字作答)同类变式解:因区域1与其他四个区域都相邻,宜先考虑区域1,有4种涂法.13425第45页，共61页，2023年，2月20日，星期一同类变式(2)若区域2,4不同色,先涂区域2有3种方法,再涂区域4有2种方法,此时区域3,5也都只有1种涂法,涂法总数为4321=24种,因此涂法共有72种.(1)若区域2,4同色,有3种涂法,此时区域3,5均有两种涂法,涂法总数为4322=48种;13425第46页，共61页，2023年，2月20日，星期一例4.用0,

1,

2,

3,

4,

5这六个数字,(1)可以组成多少个各位数字不允许重复的六位的自然数？(2)可以组成多少个各位数字不允许重复的三位的奇数?(3)可以组成多少个各位数字不重复的小于1000的自然数?(4)可以组成多少个大于3000,小于5421且各位数字不允许重复的四位数?四、排数字问题第47页，共61页，2023年，2月20日，星期一【1】1,2,3,4数字可以组成多少个没有重复数字能被3整除的三位数？【2】随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容.交通管理部门出台了一种汽车牌照组成办法，每一个汽车牌照都必须有３个不重复的英文字母和３个不重复的阿拉伯数字,并且３个字母必须合成一组出现,３个数字也必须合成一组出现，那么这种办法共能给多少辆汽车上牌照?练一练第48页，共61页，2023年，2月20日，星期一第二步:让与甲取走的卡片相对应的人来拿,有3种拿法.(例如甲拿的是2，则乙有3种拿法.)总的方法数N=3×3×1×1=9.方法一:采用”分步”处理第一步:甲先拿,按规定甲可拿2，3，4当中的一张,有3种方法.第三步:让剩余的两个人拿，都均有1种拿法.例5.同室4人各写1张贺年卡，先集中起来，然后每人从中各拿1张别人送出的贺年卡，则4张贺年卡不同的分配方式有()A.6种

B.9种

C.11种

D.23种五、综合问题B第49页，共61页，2023年，2月20日，星期一树图法甲乙丙丁213444131331442214124133212321解:四名同学分别为:甲、乙、丙、丁,所写贺卡依次为1，2，3，4.第50页，共61页，2023年，2月20日，星期一例6.自然数4320有多少个正约数？解：4320＝25×33×5,其正约数的结构式为其中α可取0,1,2,3,4,5;β可取0,1,2,3;γ可取0,1.即在α,β,γ所形成的取值集合中,各取一个元素填入上式,就得4320的一个约数.第一步：取20，21，22，23，24，25有6种;第二步：取30，31，32，33有4种；第三步：取50，51有2种.由分步计数原理，共有6×4×2＝48种.第51页，共61页，2023年，2月20日，星期一【1】630的不同的正约数的个数是____.练一练解:630＝2×32×5×7【2】5张1元币，4张1角币，1张5分币，2张2分币，可组成_____种不同的币值？(1张不取，即0元0分0角不计在内)元：0，1，2，3，4，5角：0，1，2，3，4分：0，2，4，5，7，96×5×6－1＝179179第52页，共61页，2023年，2月20日，星期一【3】三边长均为整数,且最大边长为11的三角形共有多少个?解:另两边长用x,y表示,且不妨设1≤x≤y≤11,要构成三角形,必须x+y≥12.当y=11时,有11个三角形;当y=10时,有9个三角形;当y=6时,有1个三角形;所以,所求三角形的个数共有练一练第53页，共61页，2023年，2月20日，星期一【3】在所有的两位数中,个位数字大于十位数字的两位数共有多少个？分析1:按个位数字是2,3,4,5,6,7,8,9分成8类,在每一类中满足条件的两位数分别是1个,2个,3个,4个,5个,6个,7个,8个.则根据加法原理共有1+2+3+4+5+6+7+8=36(个).分析2:按十位数字是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