《两个基本计数原理二》由会员分享,可在线阅读,更多相关《两个基本计数原理二(48页珍藏版)》请在金锄头文库上搜索。
1、两个基本计数原理二Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望 什么是分类计数原理?什么是分类计数原理? 什么是分步计数原理?什么是分步计数原理? 应用这两个原理时应注意什么问题?应用这两个原理时应注意什么问题?分类计数原理(加法原理)分类计数原理(加法原理)做一件事情,完成它可以做一件事情,完成它可以有有n类办法类办法,在第一类办法中有在第一类办法中有m1种不同的方法种不同的方法,在第二在第二类办法中有类办法中有m2种不同的方法,种不同的方法,在第,在第n类办法中有类办法中有m
2、n种不同的方法。那么完成这件事共有种不同的方法。那么完成这件事共有N=m1+m2+mn种不同的方法。种不同的方法。分步计数原理(乘法原理)分步计数原理(乘法原理)做一件事情,完成它需做一件事情,完成它需要分成要分成n个步骤,做第一步有个步骤,做第一步有m1种不同的方法,做第种不同的方法,做第二步有二步有m2种不同的方法,种不同的方法,做第,做第n步有步有mn种不同种不同的方法,那么完成这件事有的方法,那么完成这件事有N=m1m2mn种不同的方法。种不同的方法。 分类计数原理分类计数原理( (加法原理加法原理) )中,中,“完成一件完成一件事,有事,有n n类方式类方式”,即,即每种方式都可以独
3、立地每种方式都可以独立地完成这件事完成这件事。进行分类时,要求。进行分类时,要求各类方式彼此各类方式彼此之间是相互排斥的之间是相互排斥的,不论那一类办法中的哪一,不论那一类办法中的哪一种方法,种方法,都能独立完成这件事都能独立完成这件事。只有满足这个。只有满足这个条件,才能直接用加法原理,否则不可以。条件,才能直接用加法原理,否则不可以。 分步计数原理分步计数原理( (乘法原理乘法原理) )中,中,“完成一件完成一件事,需要分成事,需要分成n n个步骤个步骤”,是说,是说每个步骤都不足每个步骤都不足以完成这件事以完成这件事。如果完成一件事需要分成几个。如果完成一件事需要分成几个步骤,步骤,各步
4、骤都不可缺少各步骤都不可缺少,需要依次完成所有,需要依次完成所有步骤才能完成这件事,而步骤才能完成这件事,而各步要求相互独立各步要求相互独立,即相对于前一步的每一种方法,下一步有即相对于前一步的每一种方法,下一步有m m种不种不同的方法,那么完成这件事的方法数就可以直同的方法,那么完成这件事的方法数就可以直接用乘法原理。接用乘法原理。2.如图如图,该电路该电路,从从A到到B共有共有多少条不同的多少条不同的线路可通电?线路可通电?AB解解:从总体上看由从总体上看由A到到B的通电线路可分三类的通电线路可分三类,第一类第一类,m1=3条条第二类第二类,m2=1条条第三类第三类,m3=22=4,条条所
5、以所以,根据分类计数原理根据分类计数原理,从从A到到B共有共有N=3+1+4=8条不同的线路可通电。条不同的线路可通电。当然当然,也可以把并联的也可以把并联的4个看成一类个看成一类,这样也可分这样也可分2类求解。类求解。.ABABm1m1m2m2mnmn点评点评:我们可以把我们可以把分类计数原理看成分类计数原理看成“并联电路并联电路”;分分步计数原理看成步计数原理看成“串联电路串联电路”。如图。如图:如图如图,一蚂蚁沿着长方体的棱一蚂蚁沿着长方体的棱,从它的一个顶点爬从它的一个顶点爬到相对的另一个顶点的最近路线共有多少条?到相对的另一个顶点的最近路线共有多少条?课堂练习课堂练习3AC1解解:
6、:如图如图, ,从总体上看从总体上看, ,如如, ,蚂蚁从顶点蚂蚁从顶点A A爬到顶点爬到顶点C C1 1有三类方有三类方法法 从局部上看每类又需两步完成从局部上看每类又需两步完成, ,所以所以, , 第一类第一类, m, m1 1 = 1 = 12 = 2 2 = 2 条条 第二类第二类, m, m2 2 = 1 = 12 2 = 2 = 2 条条 第三类第三类, m, m3 3 = 1 = 12 = 2 2 = 2 条条根据分类计数原理根据分类计数原理, , 从顶点从顶点A A到顶点到顶点C C1 1最近路线共有最近路线共有 N = 2 N = 2 + 2 + 2 = 6 + 2 + 2
7、= 6 条。条。 4.如图如图,从甲地到乙地有从甲地到乙地有2条路可通条路可通,从乙地到丙地有从乙地到丙地有3条路条路可通可通;从甲地到丁地有从甲地到丁地有4条路可通条路可通,从丁地到丙地有从丁地到丙地有2条路条路可通。从甲地到丙地共有多少种不同的走法?可通。从甲地到丙地共有多少种不同的走法?甲地乙地丙地丁地解解:从总体上看从总体上看,由甲到丙由甲到丙有两类不同的走法有两类不同的走法,第一类第一类,由甲经乙去丙由甲经乙去丙,又需分两步又需分两步,所以所以m1=23=6种不同的走法种不同的走法;第二类第二类,由甲经丁去丙由甲经丁去丙,也需分两步也需分两步,所以所以m2=42=8种不同的走法种不同
8、的走法;所以从甲地到丙地共有所以从甲地到丙地共有N=6+8=14种不同的种不同的走法。走法。 例例1 1、某艺术组有、某艺术组有9 9人,每人至少会钢人,每人至少会钢琴和小号中的一种乐器,其中琴和小号中的一种乐器,其中7 7人会钢琴,人会钢琴,3 3人会小号,从中选出会钢琴和会小号的各人会小号,从中选出会钢琴和会小号的各一人,有多少种不同的选法?一人,有多少种不同的选法? 例例2 2、用红、黄、蓝不同颜色的旗各三、用红、黄、蓝不同颜色的旗各三面,每次升一面、两面、三面在某一旗杆面,每次升一面、两面、三面在某一旗杆上纵向排列,共可以组成多少种不同的信上纵向排列,共可以组成多少种不同的信号?号?提
9、示提示:对于有些较对于有些较“复杂复杂”的问题,往往不是单纯的问题,往往不是单纯的的“分类分类”、“分步分步”就可解决的,而往往将两者就可解决的,而往往将两者结合使结合使用用,一般是,一般是先先“分类分类”,再在每一类中进行,再在每一类中进行“分步分步”。 例例3 3、为了确保电子信箱的安全,在注、为了确保电子信箱的安全,在注册时,通常要设置电子信箱密码。在某网站册时,通常要设置电子信箱密码。在某网站设置的信箱中,设置的信箱中, (1 1)密码为)密码为4 4位,每位均为位,每位均为0 0到到9 9这这1010个数字个数字中的一个数字,这样的密码共有多少个?中的一个数字,这样的密码共有多少个?
10、(2 2)密码为)密码为4 4位,每位均为位,每位均为0 0到到9 9这这1010个数字个数字中的一个,或是从中的一个,或是从A A到到Z Z这这2626个英文字母中的个英文字母中的1 1个。这样的密码共有多少个?个。这样的密码共有多少个? (3 3)密码为)密码为4 4到到6 6位,每位均为位,每位均为0 0到到9 9这这1010个个数字中的一个。这样的密码共有多少个?数字中的一个。这样的密码共有多少个?排数字问题排数字问题例例4 用用0,1,2,3,4,5这六个数字这六个数字,(1)可以组成多少个各位数字不允许重复的三位可以组成多少个各位数字不允许重复的三位的奇数的奇数?(2)可以组成多少
11、个各位数字不重复的小于可以组成多少个各位数字不重复的小于1000的自然数的自然数?(3)可以组成多少个大于可以组成多少个大于3000,小于小于5421且各位且各位数字不允许重复的四位数数字不允许重复的四位数?(1993年全国高考题)同室年全国高考题)同室4人各写人各写1张张贺年卡,先集中起来,然后每人从中各贺年卡,先集中起来,然后每人从中各拿拿1张别人送出的贺年卡,则张别人送出的贺年卡,则4张贺年卡张贺年卡不同的分配方式有不同的分配方式有()A6种种B9种种C11种种D23种种变式变式:问题拓展:v (1) 若直线方程若直线方程ax+by=0中的中的a,b可以从可以从0,1,2,3,4这五个数
12、字中任取两个不同的数字这五个数字中任取两个不同的数字,则方程所表示的不同的直线共有多少条则方程所表示的不同的直线共有多少条?(2)集合集合A=1,2,-3,B=-1,-2,3,4从从A、B中各中各取取1个元素作为点个元素作为点P(x,y)的坐标的坐标(1)可以得到多少个不同的点?)可以得到多少个不同的点?(2)这些点中,位于第一象限的有几个?)这些点中,位于第一象限的有几个?(3)、某赛季足球比赛的记分规则、某赛季足球比赛的记分规则是:胜一场得是:胜一场得3分,平一场得分,平一场得1分,分,负一场得负一场得0分。一球队打完分。一球队打完15场比场比赛积赛积33分,若不考虑顺序,该队分,若不考虑
13、顺序,该队胜、平、负的情况共有(胜、平、负的情况共有()(A)5种种(B)4种种(C)3种种(D)6种种映射个数问题:v例例5 设设A=a,b,c,d,B=x,y,z,从从A到到B共有多共有多少种不同的映射少种不同的映射?v变式变式:v(1)4个人分到个人分到3个车间个车间,共有多少种分发共有多少种分发?v(2)4个人分工栽个人分工栽3棵树棵树,每人只栽每人只栽1棵棵,共有多共有多少种不同方案少种不同方案? (1 1)4 4名同学选报跑步、跳高、跳远三名同学选报跑步、跳高、跳远三个项目,每人报一项,共有多少种报名方法个项目,每人报一项,共有多少种报名方法? (2 2)4 4名同学争夺跑步、跳高
14、、跳远三名同学争夺跑步、跳高、跳远三个项目的冠军,共有多少种可能的结果?个项目的冠军,共有多少种可能的结果? (3) (3)、某中学的一幢、某中学的一幢5 5层教学楼共有层教学楼共有3 3处楼处楼梯,问从梯,问从1 1楼到楼到5 5楼共有多少种不同的走法?楼共有多少种不同的走法? (4) (4)、有、有n n个元素的集合的子集共有多少个元素的集合的子集共有多少个?个?拓展拓展: (5) (5)、自然数、自然数25202520有多少个正约数?有多少个正约数?课堂练习课堂练习1.如图如图,要给地图要给地图A、B、C、D四个区域分别涂上四个区域分别涂上3种不同颜色中的某一种种不同颜色中的某一种,允许
15、同一种颜色使用多次允许同一种颜色使用多次,但相邻区域必须涂不同的颜色但相邻区域必须涂不同的颜色,不同的涂色方案有多不同的涂色方案有多少种?少种?课堂练习课堂练习1.如图如图,要给地图要给地图A、B、C、D四个区域分别涂上四个区域分别涂上3种不同颜色中的某一种种不同颜色中的某一种,允许同一种颜色使用多次允许同一种颜色使用多次,但但相邻区域必须涂不同的颜色相邻区域必须涂不同的颜色,不同的涂色方案有多少种不同的涂色方案有多少种?解解:按地图按地图A、B、C、D四个区四个区域依次分四步完成域依次分四步完成,第一步第一步,m1=3种种,第二步第二步,m2=2种种,第三步第三步,m3=1种种,第四步第四步
16、,m4=1种种,所以根据分步计数原理所以根据分步计数原理,得到得到不同的涂色方案种数共有不同的涂色方案种数共有N=3211=6种。种。课堂练习课堂练习1.如图如图,要给地图要给地图A、B、C、D四个区域分别涂上四个区域分别涂上3种不同颜色中的某一种种不同颜色中的某一种,允许同一种颜色使用多次允许同一种颜色使用多次,但相邻区域必须涂不同的颜色但相邻区域必须涂不同的颜色,不同的涂色方案有多不同的涂色方案有多少种?少种?问问:若用若用2色、色、3色、色、4色、色、5色等色等,结果又怎样呢?结果又怎样呢?答答:它们的涂色方案种数分别它们的涂色方案种数分别是是0,4322=48,5433=180种等。种
17、等。染色问题:v例例6 有有n种不同颜色为下列两块广告牌着色种不同颜色为下列两块广告牌着色,要求要求在在四个区域中相邻四个区域中相邻(有公共边界有公共边界)区域中区域中不用同一种颜色不用同一种颜色.v(1)若若n=6,为为(1)着色时共有多少种方法着色时共有多少种方法?v(2)若为若为(2)着色时共有着色时共有120种不同方法种不同方法,求求nv v v v (1) (2) 例例7 7、(、(1 1)8 8张卡片上写着张卡片上写着0,1,2,70,1,2,7共共8 8个数字,取其中的三张卡片排放在一起,可个数字,取其中的三张卡片排放在一起,可组成多少个不同的三位数?组成多少个不同的三位数? (
18、2 2)4 4张卡片的正、反面分别写有张卡片的正、反面分别写有0 0与与1 1、2 2与与3 3、4 4与与5 5、6 6与与7 7,将其中的,将其中的3 3张卡片排放在张卡片排放在一起,共有多少个不同的三位数?一起,共有多少个不同的三位数?综合问题综合问题:例例8、在一块并排、在一块并排10垅的田地中,垅的田地中,选择选择2垅分别种植垅分别种植A、B两种作物,两种作物,每种作物种植一垅,为有利于作每种作物种植一垅,为有利于作物的生长,要求物的生长,要求A、B两种两种作物作物的间隔不于的间隔不于6垅,则不同的选垅垅,则不同的选垅方法有(方法有()种)种 例例9 9、书架上原来并排放着、书架上原来并排放着5 5本不本不同的书,现要插入三本不同的书,同的书,现要插入三本不同的书,那么不同的插法有多少种?那么不同的插法有多少种?