《计数原理-拔高难度-讲义》由会员分享,可在线阅读,更多相关《计数原理-拔高难度-讲义(11页珍藏版)》请在金锄头文库上搜索。
1、计数原理知识讲解一、基本计数原理1. 加法原理分类计数原理:做一件事,完成它有n类办法,在第一类办法中有籍种不同的方法,在第 二类办法中有m2种方法 在第n类办法中有mn种不同的方法.那么完成这件事共有 N = m1 + m2 + + m种不同的方法.又称加法原理.2. 乘法原理分步计数原理:做一件事,完成它需要分成n个子步骤,做第一个步骤有m1种不同的方法, 做第二个步骤有m2种不同方法,做第n个步骤有mn种不同的方法.那么完成这件事 共有N = m1 x m2 x x m种不同的方法.又称乘法原理.3. 加法原理与乘法原理的综合运用如果完成一件事的各种方法是相互独立的,那么计算完成这件事的
2、方法数时,使用分类 计数原理.如果完成一件事的各个步骤是相互联系的,即各个步骤都必须完成,这件事才完 成,那么计算完成这件事的方法数时,使用分步计数原理.注:分类计数原理、分步计数原理是推导排列数、组合数公式的理论基础,也是求解排列、组合问题的基本思想方法,这两个原理十分重要必须认真学好,并正确地灵活加以应用.典型例题一,选择题(共1小题)1( 2018蚌埠三模)4名大学生到三家企业应聘,每名大学生至多被一家企业 录用,则每家企业至少录用一名大学生的情况有()A . 24 种 B . 36 种 C . 48 种 D . 60 种【解答】解:分两类,第一类,有3名被录用,有=24种,第二类,4名
3、都被 录用,则有一家录用两名,有=36 ,根据分类计数原理,共有24+36=60 (种)故选:D .二,填空题(共1小题)2 . ( 2018梅州二模)某校开设10门课程供学生选修,其中A、B、C三门由于 上课时间相同,至多选一门,学校规定,每位同学选修三门,则每位同学不同的 选修方案种数是98 .【解答】解:.A , B , C三门由于上课时间相同,至多选一门,第一类A , B , C三门课都不选,有C73=35种方案; 第二类A , B , C中选一门,剩余7门课中选两门,有C31C72=63种方案. .根据分类计数原理知共有35+63=98种方案.故答案为:98 .三,解答题(共9小题)
4、3 ( 2018春南阳期末)如图所示,在以AB为直径的半圆周上,有异于A , B的六个点C ,C,C,直径AB上有异于A,B的四个点D ,D ,D ,D,则: 1261234(1 )以这12个点(包括A, B )中的4个点为顶点,可作出多少个四边形?(2 )以这10个点(不包括A,B)中的3个点为顶点,可作出多少个三角形? 其中含点c1的有多少个?【解答】解:(1)构成四边形,需要四个点,且无三点共线,可以分成三类: 四个点从C,C,C中取出,有C 4个四边形;1266 三个点从C,C,C中取出,另一个点从D,D,D,D,A,B中取出,1261234有C63C61个四边形; 二个点从C,C,C
5、中取出,另外二个点从D,D,D,D,A,B中取1261234出,有C62C62个四边形.故满足条件的四边形共有N=C64+C63C61+C62C62=360 (个).(2 )类似于(1 )可分三种情况讨论得三角形个数为C63+C61C42+C62C41=116(个). 其中含点 C1 的有 C52+C51C41+C42=36 (个).4 . ( 2018江苏)设 n N*,对 1,2,.,n 的一个排歹U i i .i,如果当 sVt 1 2 n时,有ii,则称(i,i )是排列i i .i的一个逆序,排列i i .i的所有逆 s ts t12 n12 n序的总个数称为其逆序数.例如:对1,2
6、,3的一个排列231,只有两个逆序(2, 1)(3, 1),则排列231的逆序数为2 .记fn ( k )为1,2,n的所有排列中 逆序数为k的全部排列的个数.(1)求七(2),七(2 )的值;(2 )求(2 ) ( nN5 )的表达式(用n表示).【解答】解:(1 )记M abc )为排列abc得逆序数,对1 , 2 , 3的所有排列,有M 123 ) =0 , M 132 ) =1 , M 231 ) =2 , M 321 ) =3 ,.f (0)=1, f (1)=f (2)=2, 333对1, 2,3,4的排列,利用已有的1,2,3的排列,将数字4添加进去,4在新排列中的位置只能是最后
7、三个位置.因此,f (2)=f (2)+f (1)+f ( 0 ) =5 ;4333(2 )对一般的n ( n N4 )的情形,逆序数为0的排列只有一个:12.n , .L(0 )=1.逆序数为1的排列只能是将排列12.n中的任意相邻两个数字调换位置得到的排列,(1 ) =n - 1 .为计算fn+1 ( 2 ),当1,2,n的排列及其逆序数确定后,将n+1添加进原排列,n+1在新排列中的位置只能是最后三个位置.因此,f (2) =f (2) +f (1)+f (0)=f ( 2 ) +n .n+1nnnn当 nN5 时,f ( 2 ) =f (2)-f ( 2 ) : +f(2)-f ( 2
8、 ) +.+ f ( 2 )nnn - 1n - 1n - 25-f4 ( 2 ) +七(2 )= (n-1) + (n-2) +.+4+f4 ( 2 )=因此,当 nN5 时,fn(2)=.5 .( 2017秋涞水县校级期中)有甲、乙、丙、丁、戊5位同学,求:(1) 5位同学站成一排,有多少种不同的方法?(2 ) 5位同学站成一排,要求甲乙必须相邻,丙丁不能相邻,有多少种不同的 方法?(3)将5位同学分配到三个班,每班至少一人,共有多少种不同的分配方法? 【解答】解:(1)5位同学站成一排共有=120 .(2) 5位同学站成一排,要求甲乙必须相邻,丙丁不能相邻,先用捆绑排甲乙,再和戊全排,形
9、成3个空,插入丙丁即可.故有=24 .(3 )人数分配方式有3 , 1 , 1有=60种方法2 , 2 , 1有=90种方法所以,所有方法总数为60+90=150种方法.6 .( 2017春 宁江区校级期中)三个女生和五个男生排成一排.(1 )如果女生须全排在一起,有多少种不同的排法?(2 )如果女生必须全分开,有多少种不同的排法?(3) 如果两端都不能排女生,有多少种不同的排法?(4 )如果男生按固定顺序,有多少种不同的排法?(5 )如果三个女生站在前排,五个男生站在后排,有多少种不同的排法?【解答】解:(1 )女须全排在一起,把3个女生捆绑在一起看做一个复合元素, 再和5个男生全排,故有A
10、33A66=4320种;(2 )女生必须全分开,先排男生形成了6个空中,插入3名女生,故有A55A63=14400 种;(3 )两端都不能排女生,从男生中选2人排在两端,其余的全排,故有A52A66=14400 种;(4 )男生按固定顺序,从8个位置中,任意排3个女生,其余的5个位置男生 按照固定顺序排列,故有气3=336种,(5)三个女生站在前排,五个男生站在后排,气3气5=720种7 . ( 2016东城区一模)现有两个班级,每班各出4名选手进行羽毛球的男单、 女单、男女混合双打(混双)比赛(注:每名选手打只打一场比赛).根据以往 的比赛经验,各项目平均完成比赛所需时间如表所示,现只有一块
11、比赛场地,各(II )求第三场比赛平均需要等待多久才能开始进行;(III )若要使所有参加比赛的人等待的总时间最少,应该怎样安排比赛顺序(写 出结论即可).【解答】解:(I )三场比赛共有种方式,其中按按女单、混双、男单的顺序进行比赛只有1种,所以按女单、混双、男单的顺序进行比赛的概率为(II )令A表示女单比赛、B表示男单比赛、C表示混双比赛.按ABC顺序进行比赛,第三场比赛等待的时间是:t1=20+25=45 (分钟).按ACB顺序进行比赛,第三场比赛等待的时间是:亍20+35=55 (分钟).按BAC顺序进行比赛,第三场比赛等待的时间是:顼20+25=45 (分钟).按BCA顺序进行比赛
12、,第三场比赛等待的时间是:匕=35+25=60 (分钟).按CAB顺序进行比赛,第三场比赛等待的时间是:35+20=55 (分钟).按CBA顺序进行比赛,第三场比赛等待的时间是: t6=35+25=60 (分钟).且上述六个事件是等可能事件,每个事件发生概率为-,所以平均等待时间为/(III)按照比赛时间从长到短的顺序参加比赛,可使等待的总时间最少8 .( 2016春秀英区校级期末)6男4女站成一排,求满足下列条件的排法共有 多少种?(只列式,不需计算结果)(1 )任何2名女生都不相邻有多少种排法?(2 )男甲不在首位,男乙不在末位,有多少种排法?(3 )男生甲、乙、丙排序一定,有多少种排法?
13、(4)男甲在男乙的左边(不一定相邻)有多少种不同的排法?【解答】解:(1 )任何两个女生都不得相邻,利用插空法,故有A66A74种.(2 )男甲不在首位,男乙不在末位,利用间接法,故有A1010 - 2A99+A88种,(3 )男生甲、乙、丙顺序一定,利用定序法,一=A107种,(4 )由于男甲要么在男乙的左边,要么在男乙的右边,所以男甲在男乙的左边(不一定相邻)-A1010 .9 .( 2016春九龙坡区校级期中)已知一个袋内有5只不同的红球,6只不同的 白球.(1 )从中任取4只球,红球的只数不比白球少的取法有多少种?(2 )若取一只红球记2分,取一只白球记1分,从中任取5只球,使总分不小
14、于7分的取法有多少种?(3)在(2 )条件下,当总分为8时,将抽出的球排成一排,仅有两个红球相邻的排法种数是多少?【解答】解:(1 )将取出4个球分成三类情况: 取4个红球,没有白球,C54种; 取3个红球1个白球,C53C61种; 取2个红球2个白球,C52C62种,.C54+C53C61+C52C62=215 种,(2) 设x个红球y个白球,或 或 .符合题意的取法种数有C52C63+C53C62+C54C61=381种.(3 )总分为8分,则抽取的个数为红球3个,白球2个,将抽出的球排成一排,仅有两个红球相邻,第一步先取球,共有C53C62=150种,第二步,再排,先选2个红球捆绑在一起
15、,再和另外一个红球排列,把2个白球插入,共有Xf根据分步计数原理可得,150X72=10800 .10 . ( 2016春江阴市期中)将5个编号为1 , 2 , 3 , 4 , 5的小球放入5个编号 为1 , 2 , 3 , 4 , 5的盒子中.(1 )有多少种放法?(2) 每盒至多一球,有多少种放法?(3 )恰好有一个空盒,有多少种放法?(4 )每个盒内放一个球,并且恰好有一个球的编号与盒子的编号相同,有多少 种方法?(5 )每个盒子内投放一球,并且至少有两个球的编号与盒子编号是相同的,有 多少种投放方法?(6)把5个不同的小球换成5个相同的小球,恰有一个空盒,有多少种不同的 放法?(注意:以上各小题要列出算式后再求值,否则扣分.)【解答】解:(1 )本题要求把小球全部放入盒子,.1号小球可放入任意一个盒子内,有5种放法.同理,2、3、4 , 5号小球也各有5