第一章计数原理复习课(复习课)ppt课件

.,排列组合、二项式定理复习课,.,一、两个原理的区别与联系：,做一件事或完成一项工作的方法数,直接（分类）完成,间接（分步骤）完成,做一件事，完成它可以有n类办法，第一类办法中有m1种不同的方法，第二类办法中有m2种不同的方法，第n类办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+m3+mn种不同的方法,做一件事，完成它可以有n个步骤，做第一步中有m1种不同的方法，做第二步中有m2种不同的方法，做第n步中有mn种不同的方法，那么完成这件事共有N=m1m2m3mn种不同的方法.,.,例1.书架上放有3本不同的数学书,5本不同的语文书,6本不同的英语书,(1)若从这些书中任取一本,有多少种不同的选法?(2)若从这些书中取数学书、语文书、英语书各一本,有多少种不同的选法?(3)若从这些书中取不同科目的书两本,有多少种不同的选法?,.,例2如图，某电子器件是由三个电阻组成的回路,其中有6个焊接点A，B，C，D，E，F，如果某个焊接点脱落，整个电路就会不通。现发现电路不通了,那么焊接点脱落的可能性共有（）63种（B）64种（C）6种（D）36种,分析:由加法原理可知,由乘法原理可知222222-1=63,.,（1）5名同学报名参加4项活动（每人限报1项），共有种不同的报名方法,（2）5名同学争夺4项竞赛冠军，冠军获得者共有种可能,基础练习,.,二、排列和组合的区别和联系：,从n个不同元素中取出m个元素，按一定的顺序排成一列,从n个不同元素中取出m个元素，把它并成一组,所有排列的的个数,所有组合的个数,先选后排只选不排,.,解排列组合问题遵循的一般原则:有序-;无序-2.分类-;分步-3.既有分类又有分步:4.既有排列又有组合:5.先后6.正难7.分类,排列,组合,加法,乘法,先分类再分步,先选后排,要不重不漏,则反,特殊,一般,.,排列组合应用题的常用方法,1、基本原理法,2、特殊优先法,3、捆绑法,4、插空法,5、间接法,6、穷举法,.,1对有约束条件的排列问题，应注意如下类型：某些元素不能在或必须排列在某一位置；某些元素要求连排（即必须相邻）；某些元素要求分离（即不能相邻）；,2基本的解题方法：（）有特殊元素或特殊位置的排列问题，通常是先排特殊元素或特殊位置，称为优先处理特殊元素（位置）法（优先法）；特殊元素,特殊位置优先安排策略,（）某些元素要求必须相邻时，可以先将这些元素看作一个元素，与其他元素排列后，再考虑相邻元素的内部排列，这种方法称为“捆绑法”；相邻问题捆绑处理的策略,（）某些元素不相邻排列时，可以先排其他元素，再将这些不相邻元素插入空挡，这种方法称为“插空法”；不相邻问题插空处理的策略,.,例题：（排队问题）有3名男生和4名女生，若分别满足下列条件，则共有多少种不同的排法？,.,1排成前后两排，前3人后4人：_,解：（多排问题单排法处理）.与无任何限制的排列相同，有种,根据分步计数原理：76543217！5040,.,2甲站在正中间：_,(变式)7位同学站成一排，其中甲不站在首位:,解一：共有A61A66=4320。,解二：共有A61A66=4320。,解三：A77-A66=7A66-A66=4320。,位置分析法,.,方法三：先不考虑特殊计算所有可能，再去掉不符合条件的,用三种方法完成：有3名男生和4名女生，若甲不站在中间也不站在两端，则共有多少种不同的排法？,方法一：先安排特殊位置（中间，两端）,方法二：先安排特殊元素（甲）,3.甲不站在中间也不站在两端，,.,4甲不在排头、乙不在排尾：_,.,5甲、乙必须相邻：_,要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也必须排列.,相邻问题捆绑法,变甲、乙、丙三人都相邻：,.,6甲、乙不能相邻：_,乙,甲,相离问题插空法,元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两端,.,变甲、乙、丙三人都不相邻：_,解：先将其余四个同学排好有A44种方法，此时他们留下五个“空”，再将甲、乙和丙三个同学分别插入这五个“空”有A53种方法，所以一共有A44A531440种,小结：对于不相邻问题，常用“插空法”（特殊元素后考虑）,.,7男女生各站在一起：_,解：将甲、乙、丙三个男同学“捆绑”在一起看成一个元素，另外四个女同学“捆绑”在一起看成一个元素，一共有2个元素，先捆后松一共有排法种数：,（种）.,.,8甲、乙两人之间须相隔人：_,9甲、乙两人中间恰有3人：_,.,10男女各不相邻(即男女相间、4女互不相邻)：_,插空法先排好男生，然后将女生插入其中的四个空位，共有种排法.,.,11甲在乙的右边：_,定序问题比例法,.,12从左到右，4名女生按甲、乙、丙、丁的顺序不变(即只排男生)：_,方法1：(比例法),方法2：设想有7个位置，先将男生排在其中的任意3个位置上，有种排法；余下的4个位置排女生，因为女生的位置已经指定，所以她们只有一种排法.,故本题的结论为（种）.,.,多排问题直排策略,8人排成前后两排,每排4人,其中甲乙在前排,丁在后排,共有多少排法,解:8人排前后两排,相当于8人坐8把椅子,可以把椅子排成一排.,一般地,元素分成多排的排列问题,可归结为一排考虑,再分段研究.,.,二、注意区别“恰好”与“至少”,例：从6双不同颜色的手套中任取4只，其中恰好有一双同色的手套的不同取法共有（）(A)480种（B）240种（C）180种（D）120种,解：,.,练习：从6双不同颜色的手套中任取4只，其中至少有一双同色手套的不同取法共有_种,解：,.,例16本不同的书，按下列要求各有多少种不同的选法：（1）分给甲、乙、丙三人，每人2本；,例题解读：,解：（1）根据分步计数原理得到：,种,分配问题,.,解析：(2)分给甲、乙、丙三人，每人两本有种方法，这个过程可以分两步完成：第一步分为三份，每份两本，设有x种方法；第二步再将这三份分给甲、乙、丙三名同学有种方法根据分步计数原理所以,可得：,例題解读：,因此，分为三份，每份两本一共有15种方法,所以,平均分成m组要除以,.,例16本不同的书，按下列要求各有多少种不同的选法：,（3）分为三份，一份1本，一份2本，一份3本；（4）分给甲、乙、丙三人，一人1本，一人2本，一人3本；,解：（3）这是“不均匀分组”问题，一共有种方法,（4）在（3）的基础上再进行全排列，所以一共有种方法,例题解读：,.,例16本不同的书，按下列要求各有多少种不同的选法：（5）分给甲、乙、丙三人，每人至少1本,解：（5）可以分为三类情况：,“2、2、2型”的分配情况，有种方法；,“1、2、3型”的分配情况，有种方法；,“1、1、4型”，有种方法，,所以，一共有90+360+90540种方法,例题解读：,多个分给少个时，采用先分组再分配的策略,.,1将13个球队分成3组,一组5个队,其它两组4个队,有多少分法？,2.某校高二年级共有六个班级，现从外地转入4名学生，要安排到该年级的两个班级且每班安排2名，则不同的安排方案种数为_,.,环排问题线排策略,例6.5人围桌而坐,共有多少种坐法?,解：围桌而坐与坐成一排的不同点在于，坐成圆形没有首尾之分，所以固定一人A并从此位置把圆形展成直线其余4人共有_种排法即,（5-1)！,一般地,n个不同元素作圆形排列,共有(n-1)!种排法.如果从n个不同元素中取出m个元素作圆形排列共有,.,练习题,6颗颜色不同的钻石，可穿成几种钻石圈,60,设六颗颜色不同的钻石为a,b,cd,e,f.与围桌而坐情形不同点是a,b,c,d,e,f与f,e,d,c,b,a在围桌而坐中是两种排法，即在钻石圈中只是一种排法,即把钻石圈翻到一边,所求数为：(61)!/260,要考虑“钻石圈”可以翻转的特点,.,混合问题，先“组”后“排”,例对某种产品的6件不同的正品和4件不同的次品,一一进行测试，至区分出所有次品为止，若所有次品恰好在第5次测试时全部发现,则这样的测试方法有种可能？,解：由题意知前5次测试恰有4次测到次品，且第5次测试是次品。故有：种可能。,.,练习：1、某学习小组有5个男生3个女生，从中选3名男生和1名女生参加三项竞赛活动，每项活动至少有1人参加，则有不同参赛方法_种.,解：采用先组后排方法:,2、3名医生和6名护士被分配到3所学校为学生体检,每校分配1名医生和2名护士,不同的分配方法共有多少种?,解法一：先组队后分校（先分堆后分配）,解法二：依次确定到第一、第二、第三所学校去的医生和护士.,.,小集团问题先整体局部策略,例9.用1,2,3,4,5组成没有重复数字的五位数其中恰有两个偶数夹1,这两个奇数之间,这样的五位数有多少个？,解：把,当作一个小集团与排队共有_种排法，再排小集团内部共有_种排法，由分步计数原理共有_种排法.,小集团排列问题中，先整体后局部，再结合其它策略进行处理。,.,.计划展出10幅不同的画,其中1幅水彩画,幅油画,幅国画,排成一行陈列,要求同一品种的必须连在一起，并且水彩画不在两端，那么共有陈列方式的种数为_,2.5男生和女生站成一排照像,男生相邻,女生也相邻的排法有_种,.,正难则反总体淘汰策略,例11.从0,1,2,3,4,5,6,7,8,9这十个数字中取出三个数，使其和为不小于10的偶数,不同的取法有多少种？,解：这问题中如果直接求不小于10的偶数很困难,可用总体淘汰法。,再淘汰和小于10的偶数共_,符合条件的取法共有_,9,+,有些排列组合问题,正面直接考虑比较复杂,而它的反面往往比较简捷,可以先求出它的反面,再从整体中淘汰.,.,我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种?,练习题,.,实际操作穷举策略,例15.设有编号1,2,3,4,5的五个球和编号1,23,4,5的五个盒子,现将5个球投入这五个盒子内,要求每个盒子放一个球，并且恰好有两个球的编号与盒子的编号相同,.有多少投法,解：从5个球中取出2个与盒子对号有_种还剩下3球3盒序号不能对应，,.,十五.实际操作穷举策略,例15.设有编号1,2,3,4,5的五个球和编号1,23,4,5的五个盒子,现将5个球投入这五个盒子内,要求每个盒子放一个球，并且恰好有两个球的编号与盒子的编号相同,.有多少投法,解：从5个球中取出2个与盒子对号有_种还剩下3球3盒序号不能对应，,同理3号球装5号盒时,4,5号球有也只有1种装法,由分步计数原理有2种,.,对于条件比较复杂的排列组合问题，不易用公式进行运算，往往利用穷举法或画出树状图会收到意想不到的结果,练习题,同一寝室4人,每人写一张贺年卡集中起来,然后每人各拿一张别人的贺年卡，则四张贺年卡不同的分配方式有多少种？,(9),.,例：如图,要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？,涂色问题,.,解法一:按地图A、B、C、D四个区域依次分四步完成,第一步,m1=3种,第二步,m2=2种,第三步,m3=1种,第四步,m4=1种,所以根据乘法原理,得到不同的涂色方案种数共有N=3211=6种。,解法二:3种颜色4块区域，则肯定有两块同色，只能A、D同色，把它们看成一个整体元素，所以涂色的方法有：,.,例3：如图,要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种,允许同一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？,若用2色、4色、5色等,结果又怎样呢？,涂色问题,.,4、某城市在中心广场建造一个花圃，花圃分为6个部分（如右图）现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有_种.（以数字作答）,所以，共有48+48+24=120种.,解法：从题意来看6部分种4种颜色的花，又从图形看知必有2组同颜色的花，从同颜色的花入手分类求,（2）与同色，则或同色，所以共有=48种；,（3）与且与同色，则共=24种,（1）与同色，则也同色或也同色，所以共有=48种；,.,六、分清排列、组合、等分的算法区别,例1:(1)今有10件不同奖品,从中选6件分给甲一件,乙二件和丙三件,有多少种分法?(2)今有10件不同奖品,从中选6件分给三人,其中1人一件1人二件1人三件,有多少种分法?(3)今有10件不同奖品,从中选6件分成三份,每份2件,有多少种分法?,解：（1）,（2）,(3),.,练习.在今年国家公务员录用中，某市农业局准备录用文秘人员二名，农业企业管理人员和农业法制管理人员各一名，报考农业局公务人员的考生有10人，则可能出现的录用情况有_种（用数字作答）。,解法1:,解法2:,.,七、分类组合,隔板处理,例:从6个学校中选出30名学生参加数学竞赛,每校至少有1人,这样有几种选法?,分析:问题相当于把个30相同球放入6个不同盒子(盒子不能空的)有几种放法?这类问可用“隔板法”处理.解:采用“隔板法”得:,小结：把n个相同元素分成m份每份,至少1个元素,问有多少种不同分法的问题可以采用“隔板法”得出共有种.,.,元素相同问题隔板策略,例.有10个运动员名额，再分给7个班，每班至少一个,有多少种分配方案？,解：因为10个名额没有差别，把它们排成一排。