排列组合综合应用课件大习题课

排列组合综合应用知识梳理1．排列(1)定义：从n个不同元素中任取m(m≤n)个元素，排成一列，叫做从n个不同元素中取出m个元素的一个排列．(2)排列数定义：从n个不同元素中取出m(m≤n)个元素的的个数，叫做从n个不同元素中取出m个元素的排列数，用符号表示．(3)排列数公式：n，m∈N*，m≤n，Amn＝＝n！n－m！.按照一定的顺序所有排列Amnn(n－1)(n－2)…(n－m＋1)(4)全排列：n个不同元素全部取出的一个排列，叫做n个不同元素的一个全排列，Ann＝＝，规定0！＝.2．组合(1)定义：从n个不同元素中，任意取出m(m≤n)个元素合成一组，叫做从n个不同元素中取出m个元素的一个组合．(2)组合数：从n个不同元素中任取m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中任意取出m个元素的组合数，用符号表示．(3)组合数公式：Cmn＝AmnAmm＝＝，Cmnnn－1n－2…n－m＋1mm－1…3·2·1n！n－m！m！n·(n－1)(n－2)·…·3·2·1n！1n，m∈N*，m≤n.由于0！＝，所以C0n＝.3．组合数的性质(1)Cmn＝.(2)Cmn＋1＝＋.11Cn－mnCmnCm－1n典型题型例1：用0、1、2、3、4五个数字组成无重数字的四位数，则在这些四位数中，（1）偶数有多少个？（2）被3整除的数有多少个？排数问题23131234AAAA解：432032103、、、；、、、整除情形：解：和能被33132AA共有变式题用0～9这十个数字组成没有重复数字的正整数．(1)共有几个三位数？(2)末位数字是4的三位数有多少？(3)求所有三位数的和；(4)四位偶数有多少？(5)比5231大的四位数有多少？【解答】(1)百位不能为“0”，因此共有A19·A29＝648个；(2)末位为4，百位不能为“0”，因此共有A18·A18＝64个．(3)考虑各数位上的数字之和，可得所有三位数的和为：A18A18(1＋2＋…＋9)＋A18A18(1＋2＋…＋9)×10＋A29(1＋2＋…9)×100＝355680.(4)分末位数字是否为0两种情况考虑．A39＋A14A18A28＝2296种；(5)①千位上为9,8,7,6的四位数各有A39个；②千位上是5，百位上为3,4,6,7,8,9的四位数各有A28个；③千位上是5，百位上为2，十位上为4,6,7,8,9的四位数各有A17个；④千位上是5，百位上为2，十位上为3且满足要求的共有5个，因此共有N＝4A39＋6A28＋5A17＋5＝2392种．排人问题例2：4个男孩3个女孩，站成一排照相留念。1)若三个女孩要站在一起，有多少种不同的排法？5533.AA解：2)若三个女孩要站在一起，四个男孩也要站在一起，有多少种不同的排法？288..224433AAA解：3)若三个女孩互不相邻，四个男孩也互不相邻，有多少种不同的排法？1443344AA解：例2：4个男孩3个女孩，站成一排照相留念。4)A、B小孩必须相邻，且C、D小孩不能相邻有多少种不同的排法？254422..AAA解：5)若其中A、B、C小孩有自己的顺序，有多少种不同的排法？472A：解例2：4个男孩3个女孩，站成一排照相留念。3377AA解1：问：若A、B、C三个小孩按从高到矮的顺序站，有多少种不同的排法？2.3377AA解：6）若前排站三人，后排站四人，其中的A、B两小孩必须站前排且相邻，有多少种不同的排法？55222AA解：例2：4个男孩3个女孩，站成一排照相留念。问：若7个座位3个孩子去坐，要求每个孩子的旁边都有空位置，有多少种不同的排法？搬凳子插入）解：(33A例3：（1）6本不同的书分给5名同学每人一本，有多少种不同分法？（2）5本相同的书分给6名同学每人至多一本，有多少种不同的分法？（3）6本不同的书全部分给5名同学每人至少一本，有多少种不同的分法？分配问题56A56C5526AC变式题有6本不同的书按下列分配方式分配，问共有多少种不同的分配方式？(1)分成1本、2本、3本三组；(2)分给甲、乙、丙三人，其中一个人1本，一个人2本，一个人3本；(3)分成每组都是2本的三个组；(4)分给甲、乙、丙三人，每个人2本．【解答】(1)分三步：先选1本有C16种选法；再从余下的5本中选2本有C25种选法；最后余下的3本全选有C33种选法，由分步计数原理知，分配方式共有：C16·C25·C33＝60(种)．(2)由于甲、乙、丙是不同的三个人，在(1)题的基础上，还在考虑再分配问题．因此分配方式共有：C16·C25·C33·A33＝360(种)．(3)先分三步，则应是C26·C24·C22种方法，但是这里面出现了重复．不妨记六本书为A、B、C、D、E、F.若第一步取了AB，第二步取了CD，第三步取了EF，记该种分法为(AB，CD，EF)，则C26·C24·C22种分法中还有(AB，EF，CD)、(CD，AB，EF)、(CD，EF，AB)、(EF，CD，AB)、(EF，AB，CD)，共A33种情况．而且这A33种情况仅是AB，CD，EF的顺序不同．因此只能作为一种方法．故分配方式有：C26·C24·C22A33＝15(种)．(4)在问题(3)的基础上再分配即可，共有分配方式：C26·C24·C22A33·A33＝C26·C24·C22＝90(种)．注：1.非均匀分组，，只需依次取出相应元素即可2.均匀分成m组，由于出现重复现象，故需除以3.部分均匀分组，也会出现重复现象，有k部分均匀，就除以mmAkkA（5）分给甲乙丙丁四人，其中二人各一本，二人各二本442222122426AAACCC例3：（6）7名志愿者中安排6人在周六、周日两天参加社会公益活动，若每天安排3人，者有多少种不同的安排方法？34371CC：解分配问题22223437).(2AACC：解例3：（7）将5名实习教师分配到高一年级的3个班实习，每个班至少1名，最多2名，则不同的分配方案有多少？分配问题90).(33222325AACC解：例4：（1）7个相同的小球，任意放入4个不同的盒子中，每个盒子至少有1个小球的不同放法有多少种？分配问题解：将7个小球用3块隔板分成4份但盒子又不能空隔板法3667C有不同方法数个空隙个小球有解：相同(2)7个相同的小球放入到4个相同的盒子，每个盒子至少放一个球变式：分：（1，1，1，4）；（1，1，2，3）；（1，2，2，2）共3种。（3）7个不同的小球放入到4个相同的盒子，33222426172212243747ACCCCACCCC（4）7个不同的小球放入到4个不同的盒子，4433222426172212243747)(AACCCCACCCC分配问题相同元素的分配问题：隔板法不同元素的分配问题：先组后排，注意分清—均匀分组，非均匀分组，部分均匀分组例4：（2）7个相同的小球，任意放入4个不同的盒子中，共有多少种不同的方法？分配问题解：相当于将7个小球用3块隔板分成4份隔板法3101037C共有不同方法数隔板数小球数解：例5：四面体的一个顶点是A，从其它顶点和各棱中点中取3个点，使他们和点A在同一个平面上，则共有多少种不同的取法？组图形问题3335C解：1.每个侧面上的2.顶点A与底面三线中线构成的三角形例6：四面体的顶点和各棱中点共10个点，从中任取4个不共面的点，有多少种不同的取法？组图形问题)634(46410CC解：1.四个侧面2.各棱中点构成的平行四边形3.顶点与对面中线构成的三角形例7：用正方体的8个顶点共可以组成多少个不同的四面体？组图形问题)66(4448CC解：1.6个侧面2.6个对角面例8：10双不相同的鞋子混装在一只口袋中，从中任取4只，试求符合下列各种情形的方法数？先成双后成单3360.112121212410CCCCC：解210C解：3360...244114116118120ACCCC：解（1）4只鞋子恰成两双；(2)4只鞋子没有成双；（3）4只鞋子中有2只成双，另外2只不成双;1140.121229110CCCC解：例9：8名外交工作者，其中3人只会英语，2人只会日语，3人既会英语又会日语，现从则8人中选3个会英语，3个会日语的人去完成一项任务，有多少种不同的选法？3333342312351322.).().(CCCCCCCC解：选人问题分三类：1.从多面手中选一人作为日语2.从多面手中选二人作为日语3.从多面手中选三人作为日语例10：将三种不同农作物种植在下面五块土地上，要求相邻区域不种同一作物，则有多少种不同的种植方案？42)322(231：解种植问题种共有；；，；；，；；；；，；；，；；，；；块地块地转化为：将解42A73,52,411,42,532,41,533,42,515,42,314,52,3142,3,513523312345例11：给下面的5个行政区域涂色，要求相邻区域不同色，现有4种颜色可供选择，问共有多少种不同的涂色方案？涂色问题23154种）共有种颜色涂色有：）用种颜色涂色有：）用解：分两类完成(7242314412333444123334ACACACAC问：用4种颜色给下面的5个行政区域涂色，要求相邻区域不同色，问共有多少种不同的涂色方案？点评：据不相邻区域按颜色分类例12：在下面的电路图中求相应的控制方法数？电路问题AB(3)：A、B至少有一个正常工作？(1)：用电器A正常工作？(2)：用电器B正常工作？例13（1）某城市的街区由12个全等的矩形区组成其中实线表示马路，从A走到B的最短路径有多少种？BA3735C最短路问题例13（2）1建筑工人从类似于×3的长方体框架的A点到达点B，每步走一个单位，且向上不能连续攀登，求他行走的最短路线共有多少？最短路问题AB5253726CC第一步走完下面4×2的矩形框,第二步向上攀登,相当于在6个空位中插入不相邻的三个元素例14：将4个不同的小球放到编号为1、2、3、4的4个盒子中，则恰好有一个空盒子的方法有多少种？332414..ACC解：混合问题问：恰有两个盒子不放小球的方法有多少种？22222224331424).(AACCCCC解：例15：从5男3女中选5人担任5门不同学科的课代表，求符合下列条件的不同选法？5535234513).(ACCCC解：综合问题（1）有女生担人数必须少于男生；（2）男生只能担任数学化学物理课代表；233335332325..AACAAC解：例16：3张卡片正反面分别写着数字0与1、3与4、5与6，将三张卡片并排组成三位数，共可以组成多少个不同的三位数？综合问题22121233121212..ACCACCC解：规律总结1．排列与组合的本质区别在于排列不仅取而且排，即与顺序有关，而组合只取出并成一组即可，与顺序无关．2．注意排列数公式、组合数公式有连乘形式与阶乘形式两种公式，Amn＝n(n－1)·…·(n－m＋1)，Cmn＝nn－1n－2…n－m＋1m！常用于计算，而公式Amn＝n！n－m！，Cmn＝n！m！n－m！常用于证明恒等式．(3)代入古典概型的概率计算公式3．解排列组合题的“16字方针，12个技巧”：(1)“16字方针”是解排列组合题的基本规律，即分类相加、分步相乘、有序排列、无序组合．(2)“12个技巧”是速解排列组合题的捷径．即①相邻问题捆绑法；②不相邻问题插空法；③多排问题单排法；④定序问题倍缩法；⑤定位问题优先法；⑥有序分配问题分步法；⑦多元问题分类法；⑧交叉问题集合法；⑨至少(或至多)问题间接法；⑩选排问题先取后排法；⑾局部与整体问题排除法；⑿复杂问题转化法．4．求解排列与组合的综合应用题，注意先选后排的原则．复杂的排列、组合问题利用分类思想转化为简单问题求解是最佳途径．通常有三条途径：(1)以元素为分析对象，先满足特殊元素的要求，再考虑其他元素，即优元法；(2)以位置为分析对象，即先满足特殊位置的要求，