排列与组合复习2.ppt

《排列与组合复习2.ppt》由会员分享，可在线阅读，更多相关《排列与组合复习2.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排列与组合复习排列与组合复习内蒙古第二地质中学内蒙古第二地质中学例例56本不同的书，按下列要求各有多少种不同的选法：本不同的书，按下列要求各有多少种不同的选法：（1）分给甲、乙、丙三人，每人）分给甲、乙、丙三人，每人2本；本；（2）分为三份，每份）分为三份，每份2本；本；解：解：（1 1）根据分步计数原理得到：）根据分步计数原理得到：种；种；（2 2）分给分给甲、乙、丙三人，每人两本有甲、乙、丙三人，每人两本有 种方法，种方法，这个过程可以分两步完成：第一步分为三份，每份两本，设有这个过程可以分两步完成：第一步分为三份，每份两本，设有x种方法；第二步再将这三份分给甲、乙、丙三名同学有种方法；第

2、二步再将这三份分给甲、乙、丙三名同学有 种种方法根据分步计数原理可得：方法根据分步计数原理可得：x 种方法种方法，所以所以X =即即:因此，分为三份，每份两本一共有因此，分为三份，每份两本一共有15种方法。种方法。说明：本题是分组中的说明：本题是分组中的“均匀分组均匀分组”问题问题 一般地：将一般地：将mn个元素均匀分成个元素均匀分成n组组（每（每组组m个元个元素），素），共有共有:种方法。种方法。(3）分为三份，一份）分为三份，一份1本，一份本，一份2本，一份本，一份3本；本；（4）分给甲、乙、丙三人，一人）分给甲、乙、丙三人，一人1本，一人本，一人2本，一人本，一人3本；本；(3(3）这是

3、）这是“不均匀分组不均匀分组”问题，共有问题，共有 种方法种方法 （4 4）在（）在（3 3）的基础上再进行全排列，）的基础上再进行全排列，所以共有所以共有 种方法种方法例例56本本不不同同的的书书，按按下下列列要要求求各各有有多多少少种种不不同同的的选选法：法：（5）分给甲、乙、丙三人，每人至少）分给甲、乙、丙三人，每人至少1本。本。解解:可以分为三类情况：可以分为三类情况：“2、2、2型型”即（即（1 1）中的分配情况，）中的分配情况，有有 种方法；种方法；“1、2、3型型”即（即（4 4）中的分配情况）中的分配情况,有有 种方法；种方法；“1、1、4型型”，有，有 种方法，种方法，所以，

4、一共有所以，一共有90+360+90540种方法种方法例例6马路上有编号为马路上有编号为1，2，3，10的十盏路灯，为节约的十盏路灯，为节约用电又不影响照明，可以把其中用电又不影响照明，可以把其中3盏灯关掉，但不可以同时关盏灯关掉，但不可以同时关掉相邻的掉相邻的两盏或三盏，两盏或三盏，在在两端的灯都不能关掉两端的灯都不能关掉的情况下，有多的情况下，有多少种不同的关灯方法？少种不同的关灯方法？解解：（插插空空法法）本本题题等等价价于于在在7只只亮亮着着的的路路灯灯之之间间的的6个空档中插入个空档中插入3只熄掉的灯，只熄掉的灯，故所求方法总数为故所求方法总数为 种方法。种方法。例例7某考生打算从某

5、考生打算从7 7所重点大学中选所重点大学中选3 3所填在第一档次的所填在第一档次的3 3个个志愿栏内，其中志愿栏内，其中A A校定为第一志愿；再从校定为第一志愿；再从5 5所一般大学中选所一般大学中选3 3所所填在第二档次的三个志愿栏内，其中填在第二档次的三个志愿栏内，其中B B、C C两校必选，且两校必选，且B B在在C C前。前。问：此考生共有多少种不同的填表方法？问：此考生共有多少种不同的填表方法？解：解：先填第一档次的三个志愿栏：因先填第一档次的三个志愿栏：因A A校定为第一档校定为第一档次的第一志愿，故第一档次的二、三志愿次的第一志愿，故第一档次的二、三志愿有有 种种填法；再填第二档

6、次的三个志愿栏：填法；再填第二档次的三个志愿栏：B B、C C两校两校有有 种种填法，剩余的一个志愿栏填法，剩余的一个志愿栏有有 种种填法。由分步计填法。由分步计数原理知，此考生不同的填表方法数原理知，此考生不同的填表方法 共有共有 （种）。（种）。A例例8 8如如图图是是由由1212个个小小正正方方形形组组成成的的3 34 4矩矩形形网网格格，一一质质点点沿沿网网格格线线从从A A点点到到B B点点的的不不同同路路径径之之中中，最最短短路径有路径有_条条?AB解解：总总揽揽全全局局：把把质质点点沿沿网网格格线线从从点点A A到到点点B B的的最最短短路路径径分为七步，分为七步，其其中中四四步

7、步向向右右，三三步步向向下下，不不同同走走法法的的区区别别在在于于哪哪三三步步向向下下，每每一一种种走走法法对对应应着着从从7 7步中取出步中取出3 3步的一个组合步的一个组合;因此，本题的结论是：因此，本题的结论是：变式变式1有有10级楼梯级楼梯,恰好恰好8步上完步上完,每步只能上每步只能上1级或级或2级级,问问:有多少种不同的走法？有多少种不同的走法？分析分析:由题设易知由题设易知:8步中恰好有步中恰好有2步走步走2级级,其余其余6步各走步各走1级级;因而因而,每一种走法对应每一种走法对应着从着从8步中取出步中取出2步的步的一个一个组合组合:故有故有:C8 种不同的走法？种不同的走法？2变

8、式变式2圆周上有圆周上有12个不同的点，过其中任意两点作弦，这些个不同的点，过其中任意两点作弦，这些弦在圆内的交点个数最多是多少？弦在圆内的交点个数最多是多少？解解：要要使使交交点点个个数数最最多多，则则只只需需所所有有的的交交点点都都不不重重合合。显显然然，并并不不是是每每两两条条弦弦都都在在圆圆内内有有交交点点，但但如如果果两两条条弦弦相相交交，则则交交点点就就是是以以这这两两条条弦弦的的四四个个端端点点为为顶顶点点的的四四边边形形的的对对角角线线的的交交点点，也也就就是是说说，弦弦在在圆圆内内的的交交点点与与以以圆圆上上四四点点为为顶顶点点的的四四边边形形是是一一一一对对应应的。的。因此

9、只需求以圆上四点为顶点的四边因此只需求以圆上四点为顶点的四边形的个数，即形的个数，即 个个.例例9有有10只只不不同同的的试试验验产产品品，其其中中有有4只只次次品品，6只只正正品品，现现每每次次取取一一只只测测试试，直直到到4只只次次品品全全测测出出为为止止，求求最最后后一一只只次次品品正正好在第五次测试时被发现好在第五次测试时被发现的不同情形有多少种？的不同情形有多少种？解：解：本本题题的的实质实质是，前五次是，前五次测试测试中有中有1只正品，只正品，4只次品，且第只次品，且第五次五次测试测试的是次品的是次品 思路一思路一：设想有五个位置，先从设想有五个位置，先从6 6只正品中任选只正品中

10、任选1 1只，只，放在前四个位置的任一个上，有放在前四个位置的任一个上，有 种方法；再种方法；再把把4 4只次品在剩下的四个位置上任意排列，只次品在剩下的四个位置上任意排列，有有 种种排法。排法。故不同的情形共有故不同的情形共有 种种4次品次品6 正正 品品 1 2 3 4 5 .例例9有有10只只不不同同的的试试验验产产品品，其其中中有有4只只次次品品，6只只正正品品，现现每每次次取取一一只只测测试试，直直到到4只只次次品品全全测测出出为为止止，求求最最后后一一只只次次品品正正好在第五次测试时被发现的不同情形有多少种？好在第五次测试时被发现的不同情形有多少种？解：解：本本题题的的实质实质是，

11、前五次是，前五次测试测试中有只正品，只次品，且第五中有只正品，只次品，且第五次次测试测试的是次品的是次品 思路二思路二：设想有五个位置，先从设想有五个位置，先从4 4只次品中任选只次品中任选1 1只，只，放在第五个位置上，有放在第五个位置上，有 种方法；再种方法；再从从6 6只正品中只正品中任选任选1 1只，和剩下的只，和剩下的3 3只次品一起在前四个位置上任意只次品一起在前四个位置上任意排列，有排列，有 种方法。种方法。故不同的情形共有故不同的情形共有 种。种。4次品次品6 正正 品品 1 2 3 4 5 .变式变式1在一次象棋比赛中，进行单循环比赛。其中有在一次象棋比赛中，进行单循环比赛。

12、其中有2人，人，他们各赛了他们各赛了3场后，因故退出了比赛，这样，这次比赛共进行了场后，因故退出了比赛，这样，这次比赛共进行了83场，问：比赛开始时参赛者有多少人？场，问：比赛开始时参赛者有多少人？解：解：需要考虑两种情况：需要考虑两种情况：第一种，第一种，因故退出比赛的两人之间没有进行比赛，因故退出比赛的两人之间没有进行比赛，则则 ，此方程无正整数解；，此方程无正整数解；第二种，因故退出比赛的两人之间进行了比赛，第二种，因故退出比赛的两人之间进行了比赛，则则 ，解得，解得 ，所以，比赛开始时参赛者有所以，比赛开始时参赛者有1515人。人。分析分析:因为每一场比赛对应着因为每一场比赛对应着2个

13、选手的一个选手的一个组合个组合!变式变式2学校要组织一个学校要组织一个11人的蓝球队人的蓝球队,从高一从高一4个班选拔队个班选拔队员员,每班至少一人每班至少一人,有多少不同的名额分配方案有多少不同的名额分配方案?方案方案1:一班一班2人人,二班二班4人三班人三班2人人,四班四班3人人;方案方案2:一班一班3人人,二班二班2人三班人三班4人人,四班四班2人人;方案方案3:一班一班2人人,二班二班3人三班人三班4人人,四班四班2人人;每一种方案对应着每一种方案对应着10这个空中取这个空中取3个空的一个组合个空的一个组合;即即:C103说明说明:这种方法称为这种方法称为:(隔板法隔板法)变式变式:方

14、程方程X+Y+Z=10的不同的正整数解有多少组的不同的正整数解有多少组?每一种方案对应着每一种方案对应着9这个空中取这个空中取2个空的一个组合个空的一个组合;即即:C9变式变式4：12个相同的球分给个相同的球分给3个人，每人至少一个，而且必须个人，每人至少一个，而且必须 全部分完，有多少种分法？全部分完，有多少种分法？解：将解：将12个球排成一排，一共有个球排成一排，一共有11个空隙，将两个隔板插入个空隙，将两个隔板插入 这些空隙中，规定两这些空隙中，规定两 隔板分成的左中右三部分球分别分给隔板分成的左中右三部分球分别分给 3个人，每一种隔法个人，每一种隔法 对应一种分法，于是分法的总数为对应

15、一种分法，于是分法的总数为 种方法。种方法。小结：将小结：将n个相同的元素分成个相同的元素分成m份（份（n，m为正整数），可以为正整数），可以用用m-1块隔板，插入块隔板，插入n个元素排成一排的个元素排成一排的n-1个空隙中，所有个空隙中，所有的插法数就是分法数，这种方法叫隔板法。的插法数就是分法数，这种方法叫隔板法。=55变式训练变式训练1:有有11名划船运动员名划船运动员,其中其中5人只会划左人只会划左舷舷,4人只会划右舷人只会划右舷,其它其它2人既会划左舷人既会划左舷,又会划右又会划右舷舷,现要从这现要从这12名运动员中选出名运动员中选出8人平均分在左右舷人平均分在左右舷参加划船比赛参加

16、划船比赛,有多少种不同的选法有多少种不同的选法?A B解解:既会划左舷既会划左舷,又会划右舷的又会划右舷的2人设为人设为A,B,分分3类类;(1)A,B都不在内的方法有都不在内的方法有:C5C444=5种种(2)A,B中有一人在内中有一人在内;A,B有有1人划左舷有人划左舷有:C2C5C4种种134A,B有有1人划左舷有人划左舷有:C2C5C4种种143(3)A,B都在内都在内;都划左舷都划左舷:C5C4;24划右舷划右舷,C4C5241左左,1右右,2C5C433变式变式2：有一群孩子外出旅行，回来时准备包车回家，包车费：有一群孩子外出旅行，回来时准备包车回家，包车费 20元，他们把每个人的

17、钱凑合起来，其中有元，他们把每个人的钱凑合起来，其中有23人，每人有人，每人有05元硬币一枚，另外元硬币一枚，另外10人，每人有人，每人有1元硬币一枚，问有多元硬币一枚，问有多不同的凑合方法？不同的凑合方法？解：把所有人的硬币都凑合起来共有解：把所有人的硬币都凑合起来共有2305+101=215 元，所以多元，所以多15元，这样问题可转化为取多余钱的方法数元，这样问题可转化为取多余钱的方法数 即取即取3个个05的硬币或取的硬币或取1个个05硬币和硬币和1个个1元硬币的方法元硬币的方法 数，则有数，则有 种取法。种取法。小结：对于某些问题如果直接去考虑，就会比较复杂，若小结：对于某些问题如果直接

18、去考虑，就会比较复杂，若能转化为与其等价的问题，就变得简单，容易解决，这种能转化为与其等价的问题，就变得简单，容易解决，这种方法叫转化法。方法叫转化法。3:四个同学，争夺三项竞赛冠军，冠军获得者的可能种数有多少？甲乙丙丁100米米,200米米,400米米,43 4.车上有车上有7个座位，个座位，5名乘客就座，有多少种就座方式名乘客就座，有多少种就座方式？1 2 3 4 5 6 75:车上有车上有7个箱子，个箱子，5件消防衣存放，有多少种存放件消防衣存放，有多少种存放方式？方式？A75756从编号为从编号为1，2，3，10，11的共的共11个球中，取个球中，取出出5个球，使得这个球，使得这5个球

19、的编号之和为奇数，则一共个球的编号之和为奇数，则一共有多少种不同的取法？有多少种不同的取法？解：分为三类：解：分为三类：1奇奇4偶有偶有 ；3奇奇2偶有；偶有；5奇奇0偶有，偶有，一共有一共有 +13579112468107现有现有8名青年，其中有名青年，其中有5名能胜任英语翻译工作；有名能胜任英语翻译工作；有4名青名青年能胜任德语翻译工作（其中有年能胜任德语翻译工作（其中有1名青年两项工作都能胜任）名青年两项工作都能胜任），现在要从中挑选，现在要从中挑选5名青年承担一项任务，其名青年承担一项任务，其 中中3名从事英名从事英语翻译工作，语翻译工作，2名从事德语翻译工作，则有多少种不同的选名从事

20、德语翻译工作，则有多少种不同的选法？法？解：我们可以分为三类：解：我们可以分为三类：让两项工作都能担任的青年从事英语翻译工作，有；让两项工作都能担任的青年从事英语翻译工作，有；让两项工作都能担任的青年从事德语翻译工作，有；让两项工作都能担任的青年从事德语翻译工作，有；让两项工作都能担任的青年让两项工作都能担任的青年不不从事任何工作，有，从事任何工作，有，一共有一共有 +42种方法种方法 96本不同的书全部送给本不同的书全部送给5人，每人至少人，每人至少1本，有多少种不同本，有多少种不同的送书方法？的送书方法？解解：第第一一步步：从从6本本不不同同的的书书中中任任取取2本本“捆捆绑绑”在在一一起

21、起看看成成一一 个元素有个元素有 种方法；种方法；第第二二步步：将将5个个“不不同同元元素素（书书）”分分给给5个个人人有有 种种方方法法根据分步计数原理，一共有根据分步计数原理，一共有 1800种方法种方法变变题题1：6本本不不同同的的书书全全部部送送给给5人人，有有多多少少种种不不同同的的送送书书方方法法？变变题题2：5本本不不同同的的书书全全部部送送给给6人人，每每人人至至多多1本本，有有多多少少种种不同的送书方法？不同的送书方法？变变题题3：5本本相相同同的的书书全全部部送送给给6人人，每每人人至至多多1本本，有有多多少少种种不同的送书方法？不同的送书方法？小结：在中学数学中，解答数学

22、问题常用的数学思想方法很小结：在中学数学中，解答数学问题常用的数学思想方法很 多如数形结合思想；分类讨论思想；转化的思想多如数形结合思想；分类讨论思想；转化的思想等等。等等。而我们以上的：特殊元素（位置）分析法，插入法，捆绑而我们以上的：特殊元素（位置）分析法，插入法，捆绑 法，排除法，转化法，机会均等法，隔板法都是运用这些法，排除法，转化法，机会均等法，隔板法都是运用这些 思想在解排列组合应用题时所得到的各种解法，当然，这思想在解排列组合应用题时所得到的各种解法，当然，这 些些 解法要灵活运用，而且有时要联合运用才能把问题解决。解法要灵活运用，而且有时要联合运用才能把问题解决。再见再见再见再见