组合综合应用问题学案.doc

排列、组合综合问题学案 排列、组合综合应用问题学案一、目标点击：1 进一步理解并掌握排列组合问题的基本解法.2 掌握处理排列组合综合问题的一般数学思想方法.3 学会分类讨论的思想.重点：解答排列、组合应用问题的思路难点：分类讨论思想在解决综合问题中的应用二、点击知识点：1、 分类与分步：是区别选用加法原理与乘法原理的惟一标准。分类要做到“不重不漏”，分步设计程序要合理。2、 有序与无序：是界定排列与组合的惟一标准。3、 元素与位置：解题中，界定哪些事物是元素，哪些事物是位置，根据题意恰当选择，要优先安排有限制条件的特殊元素和特殊位置，灵活运用“捆绑法”和“插空法”，“直接法”和“间接法”4、 排列组合应用问题的解题方法：a)直接法:优先安排受限制的元素（或位置），再安排其它元素（或位置）分步 元素分析法 分类 位置分析法 直接法 元素分析法：以元素为主思维，先考虑特殊元素的要求，再考虑其他元素.位置分析法：以位置为主考虑，即先考虑特殊位置的要求，再考虑其它位置.优先法：解带有附加条件的排列、组合应用题，常常存在特殊元素或特殊位置，我们可以从这些“特殊”入手，先满足特殊元素或特殊位置，再去满足其它元素或其它位置，这种解法叫做特殊优先法，它是解较复杂的排列、组合应用题的一种重要思考方法.视一法（捆绑法）：部分元素要连排在一起时，可将它们排列后视为一个元素再和其他元素排列，即为“捆绑法”.插空法：把甲、乙两类不同的元素排成一排，求甲类元素不排在一起的排列方法种数，一般用插空档法求解.这种解法的思路是，先把乙类元素进行全排列，然后在每一个排列的空档（包括排列的两端）中对甲类元素进行选排列，最后由乘法原理，便得到所求的结果.穷举法：把符合条件的所有排列和组合一一写出来.b)间接法: 间接法 （排除法）：解较复杂的排列、组合应用题，除了从正面考虑外，有时，我们也可从问题的反面入手，先求出不符合条件的排列、组合种数，然后从整体中减去这些不符合条件的种数，剩下的就是符合条件的种数.这种思考问题的方法叫做排除法. 分类 容斥原理 间接法 全集含限制条件的集合不含限制条件的集合 分类法：对较复杂的排列组合应用题，由于情况繁多，因此要对各种不同的情况进行科学分类，以便有条不紊地进行解答，避免重复或遗漏现象发生.容斥原理： 用n(M)表示集合M中元素的个数，则： n(AB)=n(A)+n(B)n(AB) 加法原理：若AB（空集），则n(AB)=n(A)+n(B) 这是容斥原理的两个集合的计数原理，它是加法原理的的发展，公式在计算左端集合中的元素个数时，在右端采用了将“应该有的”包含进来，而将“不该有的（重复的）”排斥出去的思想. 例如：A=1,2,3,4,5 B-1,-2,1,2,3, AB1,2,3,AB1,2,1,2,3,4,5, 因为n(A)5，n(B)5， n(AB)=3, n(AB)7. 所以n(AB)=n(A)+n(B)n(AB)例1：有六种不同的工作分配给6个人担任，每个人只担任其中一种工作，甲只能担任其中某两项工作，而乙不能担任这两项工作，问有多少种分配方法？ 解法一：元素分析法：甲担任允许他担任两项工作中的一项，有种方法；乙担任其余四项工作中的一项，有种方法，其它4人担任剩下的四项工作有种方法，故共有分配方法192（种）。解法二：位置分析法：先由其余4人选出1个人有种方法，让乙不能担任的两项工作分配给甲和刚选出的那个人担任，有种方法；剩下的四项工作分配给余下的4个人担任，有种方法，故共有分配方法192（种）。 点拨：此题为有限制条件的排列、组合问题,采用两种方法均为直接法。元素分析法：把6个人看成元素，在解决问题过程中优先考虑有限制条件的元素，即甲、乙的特殊要求。位置分析法：把六种不同的工作看成是位置，在解决问题过程中优先考虑有限制条件的特殊位置，即乙不能担任的两项工作和甲只能担任两项工作。三、排列、组合综合应用问题1、 相邻与不相邻问题例2：某小组6个人排队照相留念： (1)若分成两排照相，前排2人，后排4人，有多少种不同的排法？ (2)若分成两排照相，前排2人，后排4人，但其中甲必须在前排，乙必须在后排， 有多少种不同的排法？ (3)若排成一排照相，甲、乙两人必须相邻，有多少种不同的排法？ (4)若排成一排照相，6个人中有3名男生和3名女生，且男生不能相邻，有多少种 不同的排法？解：1）分两排照相实际上与排成一排照相一样，只不过把第36个位子看成是第二排 而已，所以实际上是6个元素的全排列720种；2)先确定甲的排法，有种，再确定乙的排法，有种，最后确定其他人的排法， 有 种，共有 192 种； 3)采用“捆绑法”，先把甲、乙看成1人，与其他人排队有种，然后甲、乙之间再排队，有种，共有240种；4)采用“插空法”，先把3名女生的位子拉开，在两端和她们之间放进4把椅子，如： 女 女 女 ，再将3名男生排在这4个位置上有种，3名女生之间有有种排法，共有144种排法.思考：4）题若增加条件，男生不能站在两端，有多少种排法？提示：3名男生插入几个空格中。点拨：对于排列组合中必须在一起的元素处理时把它捆绑为一整体，然后考虑其内部的位置关系；对于排列中不能相邻的元素，采用插空法处理，即把整个位置看作是一个抽屉，把无条件限制的元素作为隔板安置在抽屉中，最后把要求不相邻的元素位置在由隔板所形成的空格中，这里应注意，如果无条件限制的元素有n个，那么它们所形成的空格数目为n1个.2、 定位问题例3：7人站成一排，甲不在左端，乙不在右端，共有多少种排法？解法一：第一类，甲在右端，满足“甲不在左端，乙不在右端”限制条件，此时排法有种 ；第二类，甲不在右端：由于甲又不能在左端，所以甲可排在其余5个位置上，有种；这时乙不能排在右端，乙可以排在甲占去一个位置后的其余5个位置上，有种；甲不在左端，乙不在右端满足后，其余5人有种排法，根据乘法原理，甲不在右端时，有种排法.根据加法原理，所求排法总数为3720种. 解法二：先安排最左端位置，除甲外，可以有种，其余位置若不受限制，有种，但其中右边位置是乙时有种，不合要求,所以共有3720种排法.解法三：（排除法）若无任何限制条件，有种，但甲在左端的种不合要求，同样，乙在右端的种也不合要求，减去2，实际上，这样就减重了.甲乙这样的排法减了两次，还应再加上一次，所以共有23720种排法.3、 标号排位问题例4：将数字1，2，3，4填入标号为1，2，3，4的四个方格里，每格填入一个数，则每 个方格的标号与所填的数字均不相同的填法有( ) A 6种 B 9种 C 11种 D 23种 解：首先把1填入方格，可填入2、3、4号方格，有3种方法；然后把被占据方格的 对应的数字填入其它三个方格，又有3种方法；最后填余下的两个数字，只有1 种填法，共有3319种方法，故选B. 点拨：标号排位问题的解答程序是：把元素排到指定号码的位置上，可先把某个元素按规定排入，第二步再排另一个元素，如此继续下去，依次即可完成。例5：设有a、b、c、d、e、f六个元素排成一排列，按a、b、c、的次序排列有多少 种排法？ 解：利用插空法，OOO，其中O表示d、e、f排的位置，表示a、b、c、 去插空，把a、b、c、分四类插空。 1）把（abc）当作一个整体且顺序不变，插入四个空中，有种 2)把（ab）当作一个整体且顺序不变，c为另一组插入四空中，有种 3)把a当作一组，（bc）当作一组，且a、b、c、的次序不变，插入四个空中， 有种 4）把a、b、c、分别插入四空中，且a、b、c的次序不变，有种 根据加法原理，共有（）120种4、 分组分配问题例6：现有4套不同的练习题：1） 平均分给2名同学有多少种不同的分法？2） 平均分成2份，有多少种不同的分法？解：1）甲学生得2套，有种，乙学生得2套有种分法，根据乘法原理 共有6种分法 2)按1）分法有种重复，所以不同的分法有=3种 实验检验：把A、B、C、D四个字母分成2份：AB,CD； AC,BD；AD,BC； BC,AD； BD,AC；CD,AB；从这个具体例子可以发现，AB,AC,AD,BC,BD,CD各出现两次，重复计为 点拨：类似地，如果把A,B,C,D,E,F六个字母平均分成3份，出现重复 一般地，把4个元素平均分成2份，不同的分法有， 6个元素平均分成3份，不同的分法有, 8个元素平均分成4份，不同的分法有例7：6本不同的书按下列方法分配，有多少种分法？ 分给3人，甲得1本，乙得2本，丙得3本； （各组元素数目确定，分配对象确定） 分给3人，1人1本，1人2本，1人3本； （各组元素数目确定，分配对象不固定） 平均分给3人； （各组元素数目相等，分配给具体对象） 全部分给5个学生，每人至少1本； （各组数目不相等，分配对象的数额不固定） 分给4个学生，每人至多2本，每人至少1本；（各组数目不相等，分配对象的数额不固定） 平均分成3组； （平均分组，无分配对象） 分成3组，一组3本，一组2本，一组1本； （非平均分组，无分配对象） 分成4组，一组3本，其余各组各1本； （部分平均分组，无分配对象） 全部分给了5个学生。解：分三步：先从6本不同的书中任取1本给甲有，然后从剩余的5本中任取 2本给乙有，最后把剩余的3本都给丙，由乘法原理，共有=60种分法。 与（1）相比，各组元素数目仍分别为1，2，3，但未固定分给哪个人，不妨设甲得1本，乙得2本，丙得3本，由知有种分法，然后将3人所得的本数相互交换，故再乘以，所以共有=360种分法。：可以看作分给甲、乙、丙三人，每人得2本，由来考虑，得种分法，上述分法确保了每人任得两本不同的书，又由于人所得本数相同，不用交换，所以不再乘以，共有=90种分法。：首先6本书分成5组，各组本数分别为1、1、1、1、2，按照（2）题的方法，有种分法，这是把各组的元素看作不同数目所得，但实际上有4个学生分得的本数是完全相同的，不用相互交换，所以上述分法种数应是实际分法种数的倍，故应再除以，所以共有（）/=1800种分法，：由题意，首先将6书本分成4组，各组数目分别为2、2、1、1、有两组分的本数是相同的，由（4）的解法，可知共有（）/()=1080种.：不妨设这三个组分给甲、乙、丙三人，有种分法，但实际上并未分配到 人，与甲、乙、丙三人无关，故再除以，共有（）/=15种分法.：由于各组的元素数目不相同，就相当于与不同的确定对象有关，因此可按照1）的方 法解决，所以共有=60种分法.：首先6本书分成4组，各组本数分别为3、1、1、1，但其中有3个组是完全相同 的（平均分配），共有（）/=20种分法.：任何1本书都可以分配给5个学生中的任何一个人，有5种分法，根据乘法原理共 有56种分法.点拨：分组分配问题主要有两类，分组后有分配对象和分组后无分配对象.分配对象的分组是指元素分组后，又分配给各具体对象，而分组是指元素数目的分组。注意均匀与非均匀，编号与不编号限制条件的分组问题.例8：将4个不同的小球放入编号为1，2，3，4的四个盒中； 恰有一个空盒的放法共有多少种？ 恰有2个空盒的放法共有多少种？ 解：解法一：先从4个盒子中选一个空，然后从剩余的3个盒子中选出一个，再从4 个小球中选出2个放入此盒，还有2个盒子放2个球，每个盒子一个球，显然有2种 放法，共有2144种.解法二：先从4个小球中选出2个，再从4个盒子中选出1个，把这2个小球放入，剩下的两个小球要放入剩下的3个盒子中，每个盒子至多放一个球，共有144种.解法三：先从4个小球中选出2个，看作一个球.问题转化为“3个球，4个盒子，每个球都放入盒内，每个盒子至多放一个球，共有几种放法.”将4个不同的小球分成“2，1，1”三堆，有种分法，再将三堆分别放入4个盒中，有种，恰有一个空盒的放法共有144种.解法一：（分类法）：先从4个盒子中任选2个盒子，在这两个盒子中不放入小球，问题转化为“4个球，2个盒，每个盒子必须放小球，共有几种放法？，从放球的数目考虑分为两类；一类是其中一个盒子放入3个球，另一个盒子放入1个球，有 8种放法；另一类是每个盒子放2个球，放法数为16，共有（86）84种.解法二：（排除法）：4个不同的球，放入4个不同的盒子中有44种放法，不符合要求的放法分为三类：1)没有空盒的放法有；2）恰有1个空盒的放法有144种，3）恰有3个空盒的放法有4种；则恰有2个空盒的放法共有44144484种.5、 几何问题例9：（97全国高考）四面体的顶点和各棱中共10个点，在其中取4个不共面 的点，不同的取法共有（ ）种. A 150 B 147 C 144 D 141解：(分类法)：10个点任取4个点的取法有种，其中4点共面的情况有三类：第一类：取出的4个点位于四面体的同一面内，有4种取法，第二类：取1条棱的3个点及该棱上中点，这4个点共面，有6种取法，第三类： 由中位线构成的平面四边形（其两组对边分别平行于四面体相对的两条棱）它的4个顶点共面，有3种取法.故10个点中取4点，不共面的取法共有（463）141种.四、排列组合的数学思想方法1、化归思想例10：（93全国理）同室4人各写1张贺年卡，先集中起来，然后每人从中拿1张别 人送出的贺年卡，则4张贺年卡不同的分配方式有（ ）。 A 6种 B 9种 C 11种 D 23种 建立数学模型：用1，2，3，4这4个数字表示4张贺年卡，根据题意，将求4张贺年卡不同的分配方式转化为求1不在个位，2不在十位，3不在百位，4不在千位的无重复数字的四位数的排列数问题.解法一：个位只能放2，3，4三种，在放过数字2后，十位只能放1，3，4三种.后两 位已确定.类似地，当个位放数字3时，百位只能放1，2，4，其余也已确定。 共有339（种） 选B解法二：记四人为甲、乙、丙、丁，则甲送出的贺卡可以且只可以由乙、丙、丁三人之 一收到，若乙收到，则有两种情形：(1)甲收到乙送的卡片，则只有一种情况发生，即丙收丁、丁收丙.(2)甲收到的不是乙送的，而是收到丙的卡片，则只能是丙收乙的，丁收丙的，两种情况.这就是说，甲送的卡片被乙收到有三种情况.而甲送的卡片有三种收卡方式（乙、丙、丁） 共有339（种） 选B 解法三：具体列出所有可能的情况，即 13214323412413 314234213412共9种.412343124321解法四：将四个数填入四个有序号的空格，共有种方法.其中不合要求的有三类：（1） 四个格填写的数字都与格号相同：；（2）恰有两个与填写的格号相同：； （3）恰有一个与填写的格号相同：；所以所有方法种数为（）9点拨：本题的背景是“乱坐问题”或“排错问题”，建立数学模型转化为数学问题是： 用1，2，3，4这4个数字组成无重复的四位数，其中1不在个位，2不在十 位，3不在百位，4不在千位的四位数共有多少个？这个问题就容易解决。2、对称思想例11：（90全国）A,B,C,D,E五人并排站成一排，若B必须站在A的右边（A,B可以不相 邻），那么不同的排法共有（ ）.A 24种 B 60种 C 90种 D 120种解：对称法：不考虑限制，A,B,C,D,E五人并排站成一排共有种排法，对限制条件可考虑对称性：B在A的右边与B在A的左边机会均等，应得排法为60（种）选B3、分类思想AB8个个GGE4个8个个GGE例12：（96全国）已知集合A和集合B各含12个元素，AB含有4个元素，试求同时满 足下列两个条件的集合C的个数.(1) C (AB),且C中含有3个元素；(2) CA(表示空集)解：因为A、B各含有12个元素，AB含有4个元素，所以AB中元素的个数是1212420个，其中，属于A的元素有12个，属于B而不属于A 的元素有8个，要使CA，则组成C中的元素至少有一个含在A中，满足题设条件的集合C的个数可化为三类：第一类：A中取1个元素， B中取2个元素有个；第二类：A中取2个元素，B中取1个元素有个；第三类：A中取3个元素，B中取0个元素有个； 满足题设条件的集合C的个数为1084（个）点拨：本题与“集合A有12个元素集合B有8个元素，且AB，求在集合中取3个 元素，其中至少含有A的一个元素构成的集合C的个数”等价.把一个复杂问题，通过正确划分，进行合理分类转化为若干小问题予以各个击破。例13：某旅行社共有9名专业导游，其中6人会英语，4人会日语，若在同一天要接待 5个不同的外国旅游团队，其中有3个队要安排会英语的导游，2个队要安排会 日语的导游，求不同安排的方法共有多少种？解：显然，可以推得：有1个人即会英语也会日语,5个人只会英语，英5人日3人1人 3个人只会日语，设A只会英语的5人，B只会日语的3人 ， C即会英语也会日语1人. 以C集的元素为主要元素分成三类：1)不取C中的主要元素，在A中选取3个人，接待会英语的3个旅游团队有种，再从B中选取2人，接待会日语的2个旅游团队有种，不同的安排方法有（)()种.2)取C中的主要元素做英语导游，在A中选取2个人和C中的1人接待会英语的3个旅游团队有种，再从B中选取2人，接待会日语的2个旅游团队有种，不同的安排方法有种.3）取C中的主要元素做日语导游，在A中选取3个人，接待会英语的3个旅游团队有种，再从B中选取1人和C中的1人，接待会日语的2个旅游团队有种，不同的安排方法有()()种.根据加法原理，接待5个不同的外国旅游团队 不同的安排方法共有()() +()()=1080种.点拨：用集合的韦恩图表示9名导游的的分布情况，参照图形解答，并进行恰当的分 类，做到不重不漏。例14：九张卡片分别写着数字0，1，2，8，从中取出三张排成一排组成一个三位数，如果写着6的卡片还能当9用，问共可以组成多少个三位数？解：（1）不取卡片6，组成三位数的个数为；（2）取卡片6，又分两类，a）当6用时组成的三位数的个数为-个，b)当9用时同样组成的三位数的个数为-个，根据加法原理得所求三位数的个数为：2（-） 602(个)点拨：以是否取卡片6分成两类，每类中再注意三位数中首位不能取0。4、数形结合思想例15：设A=-8,-6,-4,-2,0,1,3,5,7,9,从A中任取两个元素作为虚数a+bi的实部和 虚部（ab）,则能组成模大于5的不同虚数的个数为多少？-55-55xyo 解：由题设知a2+b225且ab，b0;根据复数模的几何意义，结合补集思想，只要求出以O为圆心，5为半径的圆上及圆内以A中元素为横纵坐标的点的个数，然后从A中所有元素组成的不同复数对应的点中去除即可。如图所示，圆内及圆上的点有517（个）（不含实轴上的5个点）则圆外、圆内及圆上共有81（个）点（不含实轴上的10个点）所以满足题设的虚数共有(5)64（个）例16：(99全国)在一块并排10垄的田地中，选择2垄分别种植A、B两种作 物，每种作物种植一垄.为有利于作物生长，要求A、B两种作物的间 隔不小于6垄，则不同的选垄方法共有 种（用数字作答）.解法一：1)若A、B之间间隔6垄，如果A在左，B在右，A的左边可以有2垄,1垄,0垄，相应B的右边有0垄,1垄,2垄.A、B还可以交换位置，所以这样的选垄方法有3种.2)若A、B之间间隔7垄，如果A在左，B在右，A的左边可以有1垄、0垄， A、B可以交换位置，这样共有2种选垄方法.3) 若A、B之间间隔8垄,有种选垄方法.共有不同的选垄方法3212（种）解法二：插空法，中间的6垄与两旁的A、B两垄先排好，A的两边有2个空，B的两边有2个空，这4个空选2个空种植其它2垄，A、B有顺序，所以共有12种不同的选垄方法.解法三：图示法：如图，用并排一行的10个小矩形表示10垄田地，小矩形内加“O”号表示选中，具体画出来有6种选取方法。种植A、B两种作物有种种植方法，故共有612种选垄方法.OOOOOOOOOOOO 例17：从6名运动员中选取4名参加4100m接力赛，如果甲不跑第一棒，乙不跑第四 棒，有多少种不同的参赛方案？解法一：（分类讨论）把所选取运动员的情况分三类，第一类：甲、乙两人均不参赛共有24种；第二类：甲、乙两人有且只有一人参赛则有144种；第三类：甲、乙两人均参赛则共有（2）84，由加法原理所有参赛方法共有（2）252种解法二：设全集I从6人中选4人的参赛排列，A甲跑第一棒的参赛排列IAB B=乙跑第四棒的参赛排列，借助韦恩图，根据容斥原理 n(AB)=n(A)+n(B)n(AB) 故所求符合题意的参赛 方案数为 n(I)n(A)-n(B)n(AB)=- -+=252(种)点拨：借助图形、图象、示意图、图表等模拟生产、生活实际，使应用题形象化、具体化，易于求解。5、逆反思想例18：从6名男生和5名女生中选出4人，求满足下述条件的选法有多少种？1、 至少有1名女生入选； 2、不都是女生入选。解：（1）“至少有1名女生入选”的否定是“入选的4人都不是女生”，即都是男生。 315（种） （2）“不都是女生入选”的否定是“入选4人都是女生” 325（种）.点拨：根据条件从正面直接考虑，情况分类比较复杂，甚至很难把握。于是转化考虑条件的反面，从总的方法数中减去不符合条件的方法数，即得所求的方法数，用此方法应注意你所排除的与所求的必须是“否定“关系。常用的互否词语：“至少有一个是”的否定是“都不是”； “不都是”的否定是“都是”“至少有2个是”的否定是“恰好有一个是，或者都不是”。注意“都是” 与“都不是”不是互否的关系。6、整体思想例19：有8本不同的书，其中文学书3本，科技书2本，其它书3本，若将这些书排成一列放在书架上，则文学书放在一起，科技书也放在一起的不同排法共有 种.解：要保证文学书在一起，科技书也在一起，即可视文学书3本为一个整体，科技书2本为一个整体，然后与其它3本书全