组合综合应用问题学案

排列、组合综合问题学案1排列、组合综合应用问题学案一、目标点击：1．进一步理解并掌握排列组合问题的基本解法.2．掌握处理排列组合综合问题的一般数学思想方法.3．学会分类讨论的思想.重点：解答排列、组合应用问题的思路难点：分类讨论思想在解决综合问题中的应用二、点击知识点：1、分类与分步：是区别选用加法原理与乘法原理的惟一标准。分类要做到“不重不漏”，分步设计程序要合理。2、有序与无序：是界定排列与组合的惟一标准。3、元素与位置：解题中，界定哪些事物是元素，哪些事物是位置，根据题意恰当选择，要优先安排有限制条件的特殊元素和特殊位置，灵活运用“捆绑法”和“插空法”，“直接法”和“间接法”4、排列组合应用问题的解题方法：a)直接法:优先安排受限制的元素（或位置），再安排其它元素（或位置）直接法穷举法位置对称对称法元素不相邻插空法元素位置相邻视一法特殊元素、位置优先法元素分析法：以元素为主思维，先考虑特殊元素的要求，再考虑其他元素.位置分析法：以位置为主考虑，即先考虑特殊位置的要求，再考虑其它位置.⑴优先法：解带有附加条件的排列、组合应用题，常常存在特殊元素或特殊位置，我们可以从这些“特殊”入手，先满足特殊元素或特殊位置，再去满足其它元素或其它位置，这种解法叫做特殊优先法，它是解较复杂的排列、组合应用题的一种重要思考方法.⑵视一法（捆绑法）：部分元素要连排在一起时，可将它们排列后视为一个元素再和其他元素排列，即为“捆绑法”.⑶插空法：把甲、乙两类不同的元素排成一排，求甲类元素不排在一起的排列方法种数，一般用插空档法求解.这种解法的思路是，先把乙类元素进行全排列，然后在每一个排列的空档（包括排列的两端）中对甲类元素进行选排列，最后由乘法原理，便得到所求的结果.⑷穷举法：把符合条件的所有排列和组合一一写出来.b)间接法:分步元素分析法分类位置分析法排列、组合综合问题学案2间接法（排除法）：解较复杂的排列、组合应用题，除了从正面考虑外，有时，我们也可从问题的反面入手，先求出不符合条件的排列、组合种数，然后从整体中减去这些不符合条件的种数，剩下的就是符合条件的种数.这种思考问题的方法叫做排除法.间接法全集＝含限制条件的集合∪不含限制条件的集合分类法：对较复杂的排列组合应用题，由于情况繁多，因此要对各种不同的情况进行科学分类，以便有条不紊地进行解答，避免重复或遗漏现象发生.容斥原理：用n(M)表示集合M中元素的个数，则：n(A∪B)=n(A)+n(B)－n(A∩B)加法原理：若A∩B＝φ（空集），则n(A∪B)=n(A)+n(B)这是容斥原理的两个集合的计数原理，它是加法原理的的发展，公式在计算左端集合中的元素个数时，在右端采用了将“应该有的”包含进来，而将“不该有的（重复的）”排斥出去的思想.例如：A={1,2,3,4,5}B＝{-1,-2,1,2,3},A∩B＝{1,2,3},A∪B＝{－1,－2,1,2,3,4,5,}因为n(A)＝5，n(B)＝5，n(A∩B)=3,n(A∪B)＝7.所以n(A∪B)=n(A)+n(B)－n(A∩B)例1：有六种不同的工作分配给6个人担任，每个人只担任其中一种工作，甲只能担任其中某两项工作，而乙不能担任这两项工作，问有多少种分配方法？解法一：元素分析法：甲担任允许他担任两项工作中的一项，有12C种方法；乙担任其余四项工作中的一项，有14C种方法，其它4人担任剩下的四项工作有44P种方法，故共有分配方法12C14C44P＝192（种）。解法二：位置分析法：先由其余4人选出1个人有14C种方法，让乙不能担任的两项工作分配给甲和刚选出的那个人担任，有22P种方法；剩下的四项工作分配给余下的4个人担任，有44P种方法，故共有分配方法14C22P44P＝192（种）。点拨：此题为有限制条件的排列、组合问题,采用两种方法均为直接法。元素分析法：把6个人看成元素，在解决问题过程中优先考虑有限制条件的元素，即甲、乙的特殊要求。位置分析法：把六种不同的工作看成是位置，在解决问题过程中优先考虑有限制条件的特殊位置，即乙不能担任的两项工作和甲只能担任两项工作。三、排列、组合综合应用问题1、相邻与不相邻问题例2：某小组6个人排队照相留念：分类容斥原理排列、组合综合问题学案3(1)若分成两排照相，前排2人，后排4人，有多少种不同的排法？(2)若分成两排照相，前排2人，后排4人，但其中甲必须在前排，乙必须在后排，有多少种不同的排法？(3)若排成一排照相，甲、乙两人必须相邻，有多少种不同的排法？(4)若排成一排照相，6个人中有3名男生和3名女生，且男生不能相邻，有多少种不同的排法？解：1）分两排照相实际上与排成一排照相一样，只不过把第3～6个位子看成是第二排而已，所以实际上是6个元素的全排列66P＝720种；2)先确定甲的排法，有12P种，再确定乙的排法，有14P种，最后确定其他人的排法，有44P种，共有12P14P44P＝192种；3)采用“捆绑法”，先把甲、乙看成1人，与其他人排队有55P种，然后甲、乙之间再排队，有22P种，共有55P22P＝240种；4)采用“插空法”，先把3名女生的位子拉开，在两端和她们之间放进4把椅子，如：×女×女×女×，再将3名男生排在这4个位置上有34P种，3名女生之间有有33P种排法，共有34P33P＝144种排法.思考：4）题若增加条件，男生不能站在两端，有多少种排法？提示：3名男生插入几个空格中。点拨：对于排列组合中必须在一起的元素处理时把它捆绑为一整体，然后考虑其内部的位置关系；对于排列中不能相邻的元素，采用插空法处理，即把整个位置看作是一个抽屉，把无条件限制的元素作为隔板安置在抽屉中，最后把要求不相邻的元素位置在由隔板所形成的空格中，这里应注意，如果无条件限制的元素有n个，那么它们所形成的空格数目为n＋1个.2、定位问题例3：7人站成一排，甲不在左端，乙不在右端，共有多少种排法？解法一：第一类，甲在右端，满足“甲不在左端，乙不在右端”限制条件，此时排法有66P种；第二类，甲不在右端：由于甲又不能在左端，所以甲可排在其余5个位置上，有15P种；这时乙不能排在右端，乙可以排在甲占去一个位置后的其余5个位置上，有15P种；甲不在左端，乙不在右端满足后，其余5人有55P种排法，根据乘法原理，甲不在右端时，有排列、组合综合问题学案415P15P55P种排法.根据加法原理，所求排法总数为66P＋15P15P55P＝3720种.解法二：先安排最左端位置，除甲外，可以有16P种，其余位置若不受限制，有66P种，但其中右边位置是乙时有15P55P种，不合要求,所以共有16P66P－15P55P＝3720种排法.解法三：（排除法）若无任何限制条件，有77P种，但甲在左端的66P种不合要求，同样，乙在右端的66P种也不合要求，减去266P，实际上，这样就减重了.甲×××××乙这样的排法减了两次，还应再加上一次，所以共有77P－266P＋55P＝3720种排法.3、标号排位问题例4：将数字1，2，3，4填入标号为1，2，3，4的四个方格里，每格填入一个数，则每个方格的标号与所填的数字均不相同的填法有()A6种B9种C11种D23种解：首先把1填入方格，可填入2、3、4号方格，有3种方法；然后把被占据方格的对应的数字填入其它三个方格，又有3种方法；最后填余下的两个数字，只有1种填法，共有3×3×1＝9种方法，故选B.点拨：标号排位问题的解答程序是：把元素排到指定号码的位置上，可先把某个元素按规定排入，第二步再排另一个元素，如此继续下去，依次即可完成。例5：设有a、b、c、d、e、f六个元素排成一排列，按a、b、c、的次序排列有多少种排法？解：利用插空法，×O×O×O×，其中O表示d、e、f排的位置，×表示a、b、c、去插空，把a、b、c、分四类插空。1）把（abc）当作一个整体且顺序不变，插入四个空中，有14C33P种2)把（ab）当作一个整体且顺序不变，c为另一组插入四空中，有24C33P种3)把a当作一组，（bc）当作一组，且a、b、c、的次序不变，插入四个空中，有24C33P种4）把a、b、c、分别插入四空中，且a、b、c的次序不变，有34C33P种根据加法原理，共有33P（14C＋24C＋24C＋34C）＝120种4、分组分配问题例6：现有4套不同的练习题：1）平均分给2名同学有多少种不同的分法？2）平均分成2份，有多少种不同的分法？解：1）甲学生得2套，有24C种，乙学生得2套有22C种分法，根据乘法原理排列、组合综合问题学案5共有24C22C＝6种分法2)按1）分法有22P种重复，所以不同的分法有222224PCC=3种实验检验：把A、B、C、D四个字母分成2份：⑴AB,CD；⑵AC,BD；⑶AD,BC；⑷BC,AD；⑸BD,AC；⑹CD,AB；从这个具体例子可以发现，AB,AC,AD,BC,BD,CD各出现两次，重复计为22P点拨：类似地，如果把A,B,C,D,E,F六个字母平均分成3份，出现33P重复一般地，把4个元素平均分成2份，不同的分法有222224PCC，6个元素平均分成3份，不同的分法有33222426PCCC,8个元素平均分成4份，不同的分法有4422242628PCCCC例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本给甲有16C，然后从剩余的5本中任取2本给乙有25C，最后把剩余的3本都给丙33C，由乘法原理，共有16C25C33C=60种分法。⑵与（1）相比，各组元素数目仍分别为1，2，3，但未固定分给哪个人，不妨设甲得1本，乙得2本，丙得3本，由⑴知有16C25C33C种分法，然后将3人所得的本数相互交换，故再乘以33P，所以共有16C25C33C33P=360种分法。⑶：可以看作分给甲、乙、丙三人，每人得2本，由⑴来考虑，得26C24C22C种分法，上排列、组合综合问题学案6述分法确保了每人任得两本不同的书，又由于人所得本数相同，不用交换，所以不再乘以33P，共有26C24C22C=90种分法。⑷：首先6本书分成5组，各组本数分别为1、1、1、1、2，按照（2）题的方法，有16C15C14C13C22C55P种分法，这是把各组的元素看作不同数目所得，但实际上有4个学生分得的本数是完全相同的，不用相互交换，所以上述分法种数应是实际分法种数的44P倍，故应再除以44P，所以共有（16C15C14C13C22C55P）/44P=1800种分法，⑸：由题意，首先将6书本分成4组，各组数目分别为2、2、1、1、有两组分的本数是相同的，由（4）的解法，可知共有（26C24C12C11C44P）/(22P22P)=1080种.⑹：不妨设这三个组分给甲、乙、丙三人，有26C24C22C种分法，但实际上并未分配到人，与甲、乙、丙三人无关，故再除以33P，共有（26C24C22C）/33P=15种分法.⑺：由于各组的元素数目不相同，就相当于与不同的确定对象有关，因此可按照1）的方法解决，所以共有36C23C11C=60种分法.⑻：首先6本书分成4组，各组本数分别为3、1、1、1，但其中有3个组是完全相同的（平均分配），共有（36C13C12C11C）/33P=20种分法.⑼：任何1本书都可以分配给5个学生中的任何一个人，有5种分法，根据乘法原理共有56种分法.点拨：分组分配问题主要有两类，