《排列组合问题常见模型》由会员分享，可在线阅读，更多相关《排列组合问题常见模型（6页珍藏版）》请在金锄头文库上搜索。
1、排列组合问题的常见模型一、相异元素不许重复的排列组合问题这类问题有两个条件限制，一是给出的元素是不同的，即不允许有相同的元素；二是取出的元素也是不同的，即不允许重复使用元素。这类问题有如下一些常见的模型。模型1：从n个不同的元素中每次取出m个不同元素作排列或组合，规定某k个元素都包含在内，贝I：组合数：N=Cm-k排列数：N=AmCm-k1 nk2mnk例1.全组有12个同学，其中有3个女同学，现要选出5个，如果3个女同学都必须当选，试问在下列情形中，各有多种不同的选法？(1)组成一个文娱小组；(2)分别担任不同的工作.解：(1)由于要选出的5人中，3个女同学都必须当选，因此还需要选2人.这可
2、从9个男同学中选出，故不同的选法有：N=C5-3=36(种1 12-3(2)在上述组合的基础上，因为还需要考虑选出5人的顺序关系，故不同的选法有：N二A5C5-3二A5C2二120,36二4320(种2 512-359模型2.从n个不同的元素中每次取出m个不同元素作排列或组合，规定某k个元素都不包含在内，贝I：组合数：N二Cm排列数：N二AmCm二Am1n-k2mn-kn-k例2.某青年突击队有15名成员，其中有5名女队员，现在选出7人，如果5名女队员都不当选，试问下列情形中，各有多少种不同的选法？(1)组成一个抢修小组；(2)分别但任不同的抢修工作.解：(1)由于5名女队员都不当选，因此只能
3、从10名男同学选出，故不同的选法有：N二C7二C7二C3二120(种)1 15-51010(2)由于还需考虑选出的7个人的顺序问题，故不同的选法有：N二A7二A7二10,9,8,7,6,5,4二604800(种)2 15-510模型3.从n个不同的元素中每次取出m个不同元素作排列或组合，规定每一个排列或组合，都只包含某k个元素中的某S个元素。则组合数：N=Cm-s排列数：N=AmCm-s1n-k2mn-k例3.全组12个同学，其中有3个女同学，现要选出5人，如果3个女同学中，只有甲当选，试问在下列情形中，各有多少种不同的选法？(1)组成一个数学小组；(2)分别担任不同的工作.解：(1)由于女同
4、学中只有甲当选，所以还需4人，这4人要从男同学中选，因此不同选法有：N二C5-1二C4二126(种)112-39(2)由于选出的人要分别担任不同的工作，所以不同的选法有：N=A5C5-1=A5C4=15120(种).2512-359模型4.从n个不同的元素中每次取出k个不同元素作排列或组合，规定每一个排列或组合，都只包含某r个元素中的s个元素。贝I：组合数：N=CsCk-s排列数：N=AkCsC1rn-r2krn-r例4.全组12个同学，其中有3个女同学，现要选出5人，如果3个女同学中，只有1人当选，试问在下列情形中，各有多少种不同的选法？(1)组成一个数学小组；(2)分别担任不同的工作.解：
5、(1)由于女同学中只有1人当选，所以从3个女同学中选1人，从9个男同学中选4人，不同的选法有：N=CiC5-1=CiC4=378(种)1312339(2)由于选出的人要分别担任不同的工作，所以不同的选法有：N二A5C1C5-1二A5C1C4二45360(种).253i23539模型5.从n个不同的元素中每次取出k个不同元素作排列或组合，规定每一个排列或组合，都至少包含某r个元素中的s个元素.贝I：组合数：N=CsCk-s,Cs+1Ck-s-1,Cs+iCk-s-2,CrCk-rirnrrnrrnrrnr排列数：N=Ak(CsCk-s,Cs+1Ck-s-1,Cs+2Ck-s-2,CrCk-r)2
6、krn-rrn-rrn-rrn-r例5.全组12个同学，其中有3个女同学，现要选出5人，如果3个女同学中至少有1人当选，试问在下列情形中，各有多少种不同的选法？(1)组成一个数学小组；(2)分别担任不同的工作.解：N=CiC4,C2C3,C3C2=666(种，1 393939N=A5(CiC4,C2C3,C3C2)=120x666=79920(种2 5393939模型6.从n个不同的元素中每次取出k个不同元素作排列或组合，规定每一个排列或组合，都至多包含某r个元素中的s个元素.贝1：合数：N=CoCk,C1Ck-1,C2Ck-2,CsCk-s1 rn-rrn-rrn-rrn-r排窃列数：N=A
7、5(C0Ck,ClCk-1,C2Ck-2,CsCk-s)2 5rn-rrn-rrn-rrn-r例6.全组12个同学，其中有3个女同学，现要选出5人，如果3个女同学中至多有2人当选，试问在下列情形中，各有多少种不同的选法？(1)组成一个数学小组；(2)分别担任不同的工作.解：N=CoC5,C1C4,C2C3=766(种，1 393939N=A5(C0C5,C1C4,C2C3)=120x766=91920(种2 5393939模型7.从n个不同的元素中每次取出k个不同元素作排列，规定某r个元素都包含在内，并且分别占据指定的位置.则N=Ak-rn-r例7.用1,2,3,4,5这五个数字，能组成多少个
8、没有重复数字且能被25整除的四位数？解：能被25整除的数的末两位能被25整除，又1,2,3,4,5四个数字中没有0要求四位数能被25整除，最后两位只能是25.能组在被25整除的四位数只要选取前两位数就可以，所以有N=A4-2=A2=6(个).5-23模型8.从n个不同的元素中每次取出k个不同元素作排列，规定某个元素不能占据某个位置.则N=AkAk-1nn-1例8.用0,1,2,3,4,5这六个数字，能组成多少个没有重复数字的四位数？解：to不能排在首位，.能组成四位数有NA4-A3300（个）65模型9.从n个不同的元素中每次取出k个不同元素作排列，规定某s个位置的元素只能从某r个元中选取.则
9、NAsAk-srn-s例9.用1,2,3,4,5这五个数字，能组成多少个没有重复数字的四位偶数？解：个位只能排2或5，能组成四位偶数有NAi，A348（个）24模型10.从n个不同的元素中每次取出k个不同元素作排列，规定某s个位置的元素只能从某r个元中选取，而其余位置的元素只能从其余元素中选取.则NAs，Ak-srn-s例10用1至9这九个数字，能组成多少个没有重复数字并且奇数位（从右边起）是奇数，偶数位是偶数的五位数？解:奇数位的个位，百位和万位只能从1,3,5,9这四个数中选取,偶数位的十位和千位只能从2,4,6,8这四个数中选取，.能组成五位数共有NA3，A2720（个）54模型11.把
10、n个不同的元素作全排列，规定某r个元素连排在一起，则NAr，An刁+1rn-r+1例11用1,2,3,4,5这五个数字，能组成多少个没有重复数字并且两个偶数字连在一起的五位数？解：先把两个偶数字看成一个整体，作为一个数字来参加排列，然后再考虑这两个数字的前后顺序关系，因此能组面符合条件的五位数有NA2，A448（个）24模型12.把n个不同的元素作全排列，规定某r个元素中的任意两个元素都不连排在一起，n+1（rW）则NAr，An-r2n-r+1n-r例12.用1,2,3,4,5,6这六个数字，能组成多少个没有重复数字并且任意两个奇数字都不连在一起的六位数？解：先排好三个偶数字，然后在三个偶数字
11、之间的四个空位中，任选三个来排奇数字，因此能组成合条件的六位数有NA3，A324372（个）43例13.某天的课表要排入语文、数学、英语、物理、化学、体育六门课，如果第一节不排体育，最后一节不排数学，一共有多少不同的排法？解法（一）把六门课看成元素，把课表节次看成位置，元素找位置.由于数学体育这两个元素有附加条件，为此优先加以考虑，若以数学课排法进行分类；则Q数学排在第一节，NA5；Q数学排在第二节，NA1A4；Q数学排在第三节，NA1A415244344Q4数学排在第四节，NA1A4；Q5数学排在第五节，NA1A44 44544根据加法原理，共有21，A4504（种）不同排法.123454解
12、法（二）用位置分析法，先安排有约束条件的位置，位置选元素.若以第一节排法进行分类：Q第一节排数学，NA5；Q第一节排语文；NA1A4Q第一节排英语，NA1A415244344Q第一节排物理，NAiA4；第一节排化学，NAiA4444544根据加法原理，共有21-A4504(种)不同排法.123454解法(三)考虑用间接接法.不考虑任何限制条件，共有A6种不同的排法，但其中所括6(1)数学排在最后一节的排法.A5种；(2)体育排在第一节的排法.A5种；这两种情况下,55都包含了数学排在最后一节，体育排在第一节的情况，这种情况共有A5种不同的排法.因5此，不同的排法共有NA62A5+A4504(种
13、)654说明(1)有约束条件的排列问题,应先排好有约束条件的元素或位置,然后再排没有约条件的元素或位置.也可用间接法解,先排不考虑约束条件,求出所有的排列种数,然后减去不合题目要求的排列种数.(2) 本的一般模型是:把个不同的小球入入个有编号的盒中，每盒一个，但其中的甲球不能放入A盒，乙球不能放入B盒，共有不同的放法NAn，2An-1+An-2种.nn-1n-2例14.A、B、C、D、E五人站成一排，(1) 如果A、B两人要站在两端，有多少种站法？(2) 如果A、B两人不站在两端，有多少种站法？(3)如果A、B两人相邻，有多少种站法？(4) 如果A、B两人不相邻，有多少种站法？(5) 如果A在
14、B的左边(可以不相邻)，有多少种站法？解(1)因为A、B排在两端的的不同方法有A2种方法，第二步排中间三人共有A3种不同的排法，23所以根据乘法原理不同的排法共有A2-A312种不同的排法.23(2)第一步由C、D、E三人中任选两人排在两端的不同排法有A2种不同的排法，第二步由余下3的三人排中间位置共有不同的排法A3种。所以符合要求的不同排法总数为A3-A236种.3 33(3) 把A、B视为一个整体(AB),则(AB)，C，C，D，E的全排列数是A4种，再排AB则有A242种方法.因此符合要求的排法共有A4-A248种.42(4)A、B两人不相邻，有两种思考：用间接法，NA5A4A2=72种
15、.先排好C、D、E，然后现让A、B站到C、D、E5 42的空位(包括两端)，即排C、D、E有A3种方法，排A、B插空位有A2种方法，所以共有34A4-A248种.42(5)由于A的位置确定后，B的位置便可选择自已的位置。为此，可按A的位置进行分类：第#页共6页A在左数第第一位置的站法有AiA3种；A在左数第第二位置的站法有AiA3种；4 333A在左数第第三位置的站法有AiA3种；A在左数第第四位置的站法有AiA3种.23i3所以A在B的左边的不同站法共有“=A1A3+A1A3+A1A3+A1A3=60种.433323i3练习题：I. 用1,2,3,4,5这五个数字，组成没有得复数字的三位数，其中偶数共有(A)A.24个B.30个C.40个D.60个2 .有甲、乙、丙三项任务，甲需2人承担，乙、丙各需1人承担，从10人中选派4人承担这三项任务,不同的选取法共
