排列组合综合应用问题.ppt

《排列组合综合应用问题.ppt》由会员分享，可在线阅读，更多相关《排列组合综合应用问题.ppt（28页珍藏版）》请在三一办公上搜索。

1、,排列组合综合应用题,回顾,引入：前面我们已经学习和掌握了排列组合问题的求解方法，下面我们要在复习、巩固已掌握的方法的基础上，学习和讨论排列、组合的综合问题。和应用问题。,问题：解决排列组合问题一般有哪些方法？应注意什么问题？,解排列组合问题时，当问题分成互斥各类时，根据加法原理，可用分类法；当问题考虑先后次序时，根据乘法原理，可用位置法；上述两种称“直接法”,当问题的反面简单明了时，可通过求差排除法,采用“间接法”；另外，排列中“相邻”问题可采用捆绑法；“分离”问题可用插空法等。,解排列组合问题，一定要做到“不重”、“不漏”。,排列组合、不重不漏,注意问题：,解题方法：,互斥分类-分类法,先

2、后有序-位置法,反面明了-排除法,相邻排列-捆绑法,分离排列-插空法,2,一.排列组合综合问题,例1：有12 人。按照下列要求分配，求不同的分法种数。,分为两组，一组7人，一组 5人；,分为甲、乙两组，甲组 7人，乙组5人；,分为甲、乙两组，一组 7人，一组5人；,分为甲、乙两组，每组6人；,分为两组，每组 6人；,要求：审清题意、仔细分析、周密考虑、防止重漏。,分析：把12 人分成两组，一组7人，一组5人与把12人分成甲、乙两组，甲组7人，乙组5人，实质上是一样的，都必须分成两步：第一步从12 人中选出7人组成一组（或甲组）有C127种方法；第二步，剩余的5人组成一组（或乙组）有C55种方法

3、。所以总的分配种数为C127.C55种。所以、分配种数都为C127.C55,分 配 问 题,思考：把12 人分为甲、乙两组，一组7人，一组5人,与 比较,有何相同和不同地方?,相同地方都是分成两组,一组7 人,一组5 人,有C127.C55种；所不同的是一组7人，一组5人，并没有指明甲乙谁是7人，谁是5人，要考虑甲乙的顺序，所以要再乘以P22，所以总的种数为C127.C55.A22。,点评：上述问题是非平均分配问题，没有指出组名给出了组名，而且指明了谁是几个人。这在非平均分配中是一样的。而 虽然给出了组名，却没有指明谁是几个人，所以这时有顺序问题。,注意：求给出了组名，却没有指明哪组多少人的种

4、数，可以先算未给出组名（或给出组名并指明哪组多少人）的种数，然后乘以组数的阶乘。,分为甲、乙两组，一组 7人，一组5人；,分析：把12个人分为甲、乙两组，每组6人，可分成两步，第一步，从12人中抽出6人给甲组，有C126种，余下的6人给乙组有C66种，所以共有C126.C66种.,由于没有组名，与比较，显然分成甲、乙两组是有顺序的，如123456分在甲组与123456分在乙组是不一样的，而作为分成两组却是一样的。有顺序的多，无顺序的少，象非平均分配一样，有组名的种数应该是无组名的种数的关于组数的阶乘倍。所以在的基础上除以组数的阶乘，即12个人分为两组，每组 6人的种数为C126.C66/A22

5、种。,点评：上述 属于平均分配问题，求没有给出组名的种数，可以先求给出组名的种数，再除以组数的阶乘！,分为甲、乙两组，每组6人；,分为两组，每组 6人；,分为三组，一组5人，一组4人，一组3人；,分为甲、乙、丙三组，甲组5人，乙组4人，丙组3人；,分为甲、乙、丙三组，一组5人，一组4人，一组3人；,分为甲、乙、丙三组，每组4人；,分为三组，每组4人。,练习1：有12 人。按照下列要求分配，求不同的分法种数。,答案,C125.C74.C33,C125.C74.C33,C125.C74.C33.A33,C124.C84.C44,分成三组，其中一组2人，另外两组都是 5人。,小结：例1与练习1说明了

6、非平均分配、平均分配以及部分平均分配问题。,1.非平均分配问题中，没有给出组名与给出组名是一样的，可以直接分步求；给出了组名而没指明哪组是几个，可以在没有给出组名（或给出组名但不指明各组多少个）种数的基础上乘以组数的全排列数。,2.平均分配问题中，给出组名的分步求；若没给出组名的，一定要在给出组名的基础上除以组数的全排列数。,3.部分平均分配问题中，先考虑不平均分配，剩下的就是 平均分配。这样分配问题就解决了。,结论：给出组名(非平均中未指明各组个数）的要在未给出组名的种数的基础上，乘以组数的阶乘。,例2：求不同的排法种数。6男2女排成一排，2女相邻；6男2女排成一排，2女不能相邻；4男4女排

7、成一排，同性者相邻；4男4女排成一排，同性者不能相邻。,分析：由2女捆绑成一人与6男全排列,再把2女全排列，有A77.A22种“捆绑法”,把6男2女8人全排列，扣去 2 女“相邻”就是2女“不相邻”，所以有A88-A77.A22种。“排除法”,还可用“插空法”直接求解：先把6男全排列，再在6男相邻的7个空位中排2女，所以共有A66.A72种.,分 离 排 列 问 题,思考:对于不相邻的分离排列能否都用“排除法”?若改5男3女排成一列,3女不相邻,用排除法得 对吗?,(反面不明了:有3女相邻，两两相邻等几种情况。),4男4女排成一列，同性者相邻，把4男、4女捆绑成一个排列，然后同性者之间再全排列

8、，所在地共有A22.A44.A44种。“捆绑法”,本题可否用排除法得排列总数为：A88-A22.A44.A44；或用简单插空法得排列总数为：A44.A54?,错！用排除法时，反面要明了，而这里反面不明了，还有2人或3人相邻的。用简单插空法可能出现两男或两女相邻的情况。如“女男男女男女男女”。,同性不相邻必须男女都排好，即男奇数位，女偶数位，或者对调。总排列数为A22.A44.A44种。,由此可见，分离排列问题，不能简单地用插空法或排除法要根据具体的情况具体分析。,例3：某乒乓球队有8男7女共15名队员，现进行混合双打训练，两边都必须要1男1女，共有多少种不同的搭配方法。,分析：每一种搭配都需要

9、2男2女，所以先要选出2男2女，有C82.C72种；,然后考虑2男2女搭配，有多少种方法？,男女-男女,Aa-Bb,Ab-Ba,Bb-Aa,Ba-Ab,显然：与；与在搭配上是一样的。所以只有2种方法，所以总的搭配方法有2 C82.C72种。,搭 配 问 题,先组后排,例4:高二某班要从7名运动员出4名组成4100米接力队，参加校运会，其中甲，乙两人都不跑中间两棒的安排方法有多少种？,分析：从7人中选出4人分别安排在第一、二、三、四棒这个事，与组合和排列都有关，这里对甲、乙又有特殊的要求，这就有几种不同的情况，所以要分类考虑，先考虑4人的选取有几类？再考虑谁跑哪棒。,直接法：先组：分三类。第一类

10、，没有甲、乙，有C54种；第二类，有甲无乙或有乙无甲，有 2C53种；第三类，既有甲又有乙。有C52种。,分 离 排 列 问 题,引例（曾经作过的题）：4名运动员出组成4100米接力队，参加校运会，其中甲，乙两人不同时跑中间两棒的安排方法有多少种？,第一类无甲乙情况：可把4人全排列，有A44 种；第二类甲乙只有一人情况：甲或乙 先考虑有A21种余下的三人全排列有A33种；第三类甲乙都有的情况：先考虑甲乙有A22种，余下的有A22种。,所以，第一类有C54.A44种,第二类有2C53.A21.A32种,第三类有C52.A22.A22种。由加法原理；总的安排方法有 N=C54.A44+2C53.A

11、21.A33+C52.A22.A22（种）,注意：排列组合综合题在求解中的分类十分重要，大家要认真体会，理解其思路和方法是先组后排。,再考虑每一类中要如何安排棒数？,本例很难象引例那样用间接法解。,课堂小结,本节课，对几个例子的分析讨论，总结了分配问题，分离排列问题，以及排列组合综合题的解法。,解排列组合综合题一般应遵循：“先组后排”的原则。解题时一定要注意“不重、不漏”。,解题方法：,互斥分类-分类法,先后有序-位置法,反面明了-排除法,相邻排列-捆绑法,分离排列-插空法,练 习,1.某班有23男37女共60名学生，拟派出2个辩论队，每队3人，各1男2女，共有多少种不同的搭配方法。,2.高二

12、要从全级10名独唱选手中选出6名在歌咏会上表演，出场安排甲，乙两人都不唱中间两位的安排方法有多少种？,练 习,3.15 人按照下列要求分配，求不同的分法种数。,(1)分为三组，每组5人,共有_ 种不同的分法。,（2）分为甲、乙、丙三组，一组7人，另两组各4人，共有_种不同的分法。,（3）分为甲、乙、丙三组，一组6人，一组5人，一组4人，共有_种不同的分法。,4.8名同学选出4名站成一排照相，其中甲、乙两人都不站中间两位的排法有_种。,5.某班有27名男生13女生，要各选3人组成班委会和团支部每队3人，3人中2男1女，共有_ 种不同的选法。,（一）.有条件限制的排列问题,例1：5个不同的元素a,

13、b,c,d,e每次取全排列。a,e必须排在首位或末位，有多少种排法？a,e既不在首位也不在末位，有多少种排法？a,e排在一起多少种排法？a,e不相邻有多少种排法？a在e的左边（可不相邻）有多少种排法？,解：（解题思路）分两步完成，把a,e排在首末两端有A22种，再把其余3个元素排在中间3个位置有A33种。由乘法共有A22.A33=12(种)排法。,要求：开动脑筋，积极思维，不同解法，大胆说出。,点评：问题是排列问题中某几个元素必须“在”某些位置的问题，处理这类问题的原则是：有条件限制的元素或位置优先考虑。(优限法),二.排列组合应用问题,解：（解题思路1）先从b,c,d三个选其中两个排在首末两

14、位，有A32种，然后把剩下的一个与a,e排在中间三个位置有A33种，由乘法原理:共有A32.A33=36种排列.,点评：上述运用了“优限法”，既有条件限制的位置优先考虑的原则，这种解法是直接法。,（解题思路2）从反面考虑“排除法”，既间接法。,A55是5 个元素的全排列数，减去a,e分别在排头、排尾的4种情况有4A44种。但A55-4A44=24种。,上述解法哪个对，哪个错？错在哪里？,分析：减去a,e分别在排头、排尾的4种情况用图示表示即：,由图示可看出：四种情况中a排头e排尾；e 排头a 排尾各多减了一次。（遗漏）必须补回，既加上2A33种。,所以间接法的正确答案为：A55-4A44+2A

15、33（种）排法。,说明：在解题过程中，有时用“排一排”会使思路更清楚。“具体排”是一种好方法，它是把抽象转化为具体的一种思 维方法,解：（解题思路）a,e排在一起，可以将a,e看成一个整体,作为一个元素与其它3个元素全排列，有A44种；a,e两个元素的全排列数为A22种，由乘法原理共有A44.A22(种)排列。,说明：相邻元素排在一起，相当捆绑起来，既“捆绑法”，捆绑的元素还必须进行全排列。,解：（解题思路）a,e不相邻的反面是a,e相邻，反面明了，可利用“排除法”，即用5个元素的全排列数A55，扣除a,e排在一起排列数A44.A22，则a,e不相邻的排列总数为A55-A44.A22（种）,对

16、不相邻元素的排列问题，一般的还可以利用“插空法”解决。即把a,e以外的三个元素全排列有A32种，再把a,e插入三个元素排定后形成的4个空位上有A42种，由乘法原理共有A32.A42(种),说明:对不相邻元素的排列问题,一般采用“插空法”对反面明了的,可用“排除法”,解:（解题思路）a在e的左边(可不相邻)，这表明a,e只有一种顺序，但a,e间的排列数为A22，所以，可把5个元素全排列得排列数A55，然后再除以a,e的排列数A22。所以共有排列总数为A55/A22（种）,注意：若是3个元素按一定顺序，则必须除以排列数 P33。,点评：排列应用题是实际问题的一种，其指导思想：弄清题意，联系实际，合

17、理设计，调动相关知识和方法。本 例是排列的典型问题，解题方法可 借鉴。排列问题思考比较抽象，“具体排”是一种把抽象转化具体 的好方法。,例2：已知集合A=1，2，3，4，5，6，7，8，9求含有5个元素，且其中至少有两个是偶数的子集的个数。,（二）有条件限制的组合问题：,解法1：5个元素中至少有两个是偶数可分成三类：2个偶数，3个奇数；3个偶数，2个奇数；4个偶数，1个奇数。所以共有子集个数为 C42.C53+C43.C52+C44.C51=105,解法2：从反面考虑，全部子集个数为P95，而不符合条件的有两类：5 个都是奇数；4个奇数，1个偶数。所以共有子集个数为C95-C55-C54.C4

18、1=105,下面解法错在哪里?,例2：已知集合A=1，2，3，4，5，6，7，8，9求含有5个元素，且其中至少有两个是偶数的子集的个数。,至少有两个偶数，可先由4个偶数中取2个偶数，然后再由剩下的7个数中选3个组成5个元素集合且满足至少有2个是偶数。成以共有子集C42.C73=210(个),用“具体排”来看一看是否重复，如C42中的一种选法是：选4个偶数中的2，4，又C73中选剩下的3个元素不6，1，3组成集合2，4，6，1，3，；再看另一种选法：由C42 中选4个偶数中的4，6，又C73中选剩下的3个元素不2，1，3组成集合4，6，2，1，3。显然这是两个相同和子集，所以重复了。重复的原因是

19、分类不独立。,（三）排列组合混合问题：,例3：从6名男同学和4名女同学中，选出3名男同学和2名女同学分别承担A，B，C，D，E5项工作。一共有多少种分配方案。,解1：分三步完成，1.选3名男同学有C63种，2.选2名女同学有C42种，3.对选出的5人分配5种不同的工作有A55种，根据乘法原理共有C63.C42.A55=14400(种).,那么下列的解法错在哪里?,从6名男的选出3名排列有A63种,又从4名女的选出2名排列,有A42种,所以有A63.A63=1440(种).显然少了,错在哪?,错在A63中排在哪3个位置,不明确.同理A42中排在哪2位亦不明确,所以产生了遗漏现象.,例3：从6名男

20、同学和4名女同学中，选出3名男同学和2名女同学分别承担A，B，C，D，E5项工作。一共有多少种分配方案。,解2：把工作当作元素，同学看作位置，1.从5种工作中任选3种（组合问题）分给6个男同学中的3人（排列问题）有C53.A63种,第二步,将余下的2个工作分给4个女同学中的2人有A42种.根据乘法原理共有C53.A63.A42=14400(种).亦可先分配给女同学工作,再给男同学分配工作,分配方案有C52.A42.A63=14400(种).,点评:对排列组合的混合问题，解题的关键是要合理分步：在分步时一般先组合后排列，这样才能做到不重不漏。,课堂小结,排列组合应用题与实际是紧密相连的，但思考起

21、来又比较抽象。“具体排”是抽象转化为具体的桥梁，是解题的重要思考方法之一。“具体排”可以帮助思考，可以找出重复，遗漏的原因。有同学总结解排列组合应用题的方法是“想透，排够不重不漏”是很有道理的。,解排列组合应用题最重要的是，通过分析构想设计合理的解题方案，在这里抽象与具体，直接法与间接法，全面分类与合理分步等思维方法和解题策略得到广泛运用。,典 型 题,1.4名优等生被保送到3所学校，每所学校至少得1名，则不同的保送方案总数为（）。（A)36(B)24(C)12(D)6,2.若把英语单词“error”中字母的拼写顺序写错了，则可能出现的错误的种数是（）（A)20(B)19(C)10(D)69,3.小于50000且含有两个5，而其它数字不重复的五位数有（）个。（A)(B)(C)(D),A,B,B,互斥分类-分类法,先后有序-位置法,反面明了-排除法,相邻排列-捆绑法,分离排列-插空法,解排列组合综合应用题一般应遵循：“先组后排”的原则。解题时一定要注意“不重、不漏”。,解题方法：,