《排列组合基本问题教案.docx》由会员分享,可在线阅读,更多相关《排列组合基本问题教案.docx(5页珍藏版)》请在优知文库上搜索。
1、排列组合基本问题教案1 .排列的概念:从个不同元素中,任取相(J72)个元素(这里的被取元素各不相同)按照一定的顺序排成一列,叫做从个不同元素中取出机个元素的一个排列.2 .排列数的定义:从个不同元素中,任取用(tnn)个元素的所有排列的个数叫做从个元素中取出m元素的排列数,用符号A,l,l,表示3 .排列数公式:A,t,j,=n(n-1)(?-2)(n-m+y)(w,nNmn)4阶乘:!表示正整数1到的连乘积,叫做的阶乘,规定O!=1.nI5.排列数的另一个计算公式:A;=(n-n)6组合的概念:一般地,从个不同元素中取出m(m)个元素并成一组,叫做从个不同元素中取出m个元素的一个组合.7
2、.组合数的概念:从个不同元素中取出加()个元素的所有组合的个数,叫做从n个不同元素中取出根个元素的组合黎.用符号Cr表示.8 .组合数公式:Cm=望=(一1)(“一2),(-加+1)或C:=:(n,tnwN,且/n)-加(一7)!9 .组合数的性质1:C:=C;.规定:c=l;10 .组合数的性质2:Cz=C:+MT.题型讲作例1分别求出符合下列要求的不同排法的种数(1)6名学生排3排,前排1人,中排2人,后排3人;(2) 6名学生排成一排,甲不在排头也不在排尾;(3)从6名运动员中选出4人参加4X100米接力赛,甲不跑第一棒,乙不跑第四棒;(4) 6人排成一排,甲、乙必须相邻;(5) 6人排
3、成一排,甲、乙不相邻;(6) 6人排成一排,限定甲要排在乙的左边,乙要排在丙的左边(甲、乙、丙可以不相邻)解:(1)分排坐法与直排坐法一一对应,故排法种数为A:=720(2)甲不能排头尾,让受特殊限制的甲先选位置,有4种选法,然后其他5人选,有4;种选法,故排法种数为A:8=480(3)有两棒受限制,以第一棒的人选来分类:乙跑第一棒,其余棒次则不受限制,排法数为乙不跑第一棒,则跑第一棒的人有A:种选法,第四棒除了乙和第一棒选定的人外,也有种选法,其余两棒次不受限制,故有种排法,由分类计数原理,共有用+AA=252种排法(4)将甲乙“捆绑”成“一个元”与其他4人一起作全排列共有=240种排法(5
4、)甲乙不相邻,第一步除甲乙外的其余4人先排好;第二步,甲、乙选择已排好的4人的左、右及之间的空挡插位,共有(或用6人的排列数减去问题(2)后排列数为星一240=480)(6)三人的顺序定,实质是从6个位置中选出三个位置,然后排按规定的顺序放置这三人,其余3人在3个位置上全排列,故有排法=120种点评:排队问题是一类典型的排列问题,常见的附加条件是定位与限位、相邻与不相邻9例2假设在100件产品中有3件是次品,从中任意抽取5件,求下列抽取方法各多少种?(1)没有次品;(2)恰有两件是次品;(3)至少有两件是次品.解:(1)没有次品的抽法就是从97件正品中抽取5件的抽法,共有C)=64446024
5、种(2)恰有2件是次品的抽法就是从97件正品中抽取3件,并从3件次品中抽2件的抽法,共有CjC;=442320种(3)至少有2件次品的抽法,按次品件数来分有二类:第一类,从97件正品中抽取3件,并从3件次品中抽取2件,有种.第二类从97件正品中抽取2件,并将3件次品全部抽取,有CMC种.按分类计数原理有二M6976种.点评:此题是只选“元”而不排“序”的典型的组合问题,附加的条件是从不同种类的元素中抽取,应当注意:如果第(3)题采用先从3件次品抽取2件(以保证至少有2件是次品),再从余下的98件产品中任意抽取3件的抽法,那么所得结果是=466288种,其结论是错误的,错在“重复”:假设3件次品
6、是A、B、C,第一步先抽A、B第二步再抽C和其余2件正品,与第一步先抽A、C(或B、C),第二步再抽B(或A)和其余2件正品是同一种抽法,但在算式中算作3种不同抽法.例3求证:A3+=A:;Cr+MT+2C;=C震证明:利用排列数公式(7-l)!w(n-l)!左=rI-7n-tn-)!(n-tn)!(7-)(-1)!+w(77-1)!n.m.二向蕨=诉L,右另一种证法:(利用排列的定义理解)从n个元素中取m个元素排列可以分成两类:第一类不含某特殊元素。的排列有A3第二类含元素a的排列则先从(-1)个元素中取出G-1)个元素排列有AW种,然后将。插入,共有m个空档,故有机A3种,因此A3+A胃=
7、C利用组合数公式左,+n+2!(zw+1)!(m-1)(/H-1)(zz-zw+1)!m(/?-m)!+1)!(一机+1)!(m+ )(n- m +武+2Xe)=需21)! = M=右(n-mn-m+1)+m(m+1)+2(根+1)(一加+1)另法:利用公式c;=C3M推得左二(CF+cD+6+c:T)=C詈+c1=C僵=右点评:证明排列、组合恒等式通常利用排列数、组合数公式及组合数基本性质.例4已知/是集合A=,O,c,d到集合B=0,1,2的映射(1)不同的映射了有多少个?(2)若要求/()+/0)+f(c)+/(d)=4则不同的映射了有多少个?分析:(1)确定一个映射了,需要确定,b,c
8、,d的像(2) ,6,c,d的象元之和为4,则加数可能出现多种情况,即4有多种分析方案,各方案独立且并列需要分类计窠解:(I)A中每个元都可选0,1,2三者之一为像,由分步计数原理,共有3333=3个不同映射.(2)根据,6,c,d对应的像为2的个数来分类,可分为三类:第一类:没有元素的像为2,其和又为4,必然其像均为1,这样的映射只有一个;第二类:一个元素的像是2,其余三个元素的像必为0,1,这样的映射有=12个;第三类:二个元素的像是2,另两个元素的像必为0,这样的映射有C:=6个.由分类计数原理共有1+12+6=19(个)点评:问题(1)可套用投信模型:n封不同的信投入m个不同的信箱,有
9、加种方法;问题(2)的关键结合映射概念恰当确定分类标准,做到不重、不漏.例5四面体的顶点和各棱的中点共10个点(1)设一个顶点为A,从其他9点中取3个点,使它们和点A在同一平面上,不同的取法有多少种?的取法有上,除点A有3C;种(2)在这10点中取4个不共面的点,不同多少种?解:(1)如图,含顶点A的四面体的三个面外都有5个点,从中取出3点必与点A共面,共取法,含顶点A的棱有三条,每条棱上有3个点,它们与所对棱的中点共面,共有3种取法根据分类计数原理和点A共面三点取法共有3C:+3=33种.(2)取出的4点不共面比取出的4点共面的情形要复杂,故采用间接法:先不加限制任取4点(C彳种取法)减去4
10、点共面的取法.取出的4点共面有三类:第一类:从四面体的同一个面上的6点取出4点共面,有4C:种取法第二类:每条棱上的3个点与所对棱的中点共面,有6种取法第三类:从6条棱的中点取4个点共面,有3种取法根据分类计数原理4点共面取法共有4C:+6+3=69故取4个点不共面的不同取法有CI一(4C;+6+3)=141(种)点评:由点构成直线、平面、几何体等图形是一类典型的组合问题,附加的条件是点共线与不共线,点共面与不共面,线共面与不共面等.小结:m个不同的元素必须相邻,有种“捆绑”方法m个不同元素互不相邻,分别“插入”到n个“间隙”中的m个位置有P:种不同的“插入”方法.m个相同的元素互不相邻,分别“插入”到n个“间隙”中的m个位置,有C:种不同的“插入”方法.若干个不同的元素“等分”为m个组,要将选取出每一个组的组合数的乘积除以rm