排列组合基本问题教案.docx

《排列组合基本问题教案.docx》由会员分享，可在线阅读，更多相关《排列组合基本问题教案.docx（4页珍藏版）》请在优知文库上搜索。

1、排列组合根本问题教案1 .排列的概念：从个不同元素中，任取出(mt)个元素(这里的被取元素各不相同)按照.一牢的蜘芋排成一列，叫做从个不同元素中取出m个元素的1个琲烈.2 .排列数的定义：从个不同元素中，任取加(m)个元素的所有排列的个数叫做从个元素中取出M元素的排列数，用符号A；表示.3 .排列数公式：=n(n-)(n-2)(n-m+Y)(m,neN0,mn)4阶乘：!表示正整数1到的连乘积，叫做的阶乘规定O!=1.5 .排列数的另一个计算公式：A：=邛；(n-m)6组合的概念：一般地，从个不同元素中取出团(m)个元素并成一组，叫做从个不同元素中取出m个元素的一个组合7 .组合数的概念：从个

2、不同元素中取出团(m)个元素的所有组合的个数，叫做从个不同元素中取出小个元素的级令怨用符号C：表示.8 .组合数公式：C二女=-1)(-2)(？+1)A：加nl或C；=:(/?,mwN*,且加)-ml(n-m)9组合数的性质1：C：=C；m.规定:c=l;10.组合数的性质2：CM-T.题型讲蟀例1分别求出符合以下要求的不同排法的种数(1) 6名学生排3排，前排1人，中排2人，后排3人；(2) 6名学生排成一排，甲不在排头也不在排尾；(3)从6名运发动中选出4人参加4X100米接力赛，甲不跑第一棒，乙不跑第四棒；(4) 6人排成一排，甲、乙必须相邻；(5) 6人排成一排，甲、乙不相邻；(6)

3、6人排成一排，限定甲要排在乙的左边，乙要排在丙的左边(甲、乙、丙可以不相邻).解：(1)分排坐法与直排坐法一一对应，故排法种数为A：=720(2)甲不能排头尾，让受特殊限制的甲先选位置，有A：种选法，然后其他5人选，有种选法,故排法种数为A；A；=480（3）有两棒受限制，以第一棒的人选来分类：乙跑第一棒，其余棒次那么不受限制，排法数为4；乙不跑第一棒，那么跑第一棒的人有A：种选法，第四棒除了乙和第一棒选定的人外，也有A：种选法，其余两棒次不受限制，故有用种排法，由分类计数原理，共有A；+A：=252种排法（4）将甲乙“捆绑”成“一个元”与其他4人一起作全排列共有=240种排法（5）甲乙不相邻

4、，第一步除甲乙外的其余4人先排好；第二步，甲、乙选择已排好的4人的左、右及之间的空挡插位，共有A：&（或用6人的排列数减去问题（2）后排列数为A：-240=480）（6）三人的顺序定，实质是从6个位置中选出三个位置，然后排按规定的顺序放置这三人，其余3人在3个位置上全排列，故有排法C：A；=120种点评：排队问题是一类典型的排列问题，常见的附加条件是定位与限位、相邻与不相邻.例2假设在100件产品中有3件是次品，从中任意抽取5件，求以下抽取方法各多少种？（1）没有次品；（2）恰有两件是次品；（3）至少有两件是次品.解：（1）没有次品的抽法就是从97件正品中抽取5件的抽法，共有C*=644460

5、24种（2）恰有2件是次品的抽法就是从97件正品中抽取3件，并从3件次品中抽2件的抽法，共有Cl1C1=442320种（3）至少有2件次品的抽法，按次品件数来分有二类：第一类，从97件正品中抽取3件，并从3件次品中抽取2件，有种.第二类从97件正品中抽取2件，并将3件次品全部抽取，有C*C；种.按分类计数原理有=446976种。点评：此题是只选“元”而不排“序”的典型的组合问题，附加的条件是从不同种类的元素中抽取,应当注意：如果第（3）题采用先从3件次品抽取2件（以保证至少有2件是次品），再从余下的98件产品中任意抽取3件的抽法，那么所得结果是C；C；s=466288种，其结论是错误的，错在“

6、重复”：假设3件次品是A、B、C,第一步先抽A、B第二步再抽C和其余2件正品，与第一步先抽A、C（或B、C）,第二步再抽B（或A）和其余2件正品是同一种抽法，但在算式CjCl中算作3种不同抽法.例3求证：A3+核二：=A；C：向+C,+2C;=C证明：利用排列数公式左(-l)!n(w-l)!(2-w-l)!n-m)!_(一根)(-l)!+m(-l)!n_,_=而6=西L，-另一种证法：(利用排列的定义理解)从n个元素中取m个元素排列可以分成两类：第一类不含某特殊元素。的排列有A3第二类含元素的排列那么先从(-1)个元素中取出(机-1)个元素排列有A：种，然后将插入，共有m个空档，故有LA；?种

7、，因此心+”播=A：利用组合数公式左_！+”+2！(m+l)!(nm-l)(m-l)(n-m+l)!m(n-m)=7rX-(-?)(-7?2+1)+m(m+1)+2(加+1)(一机+1)m+)n-m+)=7r(h+2X2+1)=7-r=C%=右(tn+)(t-tn+)(tn+l)l(n-m+1)!另法：利用公式c：=C3+CM推得左=(cr,c;)+(c;+C,)=CT+C3=C霜=右点评：证明排列、组合恒等式通常利用排列数、组合数公式及组合数根本性质.例4/是集合A=也c,4到集合B=0,1,2的映射(1)不同的映射了有多少个？(2)假设要求/()+f伍)+(c)+/(d)=4那么不同的映射

8、/有多少个？分析：(1)确定一个映射了,需要确定,b,c,d的像(2) 4,6,c,d的象元之和为4,那么加数可能出现多种情况，即4有多种分析方案，各方案独立且并列需要分类计算.解：(1)A中每个元都可选0,1,2三者之一为像，由分步计数原理，共有3333=3个不同映射(2)根据6,c,d对应的像为2的个数来分类，可分为三类:第一类：没有元素的像为2,其和又为4,必然其像均为1,这样的映射只有一个；第二类：一个元素的像是2,其余三个元素的像必为0,1，这样的映射有C：H=I2个；第三类：二个元素的像是2,另两个元素的像必为0,这样的映射有C：=6个.由分类计数原理共有1+12+6=19（个）.

9、点评：问题（1）可套用投信模型：n封不同的信投入m个不同的信箱，有M种方法；问题（2）的关键结合映射概念恰当确定分类标准，做到不重、不漏.例5四面体的顶点和各棱的中点共10个点使它们和点A在同一平面上，不同的取法有多少（1）设一个顶点为A,从其他9点中取3个点，种？取法.它们与所对棱的中点的取法有多少种？上，除点A外都有5（2）在这10点中取4个不共面的点，不同解：（1）如图，含顶点A的四面体的三个面个点，从中取出3点必与点A共面，共有3C；种含顶点A的棱有三条，每条棱上有3个点，.共面，共有3种取法.B根据分类计数原理和点A共面三点取法共有3C；+3=33种.（2）取出的4点不共面比取出的4

10、点共面的情形要复杂，故采用间接法：先不加限制任取4点（GI）种取法）减去4点共面的取法.取出的4点共面有三类：第一类：从四面体的同一个面上的6点取出4点共面，有4C；种取法第二类：每条棱上的3个点与所对棱的中点共面，有6种取法第三类：从6条棱的中点取4个点共面，有3种取法根据分类计数原理4点共面取法共有4C：+6+3=69故取4个点不共面的不同取法有-（4C：+6+3）=（种）点评：由点构成直线、平面、几何体等图形是一类典型的组合问题，附加的条件是点共线与不共线,点共面与不共面，线共面与不共面等.小结：m个不同的元素必须相邻，有匕种“捆绑”方法.m个不同元素互不相邻，分别“插入”到n个“间隙”中的m个位置有P：种不同的“插入”方法.m个相同的元素互不相邻，分别“插入”到n个“间隙”中的m个位置，有C：种不同的“插入”方法.假设干个不同的元素“等分”为m个组，要将选取出每一个组的组合数的乘积除以2：