初三自主招生拓展内容教学案10排列组合拓展

第1页排列组合知识梳理:一、分类计数原理和分步计数原理（1）分类计数原理（加法原理）：做一件事情，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法。那么完成这件事共有N=m1+m2+…+mn种不同的方法。(2)分步计数原理（乘法原理）：做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事有N=m1×m2×…×mn种不同的方法。二、排列的概念一般地，从n个不同的元素中取出m个（m≤n）元素，按照一定的次序排成一列，叫做从n个不同的元素中取出m个元素的一个排列。根据排列的定义，两个排列相同，当且仅当两个排列的元素完全相同，且元素的排列次序也完全相同。从n个不同的元素中取出m个（m≤n）元素的所有排列的个数叫做从n个不同的元素中取出m个元素的排列数，用符号mnP表示。三、组合数一般地，从n个不同的元素取出m个（m≤n）元素组成一组，叫做从n个不同的元素中取出m个元素的一个组合。从排列组合的定义可以知道，排列与元素的次序有关，而组合与元素的次序无关，如果两个组合中的元素完全相同，那么不管元素的次序如何，都是相同的组合，只有当两个组合中的元素不完全相同是，才是不同的组合。从n个不同的元素中取出m（m≤n）个元素的所以组合的个数，叫做从n个不同的元素取出m个元素的组合数，用符号mnC表示。四、排列组合公式一般地，排列数mnP可以按照从n个不同的元素中选m个元素依次填入m个空位来考虑：显然第一个空位有n中方法，第二个空位有n-1中方法……，最后一个空位有n-m+1种方法，于是我们可以得到：nnP(1)(2)321nnn，即正整数1到n的连乘积，这个叫做n的阶乘，用!n表示，于是全排列数公式可以写成!nnPn。根据全排列公式，我们很容易推导出排列公式的另一种表示方法：!()!mnnPnm。为了使这个公式在m=n时也成立，我们规定0！=1。一般地，对于从n个不同的元素取出m个元素的排列数mnP，可以看作是由以下两部得到的：第2页第一步，先取出m个不同元素的组合，也就是mnC种；第二步，求这个组合中的m个元素的全排列数mnP，于是根据乘法原理，可以得到mmmnnmPCP。所以我们可以得到(1)(2)(1)!mmnnmmPnnnnmCPm，这里m≤n，这个公式叫做组合数公式。根据组合数公式和排列数公式的定义，我们很容易推导出组合数公式的另一种表示方法，即!!()!mnnCmnm。组合数的两个性质：（1）Cmn=Cmnn；（2）Cmn1=Cmn+C1mn.例题精讲：例1某铁路线上，在起点和终点之间原有7个车站，现在新增加了3个车站，这样需要增加多少种不同的车票？例2在6名内科医生和4名内科医生中，内科主任和外科主任各一名，现要组成5人医疗小组送医下乡，按照下列条件各有多少中选派方法？（1）有3名内科医生和2名外科医生；（2）既有内科医生，又有外科医生；（3）至少有一名主任参加；（4）既有主任，又有外科医生。第3页例3如图，中国象棋的棋子“车”按象棋中走法规则沿着棋盘路线的最短路径从左下角走到右上角，一共有多少种不同的走法？（注：中国象棋中，“车”每一步可以沿直线移动任意多格）例4a、b、c、d、e排成一排，依下列条件各有多少种排法？（1）a必须排在首位或末位；（2）a排在首位但b不排在末位；（3）a、b、c相邻；（4）a、b不相邻。同步练习：1.如图为25个小正方形组成的5×5棋盘，其中含有符号“#”的各种正方形共有个。第4页2.平面上有n个点，其中任意三点都是直角三角形的顶点，则n的最大值为。3.一青蛙在如图88的正方形（每个小正方形的边长为1）网格的格点（小正方形的顶点）上跳跃，青蛙每次所跳的最远距离为5，青蛙从点A开始连续跳六次正好跳回到点A，则所构成的封闭图形的面积的最大值是。4.在∠AOB的OA边上取m个点，在OB边上取n个点(均除O点外)，连同O点共m+n+1个点，现任取其中三个点为顶点作三角形，可作的三角形有()1212111121212121211211CCCD.CCCCCCC.CCCC.CBCCCA.Cnmnmnmmnnmmnnmmnnm5.6个人站成一行：（1）某甲不能站在排头，有多少种站法？（2）某甲既不能站在排头，也不能站在排尾，有多少种站法？（3）某甲不能站在排头，某乙不能站在排尾，有多少种站法？（4）甲乙两人要站在相邻位置，有多少种站法？（5）甲乙两人不能相邻而站，有多少种站法？A第5页6.班级有50名学生，现选派6名学牛参加社区活动，在下列情况中，各有多少种不同选法？（1）班长与冈支部书记都须入选；（2）班长与团支部书记只有1人入选；（3）班长与团支部书记都不人选；（4）班长与团支部书记至少1人入选；7.一次国际会议，从某大学外语系选出11名学生做翻译，两人既会英语，又会日语，5人只会英语，4人只会日语。现从这11人中选出4名当英语翻译，4名当日语翻译，求所有选法种数．第6页8.平面内有I1个点，每两点连成一条直线，共连得48条不同的直线．（1）这11个点中，有没有三点共线或多于三点共线的情况，若有的话则请说明情况．（2）以这11个点为顶点可以构成多少个三角形？参考答案【例题部分】例1：答案：60解：原来有车站7+2=9，现在有车站9+3=12。考虑每两个站点之间的往返车票起始站和终点站互异，所以新增的车票种类为221292()1327260CC种。例2：解：（1）先从6名内科医生中选3名，有3665420321C种选法；再从4名外科医生中选2名，共有2443621C种选法；根据乘法原理，一共有选派方法20×6=120种。（2）先考虑从10名医生中任意选派5人，有51010987625254321C种选派方法；再考虑只有外科医生或只有内科医生的情况。由于外科医生只有4人，所以不可能只选派外科医生。如果只派内科医生，有566C中选派方法。所以，一共有252-6=246种既有内科医生又有外科医生的选派方法。第7页（3）如果选1名主任，不是主任的8名医生要选4人，有488765221404321C种选派方法；如果选2名主任，则不是主任的8名医生要选3人，有388761156321C种选派方法。根据加法原理，一共有140+56=196中选派方法。（1）分两类讨论：1若选外科主任，则其余4人可以任意选取，有4998761264321C中选取方法；2若不选外科主任，则必选内科主任，且剩余4人不能全选内科医生，于是有4485876554326543214321CC种选取法。根据加法原理，一共有126+65=191中选派方法。例3：答案：106.解：中国象棋的棋子“车”按象棋中走法规则沿着棋盘路线的最短路径从左下角走到右上角，一共有106种不同的走法。例4：解：（）本问题可分两步进行，先在首末选一个位置将排上，有种方121aA法；然后在余下的四个位置排字母、、、有种方法。由分步计数原理，bcdeA44得：（种）排法。AA214448（）按先排，再排，最后排、、进行，共有（种）排218113133abcdeAAA法。（3）a、b、c相邻，可用“捆绑法”，先将a、b、c看做一个元素，与其余两个元素全排列，然后、、之间再全排列，共有（种）排法。abcAA333336（4）a、b不相邻，可用插空法，先将c、d、e全排列后，有四个空位，再排a、b，共有（种）排法。AA3342说明：对“在与不在”问题常优先考虑受限制的特殊元素或特殊位置；对“邻与不邻”问题则常使用“捆绑法”及“插空法”。第8页【同步练习部分】练习1：答案：14.解析：①含9个小正方形的大正方形有9个；2含有16个小正方的大正方形有4个；③25个小正方形的大正方形有1个；所以含有符号#的个各种正方形有14个。练习2：答案：4．练习3：答案：12解析：如图，青蛙从点A开始连续跳六次正好调回到点A，它所跳过的线段组成的图形是六边形，且边长为5，六边形的面积为12．练习4：答案：C解析：解法一第一类办法从OA边上(不包括O)中任取一点与从OB边上(不包括O)中任取两点，可构造一个三角形，有C1mC2n个；第二类办法从OA边上(不包括O)中任取两点与OB边上(不包括O)中任取一点，与O点可构造一个三角形，有C2mC1n个；第三类办法从OA边上(不包括O)任取一点与OB边上(不包括O)中任取一点，与O点可构造一个三角形，有C1mC1n个由加法原理共有N=C1mC2n+C2mC1n+C1mC1n个三角形解法二从m+n+1中任取三点共有C31nm个，其中三点均在射线OA(包括O点)，有C31m个，三点均在射线第9页OB(包括O点)，有C31n个所以，个数为N=C31nm－C31m－C31n个练习5：解析：解:练习6：解析：（1）从48名学生中挑选其余4人，故有448C种．（2）按乘法原理，有15248CC种．（3）从48名学生中挑选6人，故有648C种．（4）按加法原理，分班长与团支部书记中选1人与选2人两类，有（15248CC+448C）种．练习7：解析：解：把选法分为三类：从特殊元素入手考虑从特殊位置入手考虑间接法第（1）小题甲有5种选择1555PP排头可由其余5人中选1555PP6565PP第（2）小题甲有4种选择1545PP排头，排尾可由其余5人中选22454PP65652PP第（3）小题甲站排尾有55P种，甲站中间4位之一，乙除末位尚有4种选择51145444PPPP甲不站排头的所有种数排除乙站排尾的情况15P514544PPP6546542PPP第（4）小题甲紧邻乙左面的排法中先考虑甲，有5种选法，且乙紧靠甲，剩下4位有44P种，故1454PP，再注意甲右乙左故总数为142542PPP将甲乙并为一个元素5252PP624654PPP第（5）小题除甲乙外4人排好后，在这4人的5个间隙，排甲乙两人4245PP甲排排头，乙有4种选择；甲排第2位，乙有3种选择；甲排第3位乙有3种选择．由对称性得1414144434342PPPPPP652652PPP第10页（i）从5个只会英语的学生中选4人，则可从2名会两种语言和只会日语的4人中选口语翻译有46C种．按乘法原理这种情况下的翻译选法可有4456CC种．（ii）从5个只会英语的学生中选3人，则英语翻译有3152CC种，而这时日语翻译选法有45C种按乘法原理这种情况下的翻译选法可有3152CC45C种．（iii）从5个只会英语学生中选2人，则英语翻译有2252CC种，而这时口语翻译选法有44C种，按乘法原理这种情况下的翻译选法可有2252CC44C种．于是，所有选择总数为4456CC+3152CC45C+2252CC44C=185（种）．说明：完成选出4名英语翻译、4名日语翻译这件事必须确定分类标准，要求做到不重复、不遗漏诸如当从5名只会英语的翻译中选2人时，日语翻译就不可能从既会英语又会日语的人中选择．在确定5个只会英语的学生中选4名英语翻译的选法时，它分两步，其中第二步是确定日语翻译，故用乘法原理．当然本题还有其他分类方法．练习8：解析：解：（1）若无j点共线的情况，则这11个点每两点相连可得211C=55条直线，如果存在三点共线，则直线条数由23C降为l条，即减少2条．如果存在四点共线，则直线条数由24C降为l条，即减少5条．如果存在五点共线，则直线条数由25C降为l条，即减少9条．现减少了5548=7条直线，说明这48条直线上，有一条直线存在3个点，一条直线存在4个点，其余直线均只2个点．（2）若无三点共线的情况，则以11个点为顶点可构成311C=165个三角形，但同一条直线上的3点不能构成三