排列组合问题

WESTWOOD行政職業能力測验版WESTWOOD 写在前面的话 1、朋友们的热心，是qzzn(求职指南论坛)行政职业能力测试版发展的动力！也是加入到qzzn的各位朋友共有的财富！ 2、所有汇编资料，免费提供，仅供大家交流和学习。请在学习结束后，自行删除! 3、严禁用于商业用途！ 4、希望在公务员考试的道路上，有qzzn，有行政职业能力测试版的陪伴，大家能同进步、共发展！ 5、请大家支持视频教程网，这是一个不错的网站！http://www.abab123.com/bbs/down.asp?html=872039 6、最后，祝愿大家在即将的考试中，金榜题名，马到成功！ qzzn(求职指南论坛) 行政职业能力测试版 版主 westwood 2006年3月2日 课 题： 小结与复习 (一) 排列组合问题I 一、知识点： 1分类计数原理：做一件事情，完成它可以有n类办法，在第一类办法中有 种不同的方法，在第二类办法中有 种不同的方法，……，在第n类办法中有 种不同的方法那么完成这件事共有 种不同的方法 2.分步计数原理：做一件事情，完成它需要分成n个步骤，做第一步有 种不同的方法，做第二步有 种不同的方法，……，做第n步有 种不同的方法，那么完成这件事有 种不同的方法 3．排列的概念：从 个不同元素中，任取 （ ）个元素（这里的被取元素各不相同）按照一定的顺序排成一列，叫做从 个不同元素中取出 个元素的一个排列 4．排列数的定义：从 个不同元素中，任取 （ ）个元素的所有排列的个数叫做从 个元素中取出 元素的排列数，用符号 表示 5．排列数公式： （ ） 6 阶乘： 表示正整数1到 的连乘积，叫做 的阶乘规定 ． 7．排列数的另一个： = 8 组合的概念：一般地，从 个不同元素中取出 EMBED Equation.DSMT4 个元素并成一组，叫做从 个不同元素中取出 个元素的一个组合 9．组合数的概念：从 个不同元素中取出 EMBED Equation.DSMT4 个元素的所有组合的个数，叫做从 个不同元素中取出 个元素的组合数．用符号 表示． 10．组合数公式： 或 EMBED Equation.3 11 组合数的性质1： ．规定： ； 2： ＝ + 二、解题思路： 解排列组合问题，首先要弄清一件事是“分类”还是“分步”完成，对于元素之间的关系，还要考虑“是有序”的还是“无序的”，也就是会正确使用分类计数原理和分步计数原理、排列定义和组合定义，其次，对一些复杂的带有附加条件的问题，需掌握以下几种常用的解题方法： 特殊优先法 对于存在特殊元素或者特殊位置的排列组合问题，我们可以从这些特殊的东西入手，先解决特殊元素或特殊位置，再去解决其它元素或位置，这种解法叫做特殊优先法.例如：用0、1、2、3、4这5个数字，组成没有重复数字的三位数，其中偶数共有________个.（答案：30个） 科学分类法 对于较复杂的排列组合问题，由于情况繁多，因此要对各种不同情况，进行科学分类，以便有条不紊地进行解答，避免重复或遗漏现象发生例如：从6台原装计算机和5台组装计算机中任取5台，其中至少有原装与组装计算机各两台，则不同的选取法有_______种.（答案：350） 插空法 解决一些不相邻问题时，可以先排一些元素然后插入其余元素，使问题得以解决例如：7人站成一行，如果甲乙两人不相邻，则不同排法种数是______.(答案:3600) 捆绑法相邻元素的排列，可以采用“整体到局部”的排法，即将相邻的元素当成“一个”元素进行排列，然后再局部排列例如：6名同学坐成一排，其中甲、乙必须坐在一起的不同坐法是________种.（答案：240） 排除法 从总体中排除不符合条件的方法数，这是一种间接解题的方法. b、排列组合应用题往往和代数、三角、立体几何、平面解析几何的某些知识联系，从而增加了问题的综合性，解答这类应用题时，要注意使用相关知识对答案进行取舍.例如：从集合{0，1，2，3，5，7，11}中任取3个元素分别作为直线方程Ax+By+C=0中的A、B、C，所得的经过坐标原点的直线有_________条.（答案：30） 三、讲解范例： 例1 由数字１、２、３、４、５、６、７组成无重复数字的七位数 (1）求三个偶数必相邻的七位数的个数；（2）求三个偶数互不相邻的七位数的个数 解 (1)：因为三个偶数２、４、６必须相邻，所以要得到一个符合条件的七位数可以分为如下三步： 第一步将１、３、５、７四个数字排好有 种不同的排法； 第二步将２、４、６三个数字“捆绑”在一起有 种不同的“捆绑”方法; 第三步将第二步“捆绑”的这个整体“插入”到第一步所排的四个不同数字的五个“间隙”(包括两端的两个位置)中的其中一个位置上,有 种不同的“插入”方法 根据乘法原理共有 ＝720种不同的排法所以共有720个符合条件的七位数 解（2）：因为三个偶数２、４、６ 互不相邻，所以要得到符合条件的七位数可以分为如下两步： 第一步将１、３、５、７四个数字排好，有 种不同的排法； 第二步将２、４、６分别“插入”到第一步排的四个数字的五个“间隙”（包括两端的两个位置）中的三个位置上，有 种“插入”方法 根据乘法原理共有 ＝1440种不同的排法所以共有1440个符合条件的七位数 例２ 将Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ分成三组，共有多少种不同的分法？ 解：要将Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ分成三组，可以分为三类办法： （１－１－４）分法、（１－２－３）分法、（２－２－２）分法 下面分别计算每一类的方法数： 第一类（１－１－４）分法，这是一类整体不等分局部等分的问题，可以采用两种解法 解法一：从六个元素中取出四个不同的元素构成一个组，余下的两个元素各作为一个组，有 种不同的分法 解法二：从六个元素中先取出一个元素作为一个组有 种选法，再从余下的五个元素中取出一个元素作为一个组有 种选法，最后余下的四个元素自然作为一个组，由于第一步和第二步各选取出一个元素分别作为一个组有先后之分，产生了重复计算，应除以 所以共有 ＝15种不同的分组方法 第二类（１－２－３）分法，这是一类整体和局部均不等分的问题，首先从六个不同的元素中选取出一个元素作为一个组有 种不同的选法，再从余下的五个不同元素中选取出两个不同的元素作为一个组有 种不同的选法，余下的最后三个元素自然作为一个组，根据乘法原理共有 ＝60种不同的分组方法 第三类（２－２－２）分法，这是一类整体“等分”的问题，首先从六个不同元素中选取出两个不同元素作为一个组有 种不同的取法，再从余下的四个元素中取出两个不同的元素作为一个组有 种不同的取法，最后余下的两个元素自然作为一个组由于三组等分存在先后选取的不同的顺序，所以应除以 ，因此共有 ＝15种不同的分组方法 根据加法原理，将Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ六个元素分成三组共有：15＋60＋15＝90种不同的方法 例３ 一排九个坐位有六个人坐，若每个空位两边都坐有人，共有多少种不同的坐法？ 解：九个坐位六个人坐，空了三个坐位，每个空位两边都有人，等价于三个空位互不相邻，可以看做将六个人先依次坐好有 种不同的坐法，再将三个空坐位“插入”到坐好的六个人之间的五个“间隙”（不包括两端）之中的三个不同的位置上有 种不同的“插入”方法 根据乘法原理共有 ＝7200种不同的坐法 排列组合问题II 一、相临问题——整体捆绑法 例1．7名学生站成一排，甲、乙必须站在一起有多少不同排法？ 解：两个元素排在一起的问题可用“捆绑”法解决，先将甲乙二人看作一个元素与其他五人进行排列，并考虑甲乙二人的顺序，所以共有 种。 捆绑法:要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列,同时要注意合并元素内部也可以作排列.一般地: 个人站成一排,其中某 个人相邻,可用“捆绑”法解决，共有 种排法。 练习：5个男生3个女生排成一排,3个女生要排在一起,有多少种不同的排法? 分析 此题涉及到的是排队问题,对于女生有特殊的限制,因此,女生是特殊元素,并且要求她们要相邻,因此可以将她们看成是一个元素来解决问题. 解 因为女生要排在一起,所以可以将3个女生看成是一个人,与5个男生作全排列,有 种排法,其中女生内部也有 种排法,根据乘法原理,共有 种不同的排法. 二、不相临问题——选空插入法 例2． 7名学生站成一排，甲乙互不相邻有多少不同排法？ 解：甲、乙二人不相邻的排法一般应用“插空”法，所以甲、乙二人不相邻的排法总数应为： INCLUDEPICTURE "http://www.ycy.com.cn/2fxzd/word/48/48.htm6.gif" \* MERGEFORMATINET 种 . 插入法:对于某两个元素或者几个元素要求不相邻的问题,可以用插入法.即先排好没有限制条件的元素,然后将有限制条件的元素按要求插入排好元素的空档之中即可.若 个人站成一排，其中 个人不相邻，可用“插空”法解决，共有 种排法。 练习： 学校组织老师学生一起看电影，同一排电影票12张。8个学生，4个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的坐法？ 分析 此题涉及到的是不相邻问题,并且是对老师有特殊的要求,因此老师是特殊元素,在解决时就要特殊对待.所涉及问题是排列问题. 解 先排学生共有 种排法,然后把老师插入学生之间的空档，共有7个空档可插,选其中的4个空档,共有 种选法.根据乘法原理,共有的不同坐法为 种. 三、复杂问题——总体排除法或排异法 有些问题直接法考虑比较难比较复杂，或分类不清或多种时，而它的反面往往比较简捷，可考虑用“排除法”，先求出它的反面,再从整体中排除.解决几何问题必须注意几何图形本身对其构成元素的限制。 例3.(1996年全国高考题)正六边形的中心和顶点共7个点，以其中3个点为顶点的三角形共有　　个. 解：从7个点中取3个点的取法有 种，但其中正六边形的对角线所含的中心和顶点三点共线不能组成三角形，有3条，所以满足条件的三角形共有 －3＝32个. 练习： 我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种? 分析 此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况.而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程. 解 43人中任抽5人的方法有 种,正副班长,团支部书记都不在内的抽法有 种,所以正副班长,团支部书记至少有1人在内的抽法有 种. 四、特殊元素——优先考虑法　 　对于含有限定条件的排列组合应用题，可以考虑优先安排特殊位置，然后再考虑其他位置的安排。 例4． (1995年上海高考题) 1名老师和4名获奖学生排成一排照像留念，若老师不排在两端，则共有不同的排法　　　种． 解：先考虑特殊元素（老师）的排法，因老师不排在两端，故可在中间三个位置上任选一个位置，有 种，而其余学生的排法有 种，所以共有 ＝72种不同的排法. 例5．（2000年全国高考题）乒乓球队的10名队员中有3名主力队员，派5名队员参加比赛，3名主力队员要安排在第一、三、五位置，其余7名队员选2名安排在第二、四位置，那么不同的出场安排共有　　　种. 解：由于第一、三、五位置特殊，只能安排主力队员，有 种排法，而其余7名队员选出2名安排在第二、四位置，有 种排法，所以不同的出场安排共有 INCLUDEPICTURE "http://www.ycy.com.cn/2fxzd/word/48/48.htm19.gif" \* MERGEFORMATINET ＝252种. 五、多元问题——分类讨论法 对于元素多，选取情况多，可按要求进行分类讨论，最后总计。 例6．（2003年北京春招）某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数为（A ） A．42 B．30 C．20 D．12 解：增加的两个新节目，可分为相临与不相临两种情况：1.不相临：共有A62种；2.相临：共有A22A61种。故不同插法的种数为：A62 +A22A61=42 ，故选A。 例7．（2003年全国高考试题）如图，一个地区分为5个行政区域，现给地图着色，要求相邻地区不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有 种.（以数字作答） 解：区域１与其他四个区域相邻，而其他每个区域都与三个区域相邻，因此，可以涂三种或四种颜色． 用三种颜色着色有 =24种方法, 用四种颜色着色有 =48种方法,从而共有24+48=72种方法,应填72. 六、混合问题——先选后排法 对于排列组合的混合应用题，可采取先选取元素，后进行排列的策略． 例8．（2002年北京高考）12名同学分别到三个不同的路口进行车流量的调查，若每个路口4人，则不同的分配共有（ ） A． 种 B． 种 C． 种 D． 种 解：本试题属于均分组问题。 则12名同学均分成3组共有 种方法,分配到三个不同的路口的不同的分配方案共有： 种，故选A。 例9．（2003年北京高考试题）从黄瓜、白菜、油菜、扁豆4种蔬菜品种中选出3种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有（ ）     A．24种          B．18种          C．12种               D．6种     解:先选后排,分步实施. 由题意，不同的选法有: C32种,不同的排法有: A31·A22,故不同的种植方法共有A31·C32·A22=12，故应选C. 七．相同元素分配——档板分隔法 例10．把10本相同的书发给编号为1、2、3的三个学生阅览室，每个阅览室分得的书的本数不小于其编号数，试求不同分法的种数。请用尽可能多的方法求解，并思考这些方法是否适合更一般的情况？本题考查组合问题。 解：先让2、3号阅览室依次分得1本书、2本书；再对余下的7本书进行分配，保证每个阅览室至少得一本书，这相当于在7本相同书之间的6个“空档”内插入两个相同“I”（一般可视为“隔板”）共有 种插法，即有15种分法。 八．转化法: 对于某些较复杂的、或较抽象的排列组合问题，可以利用转化思想,将其化归为简单的、具体的问题来求解. 例11 高二年级8个班,组织一个12个人的年级学生分会,每班要求至少1人,名额分配方案有多少种? 分析 此题若直接去考虑的话,就会比较复杂.但如果我们将其转换为等价的其他问题,就会显得比较清楚,方法简单,结果容易理解. 解： 此题可以转化为:将12个相同的白球分成8份,有多少种不同的分法问题,因此须把这12个白球排成一排,在11个空档中放上7个相同的黑球,每个空档最多放一个,即可将白球分成8份,显然有 种不同的放法,所以名额分配方案有 种. 九．剩余法: 在组合问题中,有多少取法,就有多少种剩法,他们是一一对应的,因此,当求取法困难时,可转化为求剩法. 例12 袋中有5分硬币23个,1角硬币10个,如果从袋中取出2元钱,有多少种取法? 分析 此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱,难以理出头绪来.但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题. 解 把所有的硬币全部取出来,将得到0.05×23+0.10×10=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有 种取法. 十．对等法: 在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一.在求解中只要求出全体,就可以得到所求. 例13 期中安排考试科目9门,语文要在数学之前考,有多少种不同的安排顺序? 分析 对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了.并且也避免了问题的复杂性. 解 不加任何限制条件,整个排法有 种,“语文安排在数学之前考”,与“数学安排在语文之前考”的排法是相等的, 所以语文安排在数学之前考的排法共有 种. 十．平均分组问题: 例14．6本不同的书，按下列要求各有多少种不同的选法： （1）分给甲、乙、丙三人，每人2本； （2）分为三份，每份2本； （3）分为三份，一份1本，一份2本，一份3本； （4）分给甲、乙、丙三人，一人1本，一人2本，一人3本； （5）分给甲、乙、丙三人，每人至少1本。 解：（1）根据分步计数原理得到： 种； （2）分给甲、乙、丙三人，每人两本有 种方法，这个过程可以分两步完成：第一步分为三份，每份两本，设有x种方法；第二步再将这三份分给甲、乙、丙三名同学有 种方法．根据分步计数原理可得： ，所以 ． 因此，分为三份，每份两本一共有15种方法。 （3）这是“不均匀分组”问题，一共有 种方法． （4）在（3）的基础上再进行全排列，所以一共有 种方法． （5）可以分为三类情况：①“2、2、2型”即（1）中的分配情况，有 种方法； ②“1、2、3型”即（4）中的分配情况，有 种方法；③“1、1、4型”，有 种方法， 所以，一共有90+360+90＝540种方法． 总之，排列、组合应用题的解题思路可为：排组分清，加乘明确；有序排列，无序组合；分类为加，分步为乘。 具体说，解排列组合的应用题，通常有以下途径： （1）以元素为主体，即先满足特殊元素的要求，再考虑其他元素。 （2）以位置为主体，即先满足特殊位置的要求，再考虑其他位置。 （3）先不考虑附加条件，计算出排列或组合数，再减去不合要求的排列组合数。 第 1 页 共 9 页 WESTWOOD行政職業能力測验版WESTWOOD _1078904131.unknown _1078905065.unknown _1173758436.unknown _1078905079.unknown _1078904446.unknown _1078904856.unknown _1078904008.unknown _1078904122.unknown _1078903993.unknown _1078903669.unknown