排列与组合.doc

3. 2 排列与组合的概念与计算公式 1排列及计算公式 从n个不同元素中，任取m(mn)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 p(n,m)表示. p(n,m)=n(n-1)(n-2)(n-m+1)= n!/(n-m)!(规定0!=1). 2组合及计算公式 从n个不同元素中，任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(mn)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号 c(n,m) 表示. c(n,m)=p(n,m)/m!=n!/(n-m)!*m!)；c(n,m)=c(n,n-m); 其他排列与组合公式 从n个元素中取出r个元素的循环排列数p(n,r)/r=n!/r(n-r)!. n个元素被分成k类，每类的个数分别是n1,n2,.nk这n个元素的全排列数为 n!/(n1!*n2!*.*nk!). k类元素,每类的个数无限,从中取出m个元素的组合数为c(m+k-1,m).（三） 重点解讲 例1有四位男学生，三位女学生排队拍照，根据下列要求，各有多少种不同的排列结果。 （1）七个人排成一列，三个女学生中任何两个均不能连排在一起； （2）七个人排成一列，四个男学生必须连排在一起； （3）七个人排成一列，甲、乙、丙三人顺序一定； （4）七个人排成一列，但男学生必须连排在一起，女学生也必须排在一起，且男甲与女乙不能相邻； （5）七个人排成一列，其中甲、乙两人之间必须相隔2人 解：（1）遇到两个特殊元素不相邻的问题可用插空法（间隔法）。先排其余元素，后在空档中插入特殊元素，先排四个男学生，插入三位女学生，因此共有（种） （2）捆绑法（归一法），可将四个男学生看成一个整体，其与其余三个学生一起照相，因此共有（种） （3）先不考虑甲、乙、丙的顺序，任意排列共有 种，因为在上述排列中，每六种有且仅有一种恰好是符合甲、乙、丙按一定顺序排列，因此符合要求共有 （种） 另一种解法：七个位置中，先将除甲、乙、丙外的四人排入有 种，然后将甲、乙、丙排规定顺序排入三个空位中，因此共有 （种）。 （5）先从除甲、乙外的其余五人中选2人排在甲、乙之间，注意甲、乙可交换位置。有 ；然后将这4个人（包括甲、乙）作为一个整体与剩余3人作全排列，共有 （种） 例2要将n+1个不同的小球放入n个不同的盒子，有多少种不同的放法不出现空盒子？ 解法一：由于不出现空盒，所以应当有一个盒子放两个球，其余各盒都应放入一个球，从这n个盒子中选出一个放两个球，有 种不同的选法；从这n+1个球中选出两个球放入此盒，有种选法；其余(n-1)个球分别放入其余(n-1)个盒子，有 种不同放法，因此，由乘法原理及有 （种） 上述解法是从盒子的角度来考虑问题的，也可以从球的角度来考虑问题。 解法二：有两个球放入同一个盒子，从n+1个球中选出两个球，有 种不同选法；将这两个球视为一个整体，再与其余n-1个球一道分别放入这n个盒子，共有 种不同的放法，所以一共有 （种） 解法三：选将n+1个球排成一排，共有 种排法；再在它们之间插入隔板，以表示将它们放入不同的盒子。由于不出现空盒，因此将n-1块隔板分别插在它们两两之间的n个隔中的n-1个间隔中，故有 种不同的插法，又因放入同一盒子的两个球无顺序之分，因此，一共有 （种）通过一题多解，一方面可以培养学生从多角度，多方位来考虑问题，培养学生思维的广阔性，从而达到提高能力的有效途径；另一方面也是检验解排列组合问题对错的一种有效方法。例3选择题： （1） 四面体的顶点和各棱中点共有10个点，在其中取4个不共面的点，不同取法有（ ） （A）152 （B）147 （C）144 （D）141 （2）3名医生和6名护士被分配到3所学校为学生体检，每校分配1名医生和2名护士，不同分配方法共有（ ） （A）90种 （B）180种 （C）270种（D）540种 （3）20个不加区别的小球放入编号为1号，2号，3号三个盒子中，要求每个盒子内的球数不小于盒子的编号数，则不同的放法总数是（ ） （A）760 （B）764 （C）120 （D）91 （4）某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为（ ） （A）720 （B）480 （C）224 （D）20 （5）从A、B、C、D、E五名学生中选出四名分别参加数学、物理、化学、英语竞赛，其中A不参加物理、化学竞赛，则不同的参赛方案种数为（ ） （A）24 （B）48 （C）120（D）72 解：（1）本题实际上进行两次分类，第一次分类是将四点组取法数分为共面与不共面两类，确定共面四点组数，用间接法可得不共面四点组数。第二次分类是为了确定四点共面的取法数，再次进行分类，这是本题关键也是难点所在，可分三类：第一类，在每个面内取，共有 种取法；第二类，每条棱和其对棱的中点，共有6个面；第三类，6个棱的中点中，与一组对棱平行的面，共有3个，于是可得 （）= 21069 = 141（种） 故选（D） （2）本题可分两步进行：第一步将3名医生分到三个学校有p3种分配方法；第二步将6名护士分到3个学校，可首先进行均匀分组得 ，然后分到三个学校，即得 因此得 （种），故选（D） （3）先取出3个球，然后将17个球排成一列，17个球中间有16个空档，从中任取两个空档作记号1（如图所示），001000001000将17个球分成三块；第一块给1号盒，第二块给2号盒，第三块给3号盒；然后将取出的1个球给2个盒，再将取出2个球给3号盒，确保每盒内球的个数不少于盒的编号数，从而使本题要求不同的放法总数转化为从16个空档中任取2个的组合数，即， 故选（C）。 （4）把有3枪在一起命中的情况看成一个整体，则它与另一命中的一枪不能再相邻，故可用插空法。 首先，对没有命中的4枪进行排序，因其地位平等，只有一种排法，然后插入命中的情况，有p5=20种，故选（D） 这里，我们关心的是命中的情况， 如果忽略了未命中的4枪地位平等，那么就会由 而误选B。 （5）解法一（直接法），有限制条件的排列，组合问题，用特殊元素分析法，以特殊元素A把问题分为两大类，第一类：不选A的，此时参赛方案有 种；第二类：选A的，此时先选元素（人），有 种方法，再排元素有 种方法，故此种情况下参赛方法有 种；由以上可知总的参赛方案由加法原理共有： + =24+48=72（种） 故选（D）。解法二（问接法） 带有否定限制条件的问题常用间接法。 五人中任选四人总的参赛方案在 （种）而不符合条件的：A参加物理或化学的参赛方案有 （种）；所以满足条件的参赛方案有120 - 48 =72（种），故选（D）。 例4 填空题： （1）已知集合A=a，b，c，d，B=-1，0，1，则从集合A到集合B的不同映射有_ 个。 （2） 拟发行体育奖券，号码从 （3） 000001到999999，购买时揭号对奖，若规定：从个位数起，第一、三、五位是不同的奇数，第二、四、六位均为偶数时为中奖号码，则中奖面约为 _（精确到0.01%）。 （3）一杂技团有8名会表演魔术或口技的演员，其中有6人会表演口技，有5人会表演魔术，今从这8名演员中选出2人，一人表演口技，一人表演魔术，则选法种数为_ 种。（4）在一块并排10垄的田地中选择2垄分别种植A，B两种作物，每种作物种植一垄，为有利于作物生产，要求A，B两种作物的间隔不小于6垄，则不同的选垄方法共有_ 种（用数字回答） 解：（1）映射个数问题，由映射的定义，可以把问题分为四步：第一步：给集合A中的元素a在集合B中找对应元素有种方法。 第二、三、四步：同理b、c、d在B中找对应元素都有 种方法。 由乘法原理,从A到B的不同映射共有 =81(个) 一般地，设集合A有m个元素，集合B有n个元素，则从A到B的不同映射共有nm个（2）元素能重复的问题常用乘法原理。 该问题等价于求作满足同样条件的六位数的个数，分为两大步： 第一步：排第一、三、五位数字（从低位数起）由题知是不重复的奇数，则从1，3，5，7，9这五个奇数中任选3个排列有 种方法。 第二步：又可分作3小步，先排第二位，从0，2，4，6，8这五个数代取一个有种方法；再排第四位，同理有 种方法；最后排第六位，由于是奖券问题，所以0可以作高位数字，所以同样也有 种方法。 由乘法原理有 =7500（种）所以满足条件的奖券有7500个，于是中奖面为 需要注意的是，在处理较复杂的排列、组合问题时，我们常常是把问题化归（等价模拟）为一个具体的易于理解和处理的问题，从而使问题易于解决，这是一种常用的重要思想方法。 （3）解法一：加法原理法（图） 由题易知3人只会口技，2 人只会魔术，3人二者均会 把问题分作四类：（先分类，后分步）第一类：从仅会口技和仅会魔术的人中各选1人有种选法： 第二类：从只会口技与二者都会的人中各选1人有 种选法。 第三类：从只会魔术与二者都会的人中各选1人有种选法； 第四类：从二者都会的3人中选2人有 种选法。 由加法原理知满足条件的选法共有 +9解法二：主、次元素分析法。 我们不妨把要选的会口技的这1人当作主元素，把会魔术的这1人当作次元素，由主次化原则可把问题分作两大类： 第一大类：要选的会表演口技的这1人来源于只会口技的3人之一有种方法，此时，次元素（即所要选的表演魔术的这1人）又有两种来源：一种是来自二者都会的有种选法，另一种是来自只会魔术的2人之一有 种选法。第一大类中有 种选法。 第二大类：主元素这1人来源于二者都会3人之一有种选法，而此时相应的次元素这1人仍有两种来源：一种来源于二者都会的剩下的2人之一有 种选法；另一种来源于只会魔术的2人之一有 种选法。 第二大类中共有（种） 于是满足条件的