排列组合问题的常见解题策略

排列组合问题的常见解题策略张秀亮（数学科学学院,2007（2）班,07211249号）［摘要］排列组合是高中数学一大难点，也是高考考查的重点内容，很多人解决排列组合问题，都感觉无从着手.排列组合包括排列和组合两部分，其中题型，散，杂.排列组合内容独特，思维新颖，方法灵活，逻辑性强，规律性强，易于混淆，容易出错.所以针对这种现状，对排列组合进行系统分类讨论分析，总结出其中的规律和方法，有助于提升排列组合问题的能力，解决问题时也比较得心应手.［关键词］排列组合解决规律和方法一、排列问题所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序.排列的定义:从n个不同元素中，任取m（m<n）个元素（这里的被取元素各有不同）按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列.下面是排列的一些常用解题方法：（一）分类与分步法分类计数原理：做一件事情，完成它可以有n类办法，在第一类办法中有m种不同的1方法，在第二类办法中有m2种不同的方法，…,在第n类办法中有m种不同的方法.那么完成这件事共有N=mi+m2+•••+m中不同的方法.分步计数原理：做一件事情，完成它需要分成n个步骤，第一步有m种不同的方法，1第二步有m2种不同的方法，…，第n步有m种不同的方法，那么完成这件事有N=m-m-...-m种不同的方法.例1某信号兵用红，黄，蓝3面旗从上到下挂在竖直的旗杆上表示信号，每次可以任意挂一面，二面或三面，并且不同的排序表示不同的信号，一共可以表示多少种不同的信号？解信号可以分3类：第一类用一面旗表示的信号有A1种；第二类用两面旗表示的信号有A2种；3第二类用三面旗表示的信号有A3种；3由分类计数原理，所求信号种树有A3+A2+A;=3+3X2+3x2x1=15种；故一共可以表示15种不同的信号.例2用0到9这10个数字，可以组成多少个没有重复数字的三位数？解解决排列应用题，常用的思考方式是直接法和间接法.直接法:通过对问题进行恰当的分类和分步，直接计算符合条件的排列数，如解法1,2；间接法:对于有限制条件的排列应用题，可以不考虑限制条件，把所有情况的种数求出来，然后再减去不符合限制条件的情况种数，如解法3；对于有限制条件的排列应用题，要恰当的确定分类与分步的标准，防止重复与遗漏.法1.用分步计数原理：所求的三位数的个数是：A;・A：=9x9x8=648.法2.符合条件的三位数可以分成三类：没一位数字不是0的三位数有A3个，个位数是90的三位数有A;个，由分类计数原理，符合条件的三位数的个数是：A3+A;+A;=648.法3.从0到9这10个数字中任取3个数字的排列数为A,，其中以0为排头的排列数为A;，因此符合条件的三位数的个数是A^-A;=648.（二）相邻问题捆绑法有些排列组合问题可以将相邻的元素捆绑在一起，作为一个整体，然后再进行排列，这样可以将复杂的问题简单化.例36名同学排成一排，其中甲、乙两人必须站在一起的不同排法有多少种？解因甲、乙两人要排在一起，故将甲、乙两人捆在一起视作一人，与其余四人进行全排列有种排法，但甲、乙两人之间有种排法，由乘法原理可知，共有A5.A2种排法.52说明：从上述解法可以看出，所谓“捆绑法”，就是在解决对于某几个元素要求相邻问题时，可整体考虑将相邻元素视作一个“大”元素.例4由数字1、2、3、4、5、6、7组成无重复数字的七位数.（1）求三个偶数必相邻的七位数的个数；（2）求三个偶数互不相邻的七位数的个数.（1）解（一）因为三个偶数2、4、6必须相邻，所以要得到一个符合条件的七位数可以分为如下三步：第一步将1、3、5、7四个数字排好有A4种不同的排法；第二步将2、44、6三个数字捆绑在一起有A3种不同的捆绑方法；第三步将第二步捆绑的这个整体插入3到第一步所排的四个不同数字的五个间隙（包括两端的两个位置）中的其中一个位置上，有Ai种不同的插入方法.根据乘法原理共有A4.A3.A1=720种同的排法.所以共有720个符合条件的七位数.解（二）先把2、4、6捆绑在一起看做一个数与1、3、5、7进行排列共有A5种排法.5第二步将2、4、6三个数字捆绑在一起有A3种不同的捆绑方法.根据乘法原理得到3A3.A;二720种不同的排法.所以共有720个符合条件的七位数.（2）解因为三个偶数2、4、6互不相邻，所以要得到符合条件的七位数可以分为如下两步：第一步将1、3、5、7四个数字排好，有A4种不同的排法；第二步将2、4、6分4别插入到第一步排的四个数字的五个间隙（包括两端的两个位置）中的三个位置上，有A35种插入方法.根据乘法原理共有A4.A3=1440种不同的排法.所以共有1440个符合条件的45七位数.（三）相离问题插空法相离问题插空法主要针对元素不能相邻问题，将不能相邻的元素隔开，主要做法是将其它元素想排好，再将不能靠一块的插进已经排好元素的间隙中.例5要拍一张有6个歌唱节目和4个舞蹈节目的演出节目单，任何两个舞蹈节目不得相邻，问有多少不同的排法？解先将6个歌唱节目排好，其不同的排法为A6种，这6个歌唱节目的空隙及两端共6七个位置中再排4个舞蹈节目有A7种排法，由乘法原理可知，任何两个舞蹈节目不得相邻7的排法为A;•A6种.说明：从解题过程可以看出，不相邻问题是指要求某些元素不能相邻，由其他元素将它隔开，此类问题可以先将其它元素排好，再将所指定的不相邻的元素插入到它们的间隙及两端位置，故称插空法.二、组合问题组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序.组合的定义：从n个不同元素中，任取m（m<n）个元素（这里被取元素个不相同）并成一组，叫做从n个不同元素中取出m个元素的一个组合.下面的组合的一些常用解题方法：（一）标号排位问题分布法把元素排在指定号码的位置上成为标号排位问题，求解这类问题可先把某个元素按照规定排入，第二步再排另一个元素，如此继续下去，依次即可完成.例6同室4人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送来的贺年卡，则四张贺年卡不同的分配方式有多少种？解此题可以看成是将数字1、2、3、4添入标号为1、2、3、4的四个方格里，每格填一个数，且每个方格的标号与所填数不同的填法问题.所以先将1填入2至4号的三个方格中有种C3填法，第二步把被填入方格的对应数字，填入其它3个方格，又有C：种填法，第三步将余下的两个数字填入余下的两格中只有一种填法，故共有3x3x1=9种填法.（二）多元问题分类法多元问题分类法主要将问题先分成几种情况，先求出每种情况，然后将每种情况归结起来，算出总体情况.例74名男生和6名女生组成至少有1名男生参加的三人社会实践活动小组，问组成方法共有多少种？解小组构成有三种情况：3男，2男1女，1男2女，分别有C:，C•C6,C;弋，所以一共有C3+C2•C6+C4C=100种方法.（三）组合中的抽屉原理抽屉原理有时也被称为鸽巢原理，它是德国数学家狄利克雷首先明确提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原理，它是组合数学中一个重要的原理.抽屉原理的定义：假如有n+1或多于n+1个元素放到n个元素中去，其中必定至少有一个集合里有两个元素.例8幼儿园买来了不少白兔，熊猫，长颈鹿塑料玩具，每个小朋友任意选择两件，那么不管怎样挑选，在任意七个小朋友中总有两个彼此选的玩具都相同，试试说明道理.解：从三种玩具中挑选两件，搭配方式整合后和只能是下面六种：（兔，兔），（兔，熊猫），（兔，长颈鹿），（熊猫，熊猫），（熊猫，长颈鹿），（长颈鹿，长颈鹿）.把每种方式看做一个抽屉，把7个小朋友看做物体，那么根据原理1，至少有两个物体要放进同一个抽屉里，也就是说，至少两人挑选玩具采用同一种搭配方式，选的玩具相同.三、排列组合特殊类问题有些题目属于排列组合，但这些题目特殊，而且考试中易于犯错，我们把它们作为特例分下来讨论，有助于掌握.（一）排列组合“投球入盒”问题探究1、不同小球的投放问题模型1：n个不同的小球全部投入到山个不同的盒中，共有mn种不同的投放方法.分析：完成事件的最终结果是：n个球全部进入盒子中.可分n个步骤完成，第1个球有m种不同的投放方法，第2个球，第3个球第n个球也均有m种不同的投放方法，由分步计数原理：共有mn种不同投放方法.模型使用的关键在于分清“球是什么”，“盒是什么”.例9（1）5名学生从3项体育项目中选择参赛，若每名学生都要参加，且每一名学生只能参加一项，则有多少种不同的参赛方法？（2）若5名学生争夺3项比赛冠军（每一名学生参赛项目不限），则冠军获得者有几种不同情况（没有并列冠军）？解（1）中完成事件的结果是：最终每名学生都要参赛，而每一项可能有多人参加.故把学生视为“球”，项目则视为“盒”.5个不同的“球”最后都要投入到3个“盒”中.每一个“球”都有3种不同投法.故参赛法共有35=243种.（2）中完成事件最后的结果是：冠军都被学生夺得.每一项比赛冠军由一人获得，而一人可得多项冠军，故把冠军视为“球”，学生视为“盒”，“球”最后要部入“盒“（即冠军最后全部由学生夺取），每个球均有5种投法（对应每个冠皆有可能被5名生中任一人获得）故三项冠军依次被取得的情况共有53种.2、相同小球的投放问题模型2：n个相同的小球投入到m个不同的盒子中，且每盒至少有一个小球，共有Cn-1m-1种不同投放方法.分析：这类问题用“隔板法”解决比较简捷n个相同的小球之间共有n-1个空档（两外）现取（m-1）块相同的“档板”分别插入到（n-1）个空档中的m-1个空档，每一次插入就将n个球分成了m个部分（每一部分至少有一个球），即对应一种投球入盒方法，故共Cn-1种不同投法.m-1例10已知方程X+y+z+W=100，求这个方程的正整数解的组数.解此题貌似与排列或组合无关，实质可转化为组合问题解决.100为100个1的和每一组解相当于把100个1分成4组，每一种分组对应方程的一组正整数解，若将100个“1”看成100个“相同的小球”，问题转化为：“100个相同的小球投入到四个不同的盒中（X、y、z、w视为‘盒’）每盒至少投入1个球，共有多少种不同投放方法？”即在100个小球之间的99个空档处选取3个，分别插入3块“挡板”，每次插入，被分成4组的球的个数即为方程相应的一组解，故方程正整数解数共有C3=156849组.99模型3：n个相同的小球，全部投入到m个不同的盒子中（无任何要求）；共有Cm-in+m-1种不同投放方法.分析：同样运用“隔板思想”，只是隔板允许相邻，即允许隔板间没有小球，相当于从n+m-1（n个小球和m-1块隔板）个位置中任取m-1个位置放置m-1个隔板的组合数.例11从5个班中选10人组成校篮球队（无任何要求）有多少种不同选法？解“10个人”视为“10个相同的小球”班级视为“盒子”10个小球投入到5个盒子中，是10个小球和4块挡板两类元素不分顺序的排列问题.即4块“挡板”与10个球一样也要参与排成一列占位置.故有C4=1001种选法.14（二）插板法解“插板法”顾名思义就是将元素做为插板插进空档处.例12现有10个完全相同的球全部分给7个班级，每班至少1个球，问共有多少种不的分法？解题目中球的分法共三类.（1）有3个班每个班分到2个球，其余4个班每班分到1个球.其分法种数N\=C3.（2）有1个班分到3个球；1个班分到2个球;其余5个班每班分到1个球.其分法种数N2=C;-C1.（3）有1个班分到4个球;其余的6个班每班分到1个球.其分法种数N=C1.37所以，10个球的分法种数为N=N+N+N=C3+C1・C1+C1=84.由上面解题过程可以明显感到对这类问题进行分类计算，比较繁琐，若是上题中球的数目较多处理起来将更加困难，因此我们需要寻求一种新的模式解决问题，我们创设这样一种虚拟的情境插板.将10个相同的球排成一行，10个球之间出现了9个空档，现在我们用“档板”把10个球隔成有序的7份,每个班级依次按班级序号分到对应位置的几个球（可能是1个、2个、3个、4个）.这样每个班级分到球的个数不在于它所排的位置，借助于这样的虚拟“档板”分配物品的方法称之为插板法.由上述情境分析知，分球的方法实际上为档板的插法：即是在9个空之中插入6个“档板”，其方法种数为N=C?=84.思考：若上题中的球为15个全分给7个班级，每班至少一个球的分法种数是几？（C4）16由上述问题的解决看到，这种插板法解决起来非常简单，但同时也提醒大家，这类问题模型要求满足条件相当严格，必须具备以下3个条件：所要分的物品规格必须完全相同.所要分的物品必须分完，决不允许有剩余.参与分物品的每个成员至少分到1个,决不允许出现分不到物品的成员.总结：排列组合问题说难也不难，说简单也容易出错，关键看以何种思路，何种方法解决，针对一类问题进行细致，仔细的分析，研究，从而掌握这类的一般方法，对于解决这类问题有很大帮助.本文主要通过对排列组合的一个分类分析，讨论，列出了一些常见的排列组合问题的题型，从中归纳一般规律.［参考文献］［1］席明闰.排列组合的问题及解答策略.内江科技.2010第二期［2］陈绍敏.排列组合中的“投球入盒”.问题研究.2009.7［3］张亚军.高中数学教与学.第8期［4］王金锁.数学教学.考试周刊［5］李智敏.例谈排列组合的若干解题策略.实战实例［6］张金华.排列组合问题常见解题策略［7］张军.教师招聘考试专用教材.2011TheCommonPermutationAndCombinationProblemSolvingStrategyZhangXiuLiang[Abstract]Thepermutationandcombinationishighschoolmaths,butalsoadifficultthemaincontentof