NOIP中排列组合问题的十种解题策略

一、公式法例1：将N个红球和M个黄球排成一行。例如，当N=2，M=3时可得到10种排法。问题：当N=4,M=3时有（）种不同排法？（NOIP2002）解：此题属于不全相异元素的全排列，可以直接代入以下公式（公式中n1+n2+n3+……+nm=N）!*!*!*!*!321mnnnnN所以35!4!*3!7例2：公园门票每张5角，如果有10个人排队购票，每人一张，并且其中一半人恰有5角钱，另一半恰有1元钱，而票房无零钱可找，那么有多少种方法将这10个人排成一列，顺次购票，使得不至于因票房无零钱可找而耽误时间？解：此题属于D[0]=D[1]排列，可以直接代入以下公式122nnnnCC所以42210252410510CC二、转换法：深入思考，抓住问题的本质，将原问题转化成排列组合经典问题来解决。例3：某城市的街道是一个很规整的矩形网络（见下图），有7条南北向纵街，5条东西向横街。现在从西南角的A走到东北角的B，最短的走法共有（）种（NOIP2007）BA解：无论怎样走都必须经过6横4纵，因此可把问题转化为4个相同的白球和6个相同的黑球的排列问题。所以210410C三、分类法：按题目条件，把符合条件的排列、组合问题分成互不重复的若干类，分别计算，最后计算总数。例4：小陈现有2个任务A，B要完成，每个任务分别有若干步骤，A=a1→a2→a3，B=b1→b2→b3→b4→b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2→b2→a3→b3……是合法的，而……a2→b3→a3→b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有（）种。（NOIP2009）解：可知B任务中的b1一定做，而且肯定是第一个做的。除了b1外，第一类：只完成A任务，只有1种；第二类：完成A任务和b2，有414C种；第三类：完成A任务和b2，b3，有1025C种。第四类：完成A任务和b2、b3、b4，有2036C种。第五类：完成A任务和b2，b3，b4，b5，有3547C种。由加法原理可得1+4=10+20+35=70。例5：平面上有三条平行直线，每条直线上分别有7、5、6个点，且不同直线上三个点都不在同一条直线。问用这些点为顶点，能组成（）个不同的三角形？（NOIP2001）解：第一类，7个点中任取2点，5个点中任取1点，有1527*PP种；第二类，7个点中任取2点，6个点中任取1点，有1627*PP种；第三类，5个点中任取2点，7个点中任取1点，有1725*PP种；第四类，5个点中任取2点，6个点中任取1点，有1625*PP种；第五类，6个点中任取2点，7个点中任取1点，有1726*PP种；第六类，6个点中任取2点，5个点中任取1点，有1526*PP种；第七类，7个点中任取1点，5个点中任取1点，6个点任取1点，有151617**PPP种。由加法原理可得，能组成1527*PP+1627*PP+1725*PP+1625*PP+1726*PP+1526*PP+151617**PPP=751个不同的三角形。四、特殊元素（位置）优先法：把有限制条件的元素（位置）称为特殊元素（位置），对于这类问题一般采取特殊元素（位置）优先安排的方法。例6：6个人站成一横排，其中甲不站左端也不站右端，共有多少种不同站法？解法1：（元素分析法）因为甲不能站左右两端，故第一步先让甲排在左右两端之间的任一位置上，有14P种站法；第二步再让其余的5人站在其他5个位置上，有55P种站法，由乘法原理可得不同站法共有14P*55P=480。解法2：（位置分析法）因为左右两端不站甲，故第一步先让甲以外的5个人任选两人站在左右两端，有25P种；第二步再让剩余的4个人（含甲）站在中间4个位置，有44P种，由乘法原理可得不同站法共有4425*PP=480。五、排除法：对于某些比较复杂的或抽象的问题，可以采用转化思想，从问题的反面去考虑，先求出无限制条件的方法种数，然后去掉不符合条件的方法种数。在应用此法时要注意做到不重不漏。例7:8位同学排成一行，要求某两位同学互不相邻，有多少种排法？解：8位同学排成一行的总数是88P；把排在一起的两个同学看成一个人的排列总数是77P，因此排在一起的两个同学的位置可以相互换，所以两位同学排在一起的排列数是2*77P。所以符合题意的排法为88P-2*77P=30240。六、捆绑法：对于要求某几个元素必须排在一起的问题，宜用捆绑法。即将这几个元素看作一个整体，视为一个元素，与其他元素进行排列，然后相邻元素内部再进行排列。例8：书架上有四本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这四本书摆在书架上，满足所有黑皮的书都排在一起的摆法有（）种。（NOIP2008）解：先将C和D“捆绑”在一起看成一个大元素，与A、B全排列有33P种排法，而C和D又有22P种排法，由乘法原理可得满足所有黑皮的书都排在一起的摆法有33P*22P=12种。例9：由数字1,2,3,4,5,6,7组成无重复数字的七位数，求三个偶数必须相邻的七位数的个数。解：此解可分三步完成：第一步，将1，3，5，7四个数字排好有44P种不同的排法；第二步，将2，4，6三个数字“捆绑”在一起有33P种不同的“捆绑”法。第三步，将第二步“捆绑”的这个整体插入到第一步所排的四个不同数字的五个间隙中的其中一个位置上，有15P种不同的插入方法。根据乘法原理此题共有44P*33P*15P=720种不同排法。七、插空法：元素相离（即不相邻）问题，可以先将其他元素排好，然后再将不相邻的元素插入已排好的元素位置之间和两端的空中。例10：8位同学排成一行，其中有4位女同学，要求女同学不相邻，有多少种排法？解：四位男同学排成一行的总数是44P=24，在他们首尾两个位置和他们两两之间的位置（共5个）分别插入一个女同学的排列数是45P=120，所以符合题意的个数是24×120=2880。例11：马路上有编号为1，2,3，……，10十个路灯，为节约用电又看清路面，可以把其中的三盏灯关掉，但不能同时关掉相邻的两只，在两端的灯也不能关掉的情况下，求满足条件的关灯方法共有多少种？解：关掉的灯不能相邻，也不能在两端。又因为灯与灯之间没有区别，因而问题为在7盏亮着的灯形成的不包含两端的6个空中选出3个空放置熄灭的灯。所以共有36C=20种方法。八、隔板法：名额分配或相同物品的分配问题，适宜采用隔板法。例12：某校准备组建一个由12人组成的篮球队，这12个人由8个班的学生组成，每班至少一人，名额分配方案共（）种。解：此例的实质是12个名额分配给8个班，每班至少一个名额，可在12个名额中的11个空当中插入7块隔板，一种插法对应一种名额的分配方式，故有711C=330种。九、递推法：例13：在书架上放有编号为1,2，……，n的n本书。现在n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n=3时，原来位置为：123。放回去时只能为：312或231这两种。问题：求当n=5时满足以上条件的方法共有多少种？（NOIP2002）解：第一步：第一本书不放在原来的第一个位置，有n-1种放法。第二步：假设第一本书放在第二个位置，则第二本书的放法又可以分为两类：第一类，第二本恰好放在第一个位置，则余下的n-2本书有an-2种放法；第二类，第二本书不放在第一个位置，第三本书不放在第三个位置，第四本书不放在第四个位置……第n本书不放在第n个位置，所以有an-1种放法。由加法原理和乘法原理，可以得到以下的递推公式：An=(n-1)(An-1+An-2)