排列组合材料

提高班培训之二：《排列组合问题的求解方法与策略》（答案） 提高班培训材料之二：《排列组合问题的求解方法与策略》（答案） 一. 排列组合问题的求解方法 1. 含有可重元素的排列问题. 对含有相同元素求排列个数的方法是：设重集S有k个不同元素a1，a2,…...an其中限重复数为n1、n2……nk，且n = n1+n2+……nk , 则S的排列个数等于 . 例1：已知数字3、2、2，求其排列个数 又例如：数字5、5、5、求其排列个数？其排列个数 . 2.直接法. （一.合理分类与准确分步法） 解含有约束条件的排列组合问题，应按元素性质进行分类，按事情发生的连续过程分步，保证每步独立，达到分类明确，分步层次清楚，不重不漏。 例2 、五个人排成一排，其中甲不在排头，乙不在排尾，不同的排法有 （ ） A．120种 B．96种 C．78种 D．72种 分析：由题意可先安排甲，并按其分类讨论：1）若甲在末尾，剩下四人可自由排，有 种排法；2）若甲在第二，三，四位上，则有 种排法，由分类计数原理，排法共有 种，选C。解排列与组合并存的问题时，一般采用先选（组合）后排（排列）的方法解答。 例 3、 4个不同小球放入编号为1，2，3，4的四个盒中，恰有一空盒的方法有多少种？ 分析： 因恰有一空盒，故必有一盒子放两球。1）选：从四个球中选2个有 种，从4个盒中选3个盒有 种；2）排：把选出的2个球看作一个元素与其余2球共3个元素，对选出的3盒作全排列有 种，故所求放法有 种。 例4、如图：在一个正六边形的六个区域栽种观赏植物，要求同一块中种同一种植物，相邻的两块种不同的植物，现有4种不同植物可供选择，则有 种栽种？（2001年全国高中数学联赛） 　　解：由题意，要求同一块中种同一种植物，相邻的两块种不同的植物。则可先考虑A、C、E．因此作如下分类： 　　（1）若A、C、E种同一种植物，此时共有4 3 3 3=108种方法。 　　（2）若A、C、E种二种植物，此时共有3 4 3 3 2 2=432种方法。 　　（3）若A、C、E种三种植物，此时共有 2 2 2=192种方法。 　　所以共计有108+432+192=732种方法。 　例5、从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一种颜色，每两个具有公共棱的面染成不同的颜色。则不同的染色方案共有 种。 　　（注：如果我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体的上、下、左、右、前、后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案相同。）（1996年全国高中数学联赛） 　　解：本题情况较为复杂，我们对用了多少种颜色进行分类讨论。 　　（1）若只用三种颜色，从六种不同颜色中选用3种颜色有 种选法。由于每两个具有公共棱的面染成不同的颜色，则正方体的相对面均为同色，由正方体的对称性知这样的染色方案只有一种。因此共有 =20种不同的染色方案。 　　（2）若只用四种颜色，从六种不同颜色中选用4种颜色有 种选法。则仅有一个相对面不同色，共有 种不同的涂法。因此共有 =90种不同的染色方案。 　　（3）若只用五种颜色，从六种不同颜色中选用5种颜色有 种选法。则仅有一个相对面同色，不妨定为上、下底面，其有 种涂法。再涂侧面，有3种涂法。因此共有 3=90种不同的染色方案。 　　（4）用六种不同颜色来涂色。则六个面的颜色均不相同，假想颜色已经涂好，我们可以通过适当的翻转，使上底面均为同一种颜色（例如红色），再考虑下底面，则一定有5种不同的颜色。对下底面是同一种颜色的（例如蓝色），再用余下的四种颜色来涂侧面，有 种涂法。因此共有5 3！=30种不同的染色方案。一共有20+90+90+30=230种不同的染色方案 （二、元素分析与位置分析法）对于有附加条件的排列组合问题，一般采用：先考虑满足特殊的元素和位置，再考虑其它元素和位置。 例6、 用0，2，3，4，5，五个数字，组成没有重复数字的三位数，其中偶数共有（ ）。 A． 24个 B。30个 C。40个 D。60个 [分析]由于该三位数为偶数，故末尾数字必为偶数，又因为0不能排首位，故0就是其中的“特殊”元素，应该优先安排，按0排在末尾和0不排在末尾分两类：1）0排末尾时，有 个，2）0不排在末尾时，则有 个，由分数计数原理，共有偶数 =30个，选B。 例7、 马路上有8只路灯，为节约用电又不影响正常的照明，可把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，也不能关掉两端的灯，那么满足条件的关灯方法共有多少种？ 分析：表面上看关掉第1只灯的方法有6种，关第二只，第三只时需分类讨论，十分复杂。若从反面入手考虑，每一种关灯的方法对应着一种满足题设条件的亮灯与关灯的排列，于是问题转化为“在5只亮灯的4个空中插入3只暗灯”的问题。故关灯方法种数为 。 （三.列举法） 　例8、从0、1、2、3、4、5、6、7、8、9这10个数中取出3个数，使其和为不小于10的偶数，不同的取法有 。（1998年全国高中数学联赛） 　　解：从10个数中取出3个数，使其和为偶数，则这三个数都为偶数或一个偶数二个奇数。当三个数都为偶数时，有 种取法；当有一个偶数二个奇数时，有 种取法。要使其和为不小于10的偶数。我们把和为小于10的偶数列举出来，有如下9种不同取法：（0，1，3），（0，1，5），（0，1，7），（0，3，5），（0，2，4），（0，2，6），（1，2，3），（1，2，5），（1，3，4）。因此，符合题设要求的取法有 + －9=51种。 　例9、设ABCDEF为正六边形，一只青蛙开始在顶点A处，它每次可随意地跳到相邻两顶点之一。若在5次之内跳到D点，则停止跳动；若5次之内不能到达D点，则跳完5次也停止跳动。那么这只青蛙从开始到停止，可能出现的不同跳法共 种。（1997年全国高中数学联赛） 　　解：如图： 　　 　　青蛙不能经过跳1次、2次或4次到达D点。故青蛙的跳法只有下列两种： 　　（1）青蛙跳3次到达D点，有ABCD，AFED两种跳法。 　　（2）青蛙一共跳5次后停止，那么，前3次的跳法一定不到达D，只能到达B或F，则共有AFEF，AFAF，ABAF，ABCB，ABAB，AFAB这6种跳法。随后的两次跳法各有四种，比如由F出发的有：FEF，FED，FAF，FAB共四种。因此这5次跳法共有6 4=24种不同跳法。 一共有2+24=26种不同跳法。 例10．某电脑用户计划使用不超过500元的资金购买单价分别60元、70元的单片软件和盒装磁盘，根据需要，软件至少买3片，磁盘至少买2盒，则不同的选购方法有（ ） A．5种 B．6种 C．7种 D．8种 解析：根据所给选项数字较小，不难用枚举法解决． 单片买3张，磁盘买2盒，花钱320元；单片买3张，磁盘买3盒，花钱390元；单片买3张，磁盘买4盒，花钱460元；单片买4张，磁盘买2盒，花钱380元；单片买4张，磁盘买3盒，花钱450元；单片买5张，磁盘买2盒，花钱440元；单片买6张，磁盘买2盒，花钱500元．故选购方式有7种，选A． 例11．从1到100的一百个自然数中，每次取出两个数，使其和大于100，这样的取法共有多少种？ 解： 从1到100的一百个自然数中，每次取出两个数，其中必有一个是较小的．我们先按较小的一数枚举，而当较小的数取定以后，使和超过100的另一个相应较大的数不难一一例举，所有情况如下表： 较小 数 相应可取的较大数 取法种数 1 100 1 2 99，100 2 3 98，99，100 3 … … … 49 52，…，100 49 50 51，52，…，100 50 51 52，…，100 49 … … … 99 100 1 所以共有：1+2+3+…+49+50+49+…+1=2500种不同的取法．利用枚举法解题，直观性强，是处理排列组合问题的好方法． 3.排除法. （总体淘汰法）（正难则反） 例12．有五张卡片，他们的正反面分别写有0与1，2与3，4与5，6与7，8与9，将其中任意三张排放在一起组成三位数，共可组成多少个不同的三位数？ 解析：（1）0不能作百位，但可以作十位或个位．（2）0与1在同张卡片上，因此直接分类既要考虑0又要考虑1分类较复杂．于是先不考虑任何情况算出总数，然后减去0在左边第一位的号码即为所求．由于任取三张可以组成不同的三个数的号码有： ，其中0在左边第一位的号码有： ， 故所求的不同三位数共有： - =432 个． 例13．从1，2，3，…，1995这1995个自然数中，取出9个互不相邻的自然数，有多少种方法？ 解析：由于符合题意的条件错综复杂，正面进攻思维受阻，此时采用反面去考虑问题． 问题相当于“9个女生不相邻地插入站成一列横队的1986个男生之间（包括首尾外侧），有多少种方法？” 任意相邻2个男生之间最多站1个女生，队伍中的男学生首尾两侧最多也可各站1个女学生，于是，这就是1987个位置中任选9个位置的组合问题，共有 种方法． 对于含有否定字眼的问题，可以从总体中把不符合要求的除去，此时需注意不能多减，也不能少减。 例如在例3中，也可用此法解答：五个数字组成三位数的全排列有 个，排好后发现0不能排首位，而且数字3，5也不能排末位，这两种排法要除去，故有 个偶数。 4.捆绑法：在特定要求的条件下，将几个相关元素当作一个元素来考虑，待整体排好之后再考虑它们“局部”的排列.它主要用于解决“元素相邻问题”，例如，一般地，n个不同元素排成一列，要求其中某 个元素必相邻的排列有 个.其中 是一个“整体排列”，而 则是“局部排列”. 例14.①有n个不同座位，A、B两个不能相邻，则有排列法种数为 . ②有n件不同商品，若其中A、B排在一起有 . ③有n件不同商品，若其中有二件要排在一起有 . 注：①③区别在于①是确定的座位，有 种；而③的商品地位相同，是从n件不同商品任取的2个，有不确定性. 5.插空法：先把一般元素排列好，然后把待定元素插排在它们之间或两端的空档中，此法主要解决“元素不相邻问题”. 例15.：n个元素全排列，其中m个元素互不相邻，不同的排法种数为多少？ （插空法），当n – m+1≥m, 即m≤ 时有意义. 6.占位法：从元素的特殊性上讲，对问题中的特殊元素应优先排列，然后再排其他一般元素；从位置的特殊性上讲，对问题中的特殊位置应优先考虑，然后再排其他剩余位置.即采用“先特殊后一般”的解题原则. 7.调序法：当某些元素次序一定时，可用此法.解题方法是：先将n个元素进行全排列有 种， 个元素的全排列有 种，由于要求m个元素次序一定，因此只能取其中的某一种排法，可以利用除法起到去调序的作用，即若n个元素排成一列，其中m个元素次序一定，共有 种排列方法. 例16：n个元素全排列，其中m个元素顺序不变，共有多少种不同的排法？ 解法一：（逐步插空法）（m+1）（m+2）…n = n！/ m！；解法二：（比例分配法） . 8.平均法：若把kn个不同元素平均分成k组，每组n个，共有 . 例17：从1，2，3，4中任取2个元素将其平均分成2组有几种分法？有 （平均分组就用不着管组与组之间的顺序问题了）又例如将200名运动员平均分成两组，其中两名种子选手必在一组的概率是多少？ （ ） 注意：分组与插空综合. 例如：n个元素全排列，其中某m个元素互不相邻且顺序不变，共有多少种排法？有 ，当n – m+1 ≥m, 即m≤ 时有意义. 9.隔板法：常用于解正整数解组数的问题. 例18： 的正整数解的组数就可建立组合模型将12个完全相同的球排成一列，在它们之间形成11个空隙中任选三个插入3块摸板，把球分成4个组.每一种方法所得球的数目依次为 显然 ，故（ ）是方程的一组解.反之，方程的任何一组解 ，对应着惟一的一种在12个球之间插入隔板的方式（如图所示）故方程的解和插板的方法一一对应. 即方程的解的组数等于插隔板的方法数 . 注意：若为非负数解的x个数，即用 中 等于 ，有 ，进而转化为求a的正整数解的个数为 . 10.定位问题：从n个不同元素中每次取出k个不同元素作排列某r个元素都包含在内，并且都排在某r个指定位置则有 . 例19：从n个不同元素中，每次取出m个元素的排列，其中某个元素必须固定在（或不固定在）某一位置上，共有多少种排法？ 固定在某一位置上： ；不在某一位置上： 或 （一类是不取出特殊元素a，有 ，一类是取特殊元素a，有从m-1个位置取一个位置，然后再从n-1个元素中取m-1，这与用插空法解决是一样的） 11.指定元素排列组合问题. i. 从n个不同元素中每次取出k个不同的元素作排列（或组合），规定某r个元素都包含在内 。先C后A策略，排列 ；组合 . ii. 从n个不同元素中每次取出k个不同元素作排列（或组合），规定某r个元素都不包含在内。先C后A策略，排列 ；组合 . iii 从n个不同元素中每次取出k个不同元素作排列（或组合），规定每个排列（或组合）都只包含某r个元素中的s个元素。先C后A策略，排列 ；组合 . 12. 组合问题中分组问题和分配问题. ①均匀不编号分组：将n个不同元素分成不编号的m组，假定其中r组元素个数相等，不管是否分尽，其分法种数为 （其中A为非均匀不编号分组中分法数）.如果再有K组均匀分组应再除以 . 例20：10人分成三组，各组元素个数为2、4、4，其分法种数为 .若分成六组，各组人数分别为1、1、2、2、2、2，其分法种数为 ②非均匀编号分组: n个不同元素分组，各组元素数目均不相等，且考虑各组间的顺序，其分法种数为 例21：10人分成三组，各组人数分别为2、3、5，去参加不同的劳动，其安排方法为： 种. 若从10人中选9人分成三组，人数分别为2、3、4，参加不同的劳动，则安排方法有 种 ③均匀编号分组：n个不同元素分成m组，其中r组元素个数相同且考虑各组间的顺序，其分法种数为 . 例22：10人分成三组，人数分别为2、4、4，参加三种不同劳动，分法种数为 ④非均匀不编号分组：将n个不同元素分成不编号的m组，每组元素数目均不相同，且不考虑各组间顺序，不管是否分尽，其分法种数为 … 例23：10人分成三组，每组人数分别为2、3、5，其分法种数为 若从10人中选出6人分成三组，各组人数分别为1、2、3，其分法种数为 . 13. 分排问题“直排法”把几个元素排成前后若干排的排列问题，若没有其它的特殊要求，可采取统一排成一排的方法来处理。 例24、7个人坐两排座位，第一排3个人，第二排坐4个人，则不同的坐法有多少种？ 分析：7个人可以在前两排随意就坐，再无其它条件，故两排可看作一排来处理，不同的坐法共有 种。 14. 法 有些较复杂的问题可以通过列图表使其直观化。 例25、9 人组成篮球队，其中7人善打前锋，3人善打后卫，现从中选5人（两卫三锋，且锋分左、中、右，卫分左右）组队出场，有多少种不同的组队方法？ 分析：由题设知，其中有1 人既可打锋，又可打卫，则只会锋的有6人，只会卫的有2 人。列表如下： 人数 6人只会锋 2人只会卫 1人即锋又卫 结果 不同 选法 3 2 3 1 1（卫） 2 2 1（锋） 由表知，共有 种方法。 除了上述方法外，有时还可以通过设未知数，借助方程来解答，简单一些的问题可采用列举法等。解此类问题常用的数学思想是：分类讨论的思想，转化思想和对称思想等三种。排列组合是高中数学的重点和难点之一，也是进一步学习概率的基础。事实上，许多概率问题也可归结为排列组合问题。这一类问题不仅内容抽象，解法灵活，而且解题过程极易出现“重复”和“遗漏”的错误，这些错误甚至不容易检查出来，所以解题时要注意不断积累经验，总结解题规律，掌握若干技巧，最终达到能够灵活运用。 15. 转化法:对于某些较复杂的、或较抽象的排列组合问题，可以利用转化思想,将其化归为简单的、具体的问题来求解 例26. 马路上有编号为1,2,3,4,5,6,7,8,9的九只路灯,现要关掉其中的3盏,但不能关掉相邻的2盏或3盏,也不能关掉两端的2盏,求满足条件的关灯方法有多少种？ 解：把此问题当作一个排队模型：在6盏亮灯的5个空隙中插入3盏熄灯有 种． 例27. 某排共有10个座位,若4人就坐,每人左右两边都有空位,那么不同的坐法有多少种?解:等价于4人插5空模型: 一些不易理解的排列组合题，如果能转化为非常熟悉的模型，如占位填空模型，排队模型，装盒模型等，可使问题直观解决！ 例28. 高二年级8个班,组织一个12个人的年级学生分会,每班要求至少1人,名额分配方案有多少种? 　　分析 此题若直接去考虑的话,就会比较复杂.但如果我们将其转换为等价的其他问题,就会显得比较清楚,方法简单,结果容易理解. 　　解 此题可以转化为:将12个相同的白球分成8份,有多少种不同的分法问题,因此须把这12个白球排成一排,在11个空档中放上7个相同的黑球,每个空档最多放一个,即可将白球分成8份,显然有 种不同的放法,所以名额分配方案有 种. 16. 对等法:在有些题目中,它的限制条件的肯定与否定是对等的,各占全体的二分之一.在求解中只要求出全体,就可以得到所求. 例29. 期中安排考试科目9门,语文要在数学之前考,有多少种不同的安排顺序? 　　分析 对于任何一个排列问题,就其中的两个元素来讲的话,他们的排列顺序只有两种情况,并且在整个排列中,他们出现的机会是均等的,因此要求其中的某一种情况,能够得到全体,那么问题就可以解决了.并且也避免了问题的复杂性. 　　解 不加任何限制条件,整个排法有 种,“语文安排在数学之前考”,与“数学安排在语文之前考”的排法是相等的,所以语文安排在数学之前考的排法共有 种. 17. 利用映射关系解题: 就是运用集合的概念、逻辑语言、运算、图形来解决数学问题或非纯数学问题的思想方法. 例30．圆上有10个点，每两点连成一条线段，这些线段在圆内最多有多少个交点？以这些交点为顶点的三角形最多有多少个？ 解析：该题如果用枚举法显然很困难；同样用基本极数原理先算出弦的总数，然后算出交点，在减去圆外和圆上的交点个数亦很困难．利用映射关系，化难为易． 一个交点S是由两条线段p,q相交而得，反之，依题意两条在圆内相交的线段p,q确定一个交点S．即S与（p,q）可建立一一对应关系，又两条线段p,q分别是由圆上的两对点A,B与C,D连接而成．故又可在（p,q）与（A,B,C,D）之间建立一一对应关系．因此若令M={S|题中线段的交点}，N={（A,B,C,D）|10个点中，任意四个不同的点组}，则M与N中的元素构成一一对应关系，从而有|M|=|N|但N中元素个数显然为 =210，所以题中交点为210个．同样的考虑，圆 内一个三角形与圆上6个点之间构成一一对应关系，因此题中所求三角形的个数为 个． 18. 利用递推关系解题． 例31．有一楼梯共10级，每步只能跨上1级或2级，问要登上最后一级共有多少种走法？ 解析：因为每步只能跨上1级或2级，所以最后一步可能从第9级也可能从第8级跨上第10级，向前递推关系不变．设登上第k级有 种走法，显然 ，当k＞2时，登上第k级台阶的走法可以分两种情况得到：从第k-1级台阶跨一级登上第k级，或从第k-2级台阶,一步跨两级登上第k级．故当k≥3时，有 ∴ 例32.把圆分成10个不相等的扇形,并且用红、黄、蓝三种颜色给扇形染色,但不允许相邻的扇形有相同的颜色,问共有多少种染色法? 解析:前9个扇形依次染色并不难,但第10个扇形既与第九个相邻也与第1个相邻,这两个扇形颜色可能相同也可能不相同,所以直接用记数原理有困难,但建立递推关系并不难． 设将圆分成n个不相等的扇形时,满足题设的染法有 种．依次记n个扇形为s ,…s .显然a1=3.当n=2时，先对s1染色，有3种方法；s1染色后再对s2染色，有2种方法，故a2=6.当n≥3时，我们依次对s ,s2,…s 染色．对s1染色，有3种方法，对s1染色后再对s2染色有2种方法，同样的对s3,s4…,sn分别有2种方法，由乘法原理共有3·2 n-1种染色方法．但这样做sn与s1有可能同色．即在3·2 n-1种染色方法中包含了sn与s1同色的染色方法．对于sn与s1同色的情形，拆去sn与s1的边界使sn与s1合并，便得到将圆分为n-1个扇形时同色不相邻的染色方法，这样的情况有an-1种． 故an=3·2 n-1-an-1 (n≥3)．所以 a10=3·29-a9=3·29-3·28+a8=3·29-3·28+3·27-a7==3·29-3·28+3·27-3·26+3·25-3·24+3·23-3·22+3·21=210+2=1026． 19. 利用不等式(方程)组解题：在解决某些数学问题时，先设定一些未知数．然后把它们当作已知数，根据题设本身各量间的制约，列出等式，解方程即可。 例33．一个口袋内有4个不同的红球，6个不同的白球，若取一个红球记2分，取一个白球记1分，从中任取5个球，使总分不少于7分的取法有多少种？ 例34．将10个完全相同的小球放入编号为1,2,3的三个盒子内，要求放入盒子的球数不小于它的编号数，则不同的放法有（ ） A 20种 B15种 C14种 D12种 解：设编号为1,2,3的三个盒子中分别放入x,y,z个小球，于是题中不同的放法即为方程: x+y+z=10,且x≥1,y≥2,z≥3的非负整数解的个数．令u=x-1,v=y-2,w=z-3，得u+v+w=4,所以该方程的非负整数解的个数即为所求的放法数目C ，故选B ． 20. 标号排位问题分步法把元素排到指定号码的位置上，可先把某个元素按规定排入，第二步再排另一个元素，如此继续下去，依次即可完成． 例35.将数字1，2，3，4填入标号为1，2，3，4的四个方格里，每格填一个数，则每个方格的标号与所填数字均不相同的填法有 A．6种 B．9种C．11种 D．23种 分析 先把1填入方格，符合条件的有3种方法，第二步把被填入方格的对应数字填入其它三个方格，又有三种方法；第三步填余下的两个数字，只有一种填法，共有3×3×1＝9种填法，故选B． 21. 交叉问题集合法 某些排列组合问题几部分之间有交集，可用集合中求元素个数公式n(A∪B)＝n(A)＋n(B)－n(A∩B) 【例 36】从6名运动员中选出4个参加4×100m接力赛，如果甲不跑第一棒，乙不跑第四棒，共有多少种不同参赛方法？ 分析 设全集Ⅰ＝｛6人中任取4人参赛的排列｝，A＝｛甲第一棒的排列｝，B＝｛乙跑第四棒的排列｝，根据求集合元素个数的公式得参赛方法共有： 22.选排问题先取后排法从几类元素中取出符合题意的几个元素，再安排到一定位置上，可用先取后排法． 【例37】四个不同的球放入编号为1，2，3，4的四个盒中，则恰有一个空盒的放法共有________种 【例38】9名乒乓球运动员，其中男5名，女4名，现在要进行混合双打训练，有多少种不同分组法？ 23．部分合条件问题排除法在选取总数中，只有一部分合条件，可从总数中减去不合条件数，即为所求． 【例39】以一个正方体顶点为顶点的四面体共有 [ ] A．70个 B．64个 C．58个 D．52个 面体，但6个表面和6个对角面的四个顶点共面都不能构成四面体，所 【例40】正六边形中心和顶点共7个点，以其中3个点为顶点的三角形共有________个． II. 排列组合常见解题策略： ①特殊元素优先安排策略；②合理分类与准确分步策略；③排列、组合混合问题先选后排的策略（处理排列组合综合性问题一般是先选元素，后排列）；④正难则反，等价转化策略；⑤相邻问题插空处理策略； ⑥不相邻问题插空处理策略；⑦定序问题除法处理策略；⑧分排问题直排处理的策略；⑨“小集团”排列问题中先整体后局部的策略；⑩构造模型的策略.