高中联赛排列组合的解法

数学竞赛中的排列组合问题江苏省梁丰高级中学(215600)张伟新排列组合问题主要依据分类计数原理和分步计数原理，其本身应用的知识并不多，但由于题目灵活多样，在各级各类考试中经常出现，在数学竞赛活动中尤其突出。其解题方法也多种多样，归纳起来，我们一般可用下面的方法来解决。一、列举法：例1、从0、1、2、3、4、5、6、7、8、9这10个数中取出3个数，使其和为不小于10的偶数，不同的取法有。（1998年全国高中数学联赛）解：从10个数中取出3个数，使其和为偶数，则这三个数都为偶数或一个偶数二个奇数。当三个数都为偶数时，有35C种取法；当有一个偶数二个奇数时，有15C25C种取法。题意要使其和为不小于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）。因此，符合题设要求的取法有35C+15C25C－9=51种。例2、设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共4种。因此这5次跳法共有64=24种不同跳法。一共有2+24=26种不同跳法。二、分类讨论：在排列组合问题中，利用分类讨论来解决问题最为常见。如何分类、分几类成为解题的关键。下面举例说明。例3、如图：在一个正六边形的六个区域栽种观赏植物，要求同一块中种同一种植物，相邻的两块种不同的植物，现有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种方法。ABCDEFFEDCBA（3）若A、C、E种三种植物，此时共有34A222=192种方法。所以共计有108+432+192=732种方法。例4、从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一种颜色，每两个具有公共棱的面染成不同的颜色。则不同的染色方案共有种。（注：如果我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体的上、下、左、右、前、后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案相同。）（1996年全国高中数学联赛）解：本题情况较为复杂，我们对用了多少种颜色进行分类讨论。（1）若只用三种颜色，从六种不同颜色中选用3种颜色有36C种选法。由于每两个具有公共棱的面染成不同的颜色，则正方体的相对面均为同色，由正方体的对称性知这样的染色方案只有一种。因此共有36C=20种不同的染色方案。（2）若只用四种颜色，从六种不同颜色中选用4种颜色有46C种选法。则仅有一个相对面不同色，共有24C种不同的涂法。因此共有46C24C=90种不同的染色方案。（3）若只用五种颜色，从六种不同颜色中选用5种颜色有56C种选法。则仅有一个相对面同色，不妨定为上、下底面，其有15C种涂法。再涂侧面，有3种涂法。因此共有56C15C3=90种不同的染色方案。（4）用六种不同颜色来涂色。则六个面的颜色均不相同，假想颜色已经涂好，我们可以通过适当的翻转，使上底面均为同一种颜色（例如红色），再考虑下底面，则一定有5种不同的颜色。对下底面是同一种颜色的（例如蓝色），再用余下的四种颜色来涂侧面，有!33!4种涂法。因此共有53！=30种不同的染色方案。一共有20+90+90+30=230种不同的染色方案。三、构造不定方程：先介绍一个引理：引理：求证：不定方程nxxxxm321（),2,2nmnm的正整数解有11mnC组。证明：本题可用“挡板法”求解，由于11x，12x，---，1mx，把n分成n个1，这n个1共有n―1个空挡。插入m―1块挡板，把n个1分成m个部分。则每一种情况对应不定方程的一组解，所以原不定方程共有11mnC组解。推论：不定方程nxxxxm321（),2Nnm的非负整数解有11mmnC组。证明：把方程nxxxxm321化为mnxxxxm)1()1()1()1(321，令111yx，221yx，331yx，----，mmyx1，即求mnyyym21的正整数解的组数，由引理可得共有11mmnC组解。在一些排列组合问题中，除了用其他的解法外，我们还可以用不定方程的正整数解的组数来确定排列组合数的多少。例5、已知两个实数集合10021,,,aaaA与5021,,,bbbB。若从A到B的映射f使得B中每个元素都有原像，且)()()(10021afafaf，则这样的映射共有（）（A）50100C（B）4899C（C）49100C（D）4999C（2002年全国高中数学联赛）解：不妨设5021bbb，又因为B中每个元素都有原像，设1b原像的集合为1A，其元素个数为1x；2b原像的集合为2A，其元素个数为2x；--------50b原像的集合为50A，其元素个数为50x。则1005021xxx（），则问题转化为求不定方程（）的正整数解的组数，共有4999C组解，故选（D）。例6、8个女孩和25个男孩围成一圈，任意两个女孩之间至少站两个男孩，那么，共有多少种不同的排列方法。（只要把圈旋转一下就重合的排法认为是相同的）（1990年全国高中数学联赛）解：先排女孩，这是一个圆排列问题，易知共有!78!8种不同的排列。8个女孩的圆排列共留出8个空挡。再排男孩，设这8个空挡中的男孩数分别为1x，2x，3x，------8x，25821xxx，由于任意两个女孩之间至少站两个男孩，即求不定方程在21x，22x，23x，-----，28x下的正整数解的组数，所以不定方程可化为17)1()1()1(821xxx，令111yx，221yx，331yx，-----，881yx，即得17821yyy，其正整数解的组数是716C。再对男孩全排列，共有716C!25种排列。所以共有716C!7!25种不同的排列方式。例7、如果从数1、2、3、---14中，按由小到大的顺序取出a1、a2、a3使同时满足a2―a13与a3―a23，那么所有符合上述要求的不同取法有种。（1989年全国高中数学联赛）解：由11a，312aa，323aa，0143a，令11xa，212xaa，323xaa，4314xa，则144321xxxx，问题即求不定方程在11x，32x，33x，04x下的整数解的组数，又方程转化为11)1()2()2(4321xxxx。令11yx，222yx，332yx，441yx，而114321yyyy的正整数解的组数是310C。所以符合条件的a1、a2、a3的不同取法有310C=120种。四、利用递推关系：在一些排列组合问题中，我们可以从简单问题入手，寻找规律，继而把问题一般化，寻找更一般的关系式，即递推关系式，然后解决具体问题。例8、有排成一行的n个方格，用红、黄、蓝三色涂每个格子，每格涂一色，要求任何相邻的格不同色，且首尾两格也不同色，问有多少种涂法？（1991年江苏夏令营）解：设共有na种不同涂法。易得1a=3，2a=6，3a=6。且当4n时，将n个格子依此编号后，则格1与格（1n）不相邻。（1）若格（1n）涂色与格1不同，此时格n只有一色可涂，且前1n格满足首尾两格不同色，故有1na种不同涂法。（2）若格（1n）涂色与格1相同，此时格（2n）与格1涂色必然不同，否则格（1n）与格（2n）相同，于是前2n格有2na种不同涂法。因为格n与格1不同色，有两种涂法，故有22na种不同涂法。综上可得递推关系式：na=1na+22na（4n），并可得nnna)1(22（2n）。例9、一只猴子爬一个8级的梯子，每次可爬一级或上跃二级，最多上跃三级。从地面上到最上一级，一共可以有种不同的爬跃方式。（中等数学2001.3奥林匹克训练题）解：易得1a=1，2a=2，3a=4，4a=7。把问题一般化，设一共有n级梯子，每次可爬一级或上跃二级，最多上跃三级。设共有na种不同的爬跃方式。若第一次爬了一级，则有1na种方式；若第一次上跃二级，则有2na种方式；若第一次上跃三级，则有3na种方式。因此na=1na+2na+3na。易得818a。即共有81种不同的爬跃方式。江苏省梁丰高级中学邮编：215600E—mail：[e-mail]练习题：1、用红、黄、蓝三色给正方体表面染色，每面只染一种颜色，每色各染两个面，如果经过适当翻转可使两个染色的正方体各对应面的颜色相同者视为一种染色方法，那么，不同的染色方法种数为（）（A）3种（B）5种（C）8种（D）12种（2003江苏省数学夏令营）（提示：三种颜色都涂相对两面，有1种方法；一种颜色涂相对两面，有3种方法；三种颜色都不涂在相对面，有1种方法。共有5种方法。）2、如果：（1）a，b，c，d都属于4,3,2,1；（2）ba，cb，dc，ad；（3）a是a，b，c，d中的最小值。那么，可以组成的不同的四位数abcd的个数是。（2000年全国高中数学联赛）（提示：（1）abcd由2个不同数字组成，则必有a=c，故有24C=6个。（2）abcd由3个不同数字组成，则a唯一确定，当ac，db,有2种取法；当ac，c有2种取法，b=d为余下的数，故有34C（2+2）=16个。（3）abcd由4个不同数字组成，1a，故有3！=6个。因此一共有6+16+6=28个不同的四位数。）3、在正方体的8个顶点、12条棱的中点、六个面的中心及正方体的中心共27个点中，共线的三点组的个数是（）（A）57（B）49（C）43（D）37（1998年全国高中数学联赛）（提示：（1）两端点皆为顶点的共线三点组共有28278个；（2）两端点皆为面的中心的共线三点组共有3216个；两端点皆为各棱中点的共线三点组共有182312个；因此共有28+3+18=49个。）4、在世界杯足球赛前，F国教练为了考察1A，2A，----7A这七名队员，准备让他们在三场训练比赛（每场90分钟）中都上场。假设在比赛的任何时刻，这些队员中有且仅有一人在场上，且1A，2A，3A，4A每人上场的总时间（以分钟为单位）均能被7整除，5A，6A，7A每人上场的总时间（以分钟为单位）均能被13整除。如果每场换人次数不限，那么，按每名队员上场的总时间计算，共有多少种不同的情况。（2002年全国高中数学联赛）(提示：设第i名队员上场的时间为ix分钟（i=1，2，3，----，7），问题即求不定方程270721xxx在条件ix7（41i）且jx13（75j）下的正整数解的组数。由条件，设mxxxx74321，nxxx13765，3,4nm）。于是m、n即是不定方程7m+13n=270的一组正整数解。4