排列组合问题的非常规解题数学思想方法

排列组合问题的非常规解题数学思想方法湖南祁东育贤中学周友良匡宗春421600分类计数，分步计数两个原理是解决排列、组合问题的基本方法，利用该两个原理及课堂中学习的常规解法如：特殊元素、特殊位置、插空法、捆绑法等解决某些问题总觉的较难或者解答较繁．针对该现象本文列举几例介绍解排列组合问题的非常规解题思路．一.数形结合思想例1.如下图所示,有5横8竖构成的方格图,从A到B只能上行或右行共有多少条不同的路线?奎屯王新敞新疆BA解法一:如图所示,BA将一条路经抽象为如下的一个排法(5-1)+(8-1)=11格:→↑→↑↑→→→↑→→其中必有四个↑和七个→组成!所以,四个↑和七个→一个排序就对应一条路经,所以从A到B只能上行或右行共有514(51)(81)11CC条不同的路径.解法二:设ia(1,2,3,4,5,6,7)i表示经过第i列的水平路段;设jb(1,2,3,4)j表示经过第j行的竖直路段;如图所示,b4b3b2b1a7a6a5a4a3a2a1BA将一条路经抽象为如下的一个排法(5-1)+(8-1)=11格:1a1b2a2b3b3a4a5a4b6a7a可以看出这是ia(1,2,3,4,5,6,7)i与jb(1,2,3,4)j的一个分别顺序一定的排列,而且一个这样的排列对应一条路径.所以从A到B只能上行或右行共有11411117474ACAA条不同的路径.二.分类讨论思想例2.在六个空格里涂上红黄蓝三种颜色，每种颜色只能涂两次，要求相邻不同色，请问一共有多少种涂法。解法一：由题意，红黄蓝三种颜色，每种颜色恰好涂了两次，按一下分类进行：先将两个黄格■■插入到两个红格■■的两端或中间，有5种情况:■■■■，■■■■，■■■■，■■■■，■■■■，■■■■，再将两个蓝格分别插入到四个红黄间隔的的两端或中间，有4+1+1+10+10+4=30种方法；所以，共有30种涂法。解方法二：由题意，红黄蓝三种颜色，每种颜色恰好涂了两次，分为两类：第一类可按一下步骤进行：第1步：涂第一格，有3种方法；第2步：涂第二格，有2种方法；第3步：用与第一格不同的颜色涂第三格，有1种方法；第4步：第四格可以涂与第三格颜色不同的，有2种方法。第5步：用不同的两色涂剩下的两格，有2种方法；所以有3*2*1*2*2＝24种第二类可按一下步骤进行：第1步：涂第一格，有3种方法；第2步：涂第二格，有2种方法；第3步：用与第一格相同的颜色涂第三格，有1种方法；第4步：第四格只能用没有用过的颜色涂，有种方法。第5步：第五格只能用涂第二格的颜色，第六格只能用涂第四格的颜色，有1种方法；所以有3*2*1*1*1＝6种所以，共有24+6＝30种涂法。解方法三：分成如下四类：第1类：□■□■■■1，3同色有3种颜色可选，剩余的四格必须2，5同色有2种颜色可选，共有6种涂法；第二类：□■■□■■1，4同色有3种颜色可选，剩余的四格必须2，3各涂1色有2种颜色可选，5，6各涂1色有2种颜色可选，共有12种涂法；第三类：□■■■□■1，5同色有3种颜色可选，剩余的四格必须3，6同色有2种颜色可选，共有6种涂法；第四类：□■■■■□1，6同色有3种颜色可选，剩余的四格必须2，4同色有2种颜色可选，共有6种涂法；所以，共有6+12+6+6+6＝30种涂法奎屯王新敞新疆三．方程不等式思想例3．一个口袋内有4个不同的红球，6个不同的白球，若取一个红球记2分，取一个白球记1分，从中任取5个球，使总分不少于7分的取法有多少种？种符合题意的取法种数有或或则个白球个红球解：设取186142332)60(72)40(5,,164426343624CCCCCCyxyxyxyyxxyxyx例4．将10个完全相同的小球放入编号为1,2,3的三个盒子内，要求放入盒子的球数不小于它的编号数，则不同的放法有（）A20种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,所以该方程的非负整数解的个数即为所求的放法数目C154134，故选B．四.模型构造思想123456例5.证明：pnpmpmpnnmCCCC。证明：原式左端可看成一个班有m个同学，从中选出n个同学组成兴趣小组，在选出的n个同学中，p个同学参加数学兴趣小组，余下的pn个同学参加物理兴趣小组的选法数。原式右端可看成直接在m个同学中选出p个同学参加数学兴趣小组，在余下的pm个同学中选出pn个同学参加物理兴趣小组的选法数。显然，两种选法是一致的，故左边=右边，等式成立。例6.方程84321xxxx的非负整数解的组数是多少？分析：设),4,3,2,1(1ixyii则,1iy原题即转换为124321yyyy有多少正整数解。可由抽象到具体建立如下模型：将12个小球排成一列，在它们两之间形成的缝隙中任意插入3块木板，则把这12个球分成4组，而这4组的数目即为,,,,4321yyyy即原方程的非负整数解是：165311C（组）.五.“正难则反”的思想解决问题，当正面难以解决时，不妨从反面、侧面思考，顺繁则逆、正难则反．例7．有五张卡片，他们的正反面分别写有0与1，2与3，4与5，6与7，8与9，将其中任意三张排放在一起组成三位数，共可组成多少个不同的三位数？解析：（1）0不能作百位，但可以作十位或个位．（2）0与1在同张卡片上，因此直接分类既要考虑0又要考虑1分类较复杂．于是先不考虑任何情况算出总数，然后减去0在左边第一位的号码即为所求．由于任取三张可以组成不同的三个数的号码有：AC333352，其中0在左边第一位的号码有：AC222242，故所求的不同三位数共有：AC333352-AC222242=432个．例8．从1，2，3，…，1995这1995个自然数中，取出9个互不相邻的自然数，有多少种方法？解析：由于符合题意的条件错综复杂，正面进攻思维受阻，此时采用反面去考虑问题．问题相当于“9个女生不相邻地插入站成一列横队的1986个男生之间（包括首尾外侧），有多少种方法？”任意相邻2个男生之间最多站1个女生，队伍中的男学生首尾两侧最多也可各站1个女学生，于是，这就是1987个位置中任选9个位置的组合问题，共有C91987种方法．六.枚举法把符合条件的安排不重复、不遗漏的一一列举出来，是最简单、最原始但也是最基本的计数方法．教材中多次应用到，高考中也常用枚举法解决问题．例9．某电脑用户计划使用不超过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．例10．从1到100的一百个自然数中，每次取出两个数，使其和大于100，这样的取法共有多少种？解：从1到100的一百个自然数中，每次取出两个数，其中必有一个是较小的．我们先按较小的一数枚举，而当较小的数取定以后，使和超过100的另一个相应较大的数不难一一例举，所有情况如下表：较小数相应可取的较大数取法种数11001299，1002398，99，1003………4952，…，100495051，52，…，100505152，…，10049………991001所以共有：1+2+3+…+49+50+49+…+1=2500种不同的取法．评注：利用枚举法解题，直观性强，是处理排列组合问题的好方法．七.利用映射关系解题．例11．圆上有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中元素个数显然为C410=210，所以题中交点为210个．同样的考虑，圆内一个三角形与圆上6个点之间构成一一对应关系，因此题中所求三角形的个数为210610C个．八.利用递推关系解题．例12．有一楼梯共10级，每步只能跨上1级或2级，问要登上最后一级共有多少种走法？解析：因为每步只能跨上1级或2级，所以最后一步可能从第9级也可能从第8级跨上第10级，向前递推关系不变．设登上第k级有ak种走法，显然2,121aa，当k＞2时，登上第k级台阶的走法可以分两种情况得到：从第k-1级台阶跨一级登上第k级，或从第k-2级台阶,一步跨两级登上第k级．故当k≥3时，有aaakkk21∴892134212788910aaaaaaa例13.把圆分成10个不相等的扇形,并且用红、黄、蓝三种颜色给扇形染色,但不允许相邻的扇形有相同的颜色,问共有多少种染色法?解析:前9个扇形依次染色并不难,但第10个扇形既与第九个相邻也与第1个相邻,这两个扇形颜色可能相同也可能不相同,所以直接用记数原理有困难,但建立递推关系并不难．设将圆分成n个不相等的扇形时,满足题设的染法有an种．依次记n个扇形为s1,…sn.显然a1=3.当n=2时，先对s1染色，有3种方法；s1染色后再对s2染色，有2种方法，故a2=6.当n≥3时，我们依次对s1,s2,…sn染色．对s1染色，有3种方法，对s1染色后再对s2染色有2种方法，同样的对s3,s4…,sn分别有2种方法，由乘法原理共有3·2n-1种染色方法．但这样做sn与s1有可能同色．即在3·2n-1种染色方法中包含了sn与s1同色的染色方法．对于sn与s1同色的情形，拆去sn与s1的边界使sn与s1合并，便得到将圆分为n-1个扇形时同色不相邻的染色方法，这样的情况有an-1种．故an=3·2n-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．九.对称法．例14．A,B,C,D,E五人站成一排，若B必须站在A的右边（A,B可以不相邻）的不同站法有（）A24种B60种C90种D120种解：∵B站在A的右边与B站在A的左边一样多，有对称分析得21A55=60种，选B．应用对称性简洁明快，给人以美的享受．十.机会均等法例15：10个人排成一队，其中甲一定要在乙的左边，丙一定要在乙的右边，一共有多少种排法？解：甲、乙、丙三人排列一共有6种排法，在这6种排法中各种排列顺序在10个人的所有排列中出现的机会是均等的，因此符合题设条件的排法种数为166048001010P。例16：用1，4，5，x四个数字组成四位数，所有这些四位数中的数字的总和为288，求x。解：若x不为0，在每一个数位上1，4，5，x，出现的机会是均等的。由于一共可以得到24个四位数，所以每一个数字在每一个数位上出现6次，于是得到：64145288()x，解得x2。若x为0，无解。十一.转化法例17：一个楼梯共10级台阶，每步走1级