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

排列组合问题的非常规解题数学思想方法湖南祁东育贤中学 周友良 匡宗春 421600分类计数，分步计数两个原理是解决排列、组合问题的基本方法，利用该两个原理及课堂中学习的常规解法如：特殊元素、特殊位置、插空法、捆绑法等解决某些问题总觉的较难或者解答较繁针对该现象本文列举几例介绍解排列组合问题的非常规解题思路一.数形结合思想例1.如下图所示,有5横8竖构成的方格图,从A到B只能上行或右行共有多少条不同的路线? 解法一: 如图所示,将一条路经抽象为如下的一个排法(5-1)+(8-1)=11格:其中必有四个和七个组成!所以, 四个和七个一个排序就对应一条路经,所以从A到B只能上行或右行共有条不同的路径.解法二:设 表示经过第i列的水平路段;设 表示经过第j行的竖直路段;如图所示,将一条路经抽象为如下的一个排法(5-1)+(8-1)=11格:可以看出这是 与 的一个分别顺序一定的排列,而且一个这样的排列对应一条路径.所以从A到B只能上行或右行共有条不同的路径.二.分类讨论思想例2.在六个空格里涂上红黄蓝三种颜色，每种颜色只能涂两次，要求相邻不同色，请问一共有多少种涂法。解法一：由题意，红黄蓝三种颜色，每种颜色恰好涂了两次，按一下分类进行：先将两个黄格插入到两个红格 的两端或中间，有5种情况: ， ， ， ， ， ，再将两个蓝格分别插入到四个红黄间隔的的两端或中间，有4+1+1+10+10+4=30种方法；所以，共有30种涂法。解方法二：由题意，红黄蓝三种颜色，每种颜色恰好涂了两次， 分为两类：123456第一类可按一下步骤进行：第1步：涂第一格，有3种方法；第2步：涂第二格，有2种方法；第3步：用与第一格不同的颜色涂第三格，有1种方法；第4步：第四格可以涂与第三格颜色不同的，有2种方法。第5步：用不同的两色涂剩下的两格，有2种方法；所以有3*2*1*2*224种第二类可按一下步骤进行：第1步：涂第一格，有3种方法；第2步：涂第二格，有2种方法；第3步：用与第一格相同的颜色涂第三格，有1种方法；第4步：第四格只能用没有用过的颜色涂，有种方法。第5步：第五格只能用涂第二格的颜色，第六格只能用涂第四格的颜色，有1种方法；所以有3*2*1*1*16种所以，共有24+630种涂法。解方法三：分成如下四类：第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+630种涂法三方程不等式思想例3一个口袋内有4个不同的红球，6个不同的白球，若取一个红球记2分，取一个白球记1分，从中任取5个球，使总分不少于7分的取法有多少种？ 例4将10个完全相同的小球放入编号为1,2,3的三个盒子内，要求放入盒子的球数不小于它的编号数，则不同的放法有（ ） A 20种 B15种 C14种 D12种解：设编号为1,2,3的三个盒子中分别放入x,y,z个小球，于是题中不同的放法即为方程: x+y+z=10,且x1,y2,z3的非负整数解的个数令u=x-1,v=y-2,w=z-3，得u+v+w=4,所以该方程的非负整数解的个数即为所求的放法数目C，故选B 四.模型构造思想例5.证明：。证明：原式左端可看成一个班有个同学，从中选出个同学组成兴趣小组，在选出的个同学中，个同学参加数学兴趣小组，余下的个同学参加物理兴趣小组的选法数。原式右端可看成直接在个同学中选出个同学参加数学兴趣小组，在余下的个同学中选出个同学参加物理兴趣小组的选法数。显然，两种选法是一致的，故左边=右边，等式成立。例6. 方程的非负整数解的组数是多少？分析：设则原题即转换为有多少正整数解。可由抽象到具体建立如下模型：将12个小球排成一列，在它们两之间形成的缝隙中任意插入3块木板，则把这12个球分成4组，而这4组的数目即为即原方程的非负整数解是：（组）.五.“正难则反”的思想解决问题，当正面难以解决时，不妨从反面、侧面思考，顺繁则逆、正难则反例7有五张卡片，他们的正反面分别写有0与1，2与3，4与5，6与7，8与9，将其中任意三张排放在一起组成三位数，共可组成多少个不同的三位数？解析：（1）0不能作百位，但可以作十位或个位（2）0与1在同张卡片上，因此直接分类既要考虑0又要考虑1分类较复杂于是先不考虑任何情况算出总数，然后减去0在左边第一位的号码即为所求由于任取三张可以组成不同的三个数的号码有：，其中0在左边第一位的号码有：，故所求的不同三位数共有：-=432 个例8从1，2，3，1995这1995个自然数中，取出9个互不相邻的自然数，有多少种方法？解析：由于符合题意的条件错综复杂，正面进攻思维受阻，此时采用反面去考虑问题问题相当于“9个女生不相邻地插入站成一列横队的1986个男生之间（包括首尾外侧），有多少种方法？”任意相邻2个男生之间最多站1个女生，队伍中的男学生首尾两侧最多也可各站1个女学生，于是，这就是1987个位置中任选9个位置的组合问题，共有种方法六. 枚举法把符合条件的安排不重复、不遗漏的一一列举出来，是最简单、最原始但也是最基本的计数方法教材中多次应用到，高考中也常用枚举法解决问题例9某电脑用户计划使用不超过500元的资金购买单价分别60元、70元的单片软件和盒装磁盘，根据需要，软件至少买3片，磁盘至少买2盒，则不同的选购方法有（ ）A5种B6种C7种D8种解析：根据所给选项数字较小，不难用枚举法解决单片买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，10034952，100495051，52，100505152，10049991001所以共有：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中元素个数显然为=210，所以题中交点为210个同样的考虑，圆 内一个三角形与圆上6个点之间构成一一对应关系，因此题中所求三角形的个数为个八. 利用递推关系解题例12有一楼梯共10级，每步只能跨上1级或2级，问要登上最后一级共有多少种走法？解析：因为每步只能跨上1级或2级，所以最后一步可能从第9级也可能从第8级跨上第10级，向前递推关系不变设登上第k级有种走法，显然，当k2时，登上第k级台阶的走法可以分两种情况得到：从第k-1级台阶跨一级登上第k级，或从第k-2级台阶,一步跨两级登上第k级故当k3时，有例13.把圆分成10个不相等的扇形,并且用红、黄、蓝三种颜色给扇形染色,但不允许相邻的扇形有相同的颜色,问共有多少种染色法?解析:前9个扇形依次染色并不难,但第10个扇形既与第九个相邻也与第1个相邻,这两个扇形颜色可能相同也可能不相同,所以直接用记数原理有困难,但建立递推关系并不难设将圆分成n个不相等的扇形时,满足题设的染法有种依次记n个扇形为s,s.显然a1=3.当n=2时，先对s1染色，有3种方法；s1染色后再对s2染色，有2种方法，故a2=6.当n3时，我们依次对s,s2,s染色对s1染色，有3种方法，对s1染色后再对s2染色有2种方法，同样的对s3,s4,sn分别有2种方法，由乘法原理共有32 n-1种染色方法但这样做sn与s1有可能同色即在32 n-1种染色方法中包含了sn与s1同色的染色方法对于sn与s1同色的情形，拆去sn与s1的边界使sn与s1合并，便得到将圆分为n-1个扇形时同色不相邻的染色方法，这样的情况有an-1种 故an=32 n-1-an-1 (n3)所以a10=329-a9=329-328+a8=329-328+327-a7=329-328+327-326+325-324+323-322+321=210+2=1026九.对称法例14A,B,C,D,E五人站成一排，若B必须站在A的右边（A,B可以不相邻）的不同站法有（ ） A 24种 B60种 C90种 D120种解：B站在A的右边与B站在A的左边一样多，有对称分析得=60种，选B应用对称性简洁明快，给人以美的享受十.机会均等法 例15：10个人排成一队，其中甲一定要在乙的左边，丙一定要在乙的右边，一共有多少种排法？ 解：甲、乙、丙三人排列一共有6种排法，在这6种排法中各种排列顺序在10个人的所有排列中出现的机会是均等的，因此符合题设条件的排法种数为。 例16：用1，4，5，四个数字组成四位数，所有这些四位数中的数字的总和为288，求。 解：若不为0，在每一个数位上1，4，5，出现的机会是均等的。由于一共可以得到24个四位数，所以每一个数字在每一个数位上出现6次，于是得到： ，解得。 若为0，无解。十一.转化法 例17：一个楼梯共10级台阶，每步走1级或2级，8步走完，一共有多少种走法？ 解：10级台阶，要求8步走完，并且每步只能走一级或2级。显然，必须有2步中每步走2级，6步中每步走一级。记每次走1级台阶为A，记每次走2级台阶为B，则原问题就相当于在8个格子中选2个填写B。其余的填写A，这是一个组合问题，所以一共有种走法。 例18：动点从（0，0）沿水平或竖直方向运动到达（6，8），要使行驶的路程最小，有多少种走法？ 解：动点只能向上或向右运动才能使路程最小而且最小的路程为14，把动点运动1个单位看成是1步，则动点走了14步，于是问题就转化为在14个格子中填写6个“上”和8个“右”，这也是一个组合的问题，于是得到一共有种走法。电子邮箱周友良 zyl2518006,手机号码[phone]； 湖南祁东育贤中学 周友良 421600