排列、组合问题及对策

排列、组合问题及对策http:/www.DearEDU.com摘要：排列、组合知识是数学知识来源于生活，又应用于生活的具体体现。不同情况下的排列、组合问题的解决，是提高人们利用数学知识解决现实问题能力的一种途径。关键字：排列、组合、分类、分步、元素、特殊、相邻排列组合问题与现实生活有密切联系，在很多领域有广泛的应用，是当今发展很快的组合数学的最初步知识。这种以记数问题为特征的内容在中学数学中是较为独特的。它不仅应用广泛，是学习概率与统计知识以及进一步学习高等数学有关知识的准备知识，而且由于其思想方法独特灵活，也是发展学生抽象能力和逻辑思维能力的素材。正因如此，它也是学习高中数学的一个难点。下面，我谈谈高中数学中排列与组合问题的常见类型及应对策略。一、有限制排列问题有限制排列问题，因限制条件不同，而使问题复杂多样，解决手段也必须“对症下药”。常见的限制条件及对策。1、 有特殊元素或特殊位置。2、 元素必须相邻的排列。、3、 元素不相邻的排列。4、 元素有顺序限制的排列。基本的解题思想方法为：1、 对于特殊元素或特殊位置，一般采用直接法。即先排特殊元素或特殊位置。2、 相邻排列问题，通常采用“捆绑”法，即可以把相邻元素看作一个整体参与其它元素排列，同时对相邻元素自排。3、 对于元素不相邻的排列，可以先考虑不受限制的元素的排列。再把不相邻的元素插在前面元素排列的空位和两端。4、 对于元素顺序有限制的排列，可以先不考虑限制排列后，利用规定顺序的实情求结果。在实际解题过程中，首先必须认真审题，明确问题为排列还是组合问题。其次是抓住问题的本质特征，灵活运用基本原理和公式进行分析解答，同时还要注意一些方法和技巧，使一些看似复杂的问题迎刃而解。1、 特殊优先法对于存在特殊元素或特殊位置的排列组合问题，我们可以从这些特殊入手。先满足特殊元素或特殊位置，再去满足其它元素或位置，这种解法叫做特殊优先法。例：1名老师和4名学生排成一排，若老师不排在两端，则共有多少种不同的排法？分析：（解法1、特殊元素法）老师在中间3个位置上任选1个的选法有A41种，然后剩余的四名学生在余下的四个位置上，排法有A44种。由分步记数原理，所以共有A31A44=72 种。（解法2、特殊位置法）先安排两端站两名学生共有A42种方法，其余位置安排有A33种。所以共有排法数为A42A33=72种。答案：72种。2、 总体淘汰法对于含否定词的问题，还可以从总体中把不符合要求的除去。比如上面的例题中，1名老师和4名学生共5人，其排列方法为A55种，把老师排在队伍两端的情况A21A44减去。所以方法数为A55-A21 A44=72种。答案：72种。3、 相邻问题用“捆绑法”对于某些元素要求相邻的问题，可先将相邻的元素捆绑并看作一个元素并与其它元素进行排列，同时对相邻元素内部进行排列。例：3个女生与5个男生排在一起，女生必须在一起，可以有多少种不同的方法？分析：因为3个女生必须排在一起，所以可以把她们看作一个整体，连同5个男生共6个元素，排成一排有A66种不同的排法，同时每种排法中，女生之间又有A33种不同的排法，利用分步记数原理，可得有A66A33种不同的排法。答案：A66A334、 问题用“插空法”对于几个元素不相邻的排列问题，先将没有限制条件的元素排好，然后再将不相邻的元素在已排好的元素之间及两端的空隙插入即可。例：7人排成一排照相，若要求甲、乙、丙三人不相邻，有多少种不同的排法？分析：先将其余4人站好，有A44种排法，再于4人之间及两端5个“空隙”中选3个位置将甲、乙、丙插入，有A53种方法。由分步记数原理，这样共有A44A53种不同的排法。答案：A44A53 5、 顺序问题用“除法”对于几个元素顺序一定的排列问题，可先把这几个元素同其余元素一同进行排列，然后用总的排列数除以这几个元素的全排列数。例：7个节目，甲、乙、丙三个节目按给定顺序出现，有多少种排法？分析：7个节目的全排列为A77,甲、乙、丙之间的顺序已定。所以有A77A33=840种。答案：840种。6、 分排问题用“直排法”把n个元素排成几排的问题，若没有其它特殊要求，可采用统一排成一排的方法来处理。例：15人排成两排，前排7人，后排8人，共有多少种不同的方法？分析：前排7人有A157种方法，后排8人有A88种方法，所以有A157A88=A1515种不同方法。其实就相当于将15个人排成一排。答案：A1515种7、 穷举法当题目中的附加条件增多，结果数目不大，解决它的方法又不一般，采用穷举法有时能取得意想不到的效果。例：三边长均为整数，最长边为8 的三角形有多少个？分析：另两边用字母x、y表示，且不妨设1xy8，x+y9当 y=8时，x=1,2,8, 有8个。当y=7时，x=2,37 有6个。当y=6时，x=3,4,5,6,有4个当y=5时，x=4,5,有2 个。所以，所求的三角形的个数为8+6+4+2=20。答案：20个。8、 特征分析研究有约束条件的排数问题，需紧扣题中所提供的数字特征，结构特征，进行推理，分析求解。例：由1，2，3，4，5，6这六个数可组成多少个无重复且是6的倍数的五位数？分析：6的倍数既是2的倍数，又是3的倍数。是2的倍数，个位上为2、4或6；是3 的倍数必须满足各个数字上的数字之和是3的倍数的特征。把这6个数分组（3）、（6）、（1，5）、（2，4），每组的数字和都是3的倍数，因此可分成两类讨论。第一类：由1、2、4、5、6作数码，首先从2、4、6中任选一个作为个位数字，有A31种，然后其余4个数字在其它数字上全排列有A44,所以，N1=A31A44个，第二类：由1、2、3、4、5作数码，依上法有N2=A21A44个。故N=N1+N2=120个。答案：120个。9、 对应有些时候，一个事件与一个结果之间存在一一对应的关系。例：在100名选手之间进行单循环淘汰赛（即一场比赛后，失败者退出比赛），最后产生一名冠军，需举行多少场比赛？分析：要产生一名冠军，需要淘汰99名选手。要淘汰掉一名选手，必须举行一场比赛；反之，每场比赛恰淘汰一名选手。两者之间一一对应。故要淘汰99名选手，应举行99场比赛，从而产生一名冠军。答案：99场。10、消序某些条件，使得元素位置确定。例：有3个男生，3个女生，排成一列，高矮互不相等。要求从前到后，女生从高到矮排列，有多少种不同的排法？分析：先从6个位置中选3个位置排男生，有A63种不同排法。余下3个位置排女生，因要求“从高到低”所以女生的排法只有一种。故有A63=120 种。答案：120种。11进住法解决允许重复排列问题要注意区分两类元素：一类元素可以重复，另一类不能重复。把不能重复的元素看成“一封信”，能重复的元素看成“信箱”。在利用乘法原理直接求解的方法称为进住法。例：5名运动员争夺3个项目的冠军（没有并列），所以可能的结果有多少种？分析：因为同一运动员可以同时夺得几项冠军，故运动员可以重复排列，将5名运动员看作五个信箱，3项冠军看成3封信，每封信可以投进五个信箱，有5种投递方法。由乘法原理知有53种。答案：53种12、探索对情况复杂，不易发现规律的问题，要仔细分析，探索其中规律，再予以解决。例：从1到100的自然数中，每次取出两个数，使它们的很大于100，则弥补台的取法有多少种？分析：此题数字较多，情况不一样。需要分析摸索其规律。为方便，我们称两个加数中较小的为被加数。因1+100100，1为被加数的只有一种。2+99100，2+100100，2为被加数的有两种。同理，3为被加数的有3种49为被加数的有49种。50为被加数的有50种。但51为被加数的只有49种99为被加数的只有一种。故不同的取法有（1+2+3+50）+（49+48+1）=2500种。答案：2500种。）13、“树图”表示法 对某些分步进行的问题，可依次对每步可能出现的情况用“树”状图形表示出来。例：四人各写出一张贺卡，先集中起来，然后每人从中拿一张别人送出的贺卡，则四张贺卡的不同分配方式有（ ）种。A.6 B.9 C.11 D.32分析：将四张贺卡分别记为A,B,C,D。由题意，某人（不妨设为A卡的供卡人）取卡有3种情况。因此将卡的不同分配方式分为三类，对于每一类，其它人依次取卡分步进行。为避免重复或遗漏现象，可用树状图表示。 ADC ADB ABCBCDA CDAB DCAB DAC DBA CBA所以共有9种不同的分配方式。答案：B 。14、用比例法有些排列应用题，可以根据每个元素出现机会占整个问题的比例，从而求得问题的结果。例：A、B、C、D、E五人站成一排，如果B必须站在A的右边（A、B 可以不相邻），不同的排法有多少种？分析：若没有限制条件，则5人的全排列有A55=120种，而A在B右边与B在A右边各占一半，所以B在A右边的排列法有12A55=60种。答案：60种。例：从6个运动员中选出4个参加4100 米接力赛。如果甲、乙都不能跑第一棒，那么共有多少种不同的参赛方案？分析：若不受条件限制，则参赛方案有A64=360种，但其中限制甲、乙两人不能跑第一棒，即跑第一棒的只能是其他的人，而这4人在第一棒中出现的可能性为4/6故所求参赛方案有46A64=240种。答案：240种。以上介绍了排列应用题的几种常见求解策略。这些策略不是彼此孤立的，而是相互依存。有时解决某一问题是要综合运用几种求解策略。在处理具体问题时，应能合理分类与准确分步。首先要弄清楚：要完成的是一件什么事，完成这件事有几类方法，每类方法中，又有几个步骤。这样才会不重复、不遗漏地解决问题。二、 组合问题常见类型及策略1、在解组合应用题时，常会遇到“至少”、“最多”、“含”等词，要仔细审题，理解其含义。2、分组、分配问题：分组和分配是有区别的。分组问题中只要组与组之间，元素个数相同，是不可分的。而分配问题中即使元素个数相同，但因元素不同，仍然是可区分的。对于这类问题，必须遵循先分组后排列，若平均分成m组，则分法=分法m!3、指标问题采用“隔板法”，每种隔板对应一种分法。例1：从12人中选出5人去参加一项活动。按下列要求，有多少中不同的选法。（1）A、B、C三人必须入选。（2）A、B、C三人不能入选。（3）A、B、C三人只有一人入选。（4）A、B、C三人至少1人入选。（5）A、B、C三人至多二人入选。 分析（1）：须从其余9人中任选2人，所有C92=36种。（2）：须从其余9人中任选5人，所以有C95=126种。（3）：从三人中任选一人，有C31种结果，再从其余9人中人选4人，有C94种选法，由分步记数原理，共有C31C94=378种。（4）：（直接法）可分三类： 三人中只选一人，从其余9人中任选4人。有C31C94=378种。 三人中选二人，从其余9人中任选3人。有 C32C93=252种。 三人都选，从其余人中任选人。有C33C92=36种。由分类记数原理，共有378+252+36=666种不同选法。（间接法）：从12人中任选人，再减去A、B、C三人都不入选的情况。共有C125-C95=666种选法。（）（直接法） 三人都不入选，有C95=126种选法。 三人中选人，其余人中选人，有C31C94=378种选法。 三人中选人，其余人中选人，有C32C93=84种选法。由分类记数原理，共有16+378+84=756种选法。（间接法）：先从12人中任选人，再减去A、B、C三人都入选的情况。即C125-C92=756中选法。例：有10人，按照下列要求分组，求不同的分法种数。分成两组，一组人，一组人。分为甲、乙两组，一组人，一组人。分成甲、乙两组，每组人。两组，每组人。分析：从人中选人作为一组，其余人自为一组，有C106=210种。从人中选人作为一组，其余人自为一组，再分别作为甲乙组，共有C106A22420种。先从人中选人作为甲组，剩下人自为乙组，共有C105=252种方法。从人中选人作为一组，剩下人为另一组，由于两组人数相同，组与组之间没有顺序，所以，每种方法都重复了A22次，故有C105A22=126中方法。例：有个三好学生名额，分配给高三年纪个班，每班至少一个名额。有多少种不同的分配方案？分析：个班分这些名额，用个隔板，将个名额排成一排，名额之间有个空，将个隔板插入个空，每种插法对应一种分配方案。因此有C95=126种方案。答案：126种分配方案。例4：如图，从56方格中的顶点A到顶点B的最短线路有多少条？ 分析：从A到的最短路线均需走11步，（一步即为一个单位），即横向走6步，纵向走5步，因此要确定一种走法，只需确定这11步中哪6步是横向走即可，故不同的走法为C116=462种。答案：462种。 三、高考链接纵观全国高考数学试题，每年都有道排列组合题，考查排列组合的基础知识、思维能力。多数试题难度与课本中习题的难度相当，但也有个别试题难度较大，重点考查理解问题的能力、分析和解决问题的能力以及分类讨论的思想，有些试题以应用题的形式出现，考查解决实际问题的能力。例1：（2004年全国，理12）将4名教师分配到3所中学任教，每所中学至少1名教师，则不同的分配方案有（ ）A.12 种 B.24种 C.36种 D.48种分析：将4名教师分配到3所学校任教，每所学校至少一名，那么3所学校中只有一所学校分配到2名教师，其它两所学校只分配1名。所以完成这件事可分为两步，第一步从4名教师中任选两名；第二步把任选的两名教师看作一个整体，与剩下的2名教师进行全排列，即C42P33=36(种)。所以选C.例2：（2004年安春，理9）直角坐标系xOy平面上，平行直线x=n(n=0,1,2,5)与平行直线y=n(n=0,1,2,5)组成的图形中，矩形有（ ）。A.25个 B.36个 C.100个 D.225个分析：解决记数问题的关键