第6讲 排列组合的综合应用.doc

第六讲 排列组合的综合应用
　　排列组合是数学中风格独特的一部分内容.它具有广泛的实际应用.例如：某城市电话号码是由六位数字组成，每位可从0～9中任取一个，问该城市最多可有多少种不同的电话号码？又如从20名运动员中挑选6人组成一个代表队参加国际比赛.但运动员甲和乙两人中至少有一人必须参加代表队，问共有多少种选法？回答上述问题若不采用排列组合的方法，结论是难以想像的.（前一个问题，该城市最多可有1000000个不同电话号码.后一个问题，代表队有20196种不同选法.）
　　当然排列组合的综合应用具有一定难度.突破难点的关键：首先必须准确、透彻的理解加法原理、乘法原理；即排列组合的基石.其次注意两点：①对问题的分析、考虑是否能归纳为排列、组合问题？若能，再判断是属于排列问题还是组合问题？②对题目所给的条件限制要作仔细推敲认真分析.有时利用图示法，可使问题简化便于正确理解与把握.
例1 从5幅国画，3幅油画，2幅水彩画中选取两幅不同类型的画布置教室，问有几种选法？
分析 首先考虑从国画、油画、水彩画这三种画中选取两幅不同类型的画有三种情况，即可分三类，自然考虑到加法原理.当从国画、油画各选一幅有多少种选法时，利用的乘法原理.由此可知这是一道利用两个原理的综合题.关键是正确把握原理.
解： 符合要求的选法可分三类：
　　不妨设第一类为：国画、油画各一幅，可以想像成，第一步先在5张国画中选1张，第二步再在3张油画中选1张.由乘法原理有 5×3＝15种选法.第二类为国画、水彩画各一幅，由乘法原理有 5×2＝10种选法.第三类油画、水彩各一幅，由乘法原理有3×2＝6种选法.这三类是各自独立发生互不相干进行的.
　　因此，依加法原理，选取两幅不同类型的画布置教室的选法有 15＋10＋ 6＝31种.
　　注 运用两个基本原理时要注意：
　　①抓住两个基本原理的区别，千万不能混.
　　不同类的方法（其中每一个方法都能各自独立地把事情从头到尾做完）数之间做加法，可求得完成事情的不同方法总数.
　　不同步的方法（全程分成几个阶段（步），其中每一个方法都只能完成这件事的一个阶段）数之间做乘法，可求得完成整个事情的不同方法总数.
　　②在研究完成一件工作的不同方法数时，要遵循“不重不漏”的原则.请看一些例：从若干件产品中抽出几件产品来检验，如果把抽出的产品中至多有2件次品的抽法仅仅分为两类：第一类抽出的产品中有2件次品，第二类抽出的产品中有1件次品，那么这样的分类显然漏掉了抽出的产品中无次品的情况.又如：把能被2、被3、或被6整除的数分为三类：第一类为能被2整除的数，第二类为能被3整除的数，第三类为能被6整除的数.这三类数互有重复部分.
　　③在运用乘法原理时，要注意当每个步骤都做完时，这件事也必须完成，而且前面一个步骤中的每一种方法，对于下个步骤不同的方法来说是一样的.
例2 一学生把一个一元硬币连续掷三次，试列出各种可能的排列.
分析 要不重不漏地写出所有排列，利用树形图是一种直观方法.为了方便，树形图常画成倒挂形式.
解：

　　由此可知，排列共有如下八种：
　　正正正、正正反、正反正、正反反、
　　反正正、反正反、反反正、反反反.
例3 用0～9这十个数字可组成多少个无重复数字的四位数.
分析 此题属于有条件限制的排列问题，首先弄清楚限制条件表现为：①某位置上不能排某元素.②某元素只能排在某位置上.分析无重复数字的四位数的千位、百位、十位、个位的限制条件：千位上不能排0，或说千位上只能排1～9这九个数字中的一个.而且其他位置上数码都不相同，下面分别介绍三种解法.
　　解法1：分析 某位置上不能排某元素.分步完成：第一步选元素占据特殊位置，第二步选元素占据其余位置.
解： 分两步完成：
　　第一步：从1～9这九个数中任选一个占据千位，有9种方法.
　　第二步：从余下的9个数（包括数字0）中任选3个占据百位、十位、个位，百位有9种.十位有8种，个位有7种方法.
　　由乘法原理，共有满足条件的四位数9×9×8×7=4536个.
　　答：可组成4536个无重复数字的四位数.
　　解法2：分析 对于某元素只能占据某位置的排列可分步完成：第一步让特殊元素先占位，第二步让其余元素占位.在所给元素中0是有位置限制的特殊元素，在组成的四位数中，有一类根本无0元素，另一类含有0元素，而此时0元素只能占据百、十、个三个位置之一.
解： 组成的四位数分为两类：
　　第一类：不含0的四位数有9×8×7×6=3024个.
　　第二类：含0的四位数的组成分为两步：第一步让0占一个位有3种占法，（让0占位只能在百、十、个位上，所以有3种）第二步让其余9个数占位有9×8×7种占法.所以含0的四位数有3×9×8×7=1512个.
　　∴由加法原理，共有满足条件的四位数
　　3024+1512=4536个.
　　解法3：从无条件限制的排列总数中减去不合要求的排列数（称为排除法）.此题中不合要求的排列即为0占据千位的排列.
解： 从0～9十个数中任取4个数的排列总数为10×9×8×7，其中0在千位的排列数有9×8×7个（0确定在千位，百、十、个只能从9个数中取不同的3个）
　　∴共有满足条件的四位数
　　10×9×8×7-9×8×7
　　=9×8×7×（10-1）
　　=4536个.
　　注 用解法3时要特别注意不合要求的排列有哪几种？要做到不重不漏.
例4 从右图中11个交点中任取3个点，可画出多少个三角形？

　　分析首先，构成三角形与三个点的顺序无关因此是组合问题，另外考虑特殊点的情况：如三点在一条直线上，则此三点不能构成三角形，四点在一条直线上，则其中任意三点也不能构成三角形.此题采用排除法较方便.
　　解：组合总数为C311，
　　其中三点共线不能构成的三角形有7C33，
　　四点共线不能构成的三角形有2C34，
　　∴C311-（7C33+2C34）=165-（7+8）=150个.
例5 7个相同的球，放入4个不同的盒子里，每个盒子至少放一个，不同的放法有多少种？（请注意，球无区别，盒是有区别的，且不允许空盒）
分析 首先研究把7分成4个自然数之和的形式，容易得到以下三种情况：
　　①7=1+1+1+4
　　②7=1+2+2+2
　　③7=1+1+2+3
　　其次，将三种情况视为三类计算不同的放法.第一类：有一个盒子里放了4个球，而其余盒子里各放1个球，由于4个球可任意放入不同的四个盒子之一，有4种放法，而其他盒子只放一个球，而球是相同的，任意调换都是相同的放法，所以第一类只有4种放法.
　　第二类：有一个盒子里放1个球，有4种放法，其余盒子里都放2个球，与第一类相同，任意调换都是相同的放法，所以第二类也只有4种放法.
　　第三类：有两个盒子里各放一个球，另外两个盒子里分别放2个及3个球，这时分两步来考虑：第一步，从4个盒子中任取两个各放一个球，这种取法有C24种.
　　第二步，把余下的两个盒子里分别放入2个球及3个球，这种放法有P22种.由乘法原理有C24×P22=12种放法.
　　∴由加法原理，可得符合题目要求的不同放法有
　　4+4+12=20（种）
　　答：共有20种不同的放法.
　　注 本题也可以看成每盒中先放了一个球垫底，使盒不空，剩下3个球，放入4个有区别盒的放置方式数.
例6 用红、橙、黄、绿、蓝、青、紫七种颜色中的一种，或两种，或三种，或四种，分别涂在正四面体各个面上，一个面不能用两色，也无一个面不涂色的，问共有几种不同涂色方式？
分析 首先介绍正四面体（模型）.正四面体四个面的相关位置，当底面确定后，（从上面俯视）三个侧面的顺序有顺时针和逆时针两种（当三个侧面的颜色只有一种或两种时，顺时针和逆时针的颜色分布是相同的）.

　　先看简单情况，如取定四种颜色涂于四个面上，有两种方法；如取定一种颜色涂于四个面上，只有一种方法.但取定三种颜色如红、橙、黄三色，涂于四个面上有六种方法，如下图①②③（图中用数字1，2，3分别表示红、橙、黄三色）

　　如果取定两种颜色如红、橙二色，涂于四个面上有三种方法.如下图④⑤⑥

　　但是从七种颜色里，每次取出四种颜色，有C47种取法，每次取出三种颜色有C37种取法，每次取出两种颜色有C27种取法，每次取出一种颜色有C17种取法.
　　因此着色法共有2C47+6C37+3C27+C17=350种.
习题六
　　1.有3封不同的信，投入4个邮筒，一共有多少种不同的投法？
　　2.甲、乙两人打乒乓球，谁先连胜头两局，则谁赢.如果没有人连胜头两局，则谁先胜三局谁赢，打到决出输赢为止，问有多少种可能情况？
　　3.在6名女同学，5名男同学中，选4名女同学，3名男同学，男女相间站成一排，问共有多少种排法？
　　4.用0、1、2、3、4、5、6这七个数字可组成多少个比300000大的无重复数字的六位偶数？
　　5.如右图：在摆成棋盘眼形的20个点中，选不在同一直线上的三点作出以它们为顶点的三角形，问总共能作多少个三角形？

　　6.有十张币值分别为1分、2分、5分、1角、2角、5角、1元、2元、5元、10元的人民币，能组成多少种不同的币值？并请研究是否可组成最小币值1分与最大币值（总和）之间的所有可能的币值.
习题六解答
　　1.若投一封信看作一个步骤，则完成投信的任务可分三步，每封信4个邮筒都可投，即每个步骤都有4种方法.故由乘法原理：共有不同的投法4×4×4=64种.
　　2.甲（或乙）胜就写一个甲（或乙）字，
　　画树形图：

　　由图可见共有14种可能.
　　甲甲、甲乙甲甲、甲乙甲乙甲、甲乙甲乙乙、甲乙乙甲甲、甲乙乙甲乙、甲乙乙乙、乙甲甲甲、乙甲甲乙甲、乙甲甲乙乙、乙甲乙甲甲、乙甲乙甲乙、乙甲乙乙、乙乙.
　　3.现有4名女同学，3名男同学，男女相间站成一排，则站在两端的都是女同学.将位置从右到左编号，第1、3、5、7号位是女同学，第2、4、6号位是男同学.于是完成适合题意的排列可分两步：
　　第一步：从6名女同学中任选4名排在第1、3、5、7号位.有P46种排法.
　　第二步：从5名男同学中任选3名排在第2、4、6号位，有P35种排法.
　　因此，由乘法原理排出不同队形数为
　　P46·P35=6×5×4×3×5×4×3=21600.
　　4.图示：

　　分两类：
　　第一类：十万位上是3或5之一的六位偶数有
　　P12·P14·P45个.
　　第二类：十万位上是4或6之一的六位偶数有
　　P12·P13·P45个.
　　∴P12P14P45+P12P13P45=1680.
　　5.五点共线有4组，四点共线的有9组，三点共线的有8组，利用排除法：
　　C320-4C35-9C34-8C33
　　=1140-4×10-9×4-8
　　=1056.
　　6.因为任一张人民币的币值都大于所有币值比它小的人民币的币值的和，例如1角的大于1分、2分、5分的和，因此不论取多少张，它们组成的币值都不重复，所以组成的币值与组合总数一致，有
　　C110+C210+……+C1010=210-1=1023种.
　　因为由这些人民币能组成的最小的币值是1分，最大的币值是十张币值的和，即1888分，而1023＜1888，可见从1分到1888分中间有一些币值不能组成.