排列组合问题的基本模型及解题方法
导语:解决排列组合问题要讲究策略,首先要认真审题,弄清楚是排列(有序)还是组合(无序),还是排列与组合混合问题。其次,要抓住问题的本质特征,准确合理地利用两个基本原则进行“分类与分步”。加法原理的特征是分类解决问题,分类必须满足两个条件:①类与类必须互斥(不相容),②总类必须完备(不遗漏);乘法原理的特征是分步解决问题,分步必须做到步与步互相独立,互不干扰并确保连续性。分类与分步是解决排列组合问题的最基本的思想策略,在实际操作中往往是“步”与“类”交叉,有机结合,可以是类中有步,也可以是步中有类,以上解题思路分析,可以用顺口溜概括为:审明题意,排(组)分清;合理分类,用准加乘;周密思考,防漏防重;直接间接,思路可循;元素位置,特殊先行;一题多解,检验真伪。注意以下几点:
1、解排列组合应用题的一般步骤为:
①什么事:明确要完成的是一件什么事(审题);
②怎么做:分步还是分类,有序还是无序。
2、解排列组合问题的思路
(1)两种思路:直接法,间接法。
(2)两种途径:元素分析法,位置分析法。
3、基本模型及解题方法:
(一)、元素相邻问题
(1)、全相邻问题,捆邦法
例1、6名同学排成一排,其中甲,乙两人必须排在一起的不同排法有( C )种。
A、720 B、360 C、240 D、120
说明:从上述解法可以看出,所谓“捆邦法”,就是在解决对于某几个元素要求相邻问题时,可以整体考虑将相邻元素视作一个“大”元素。
(2)、全不相邻问题插空法
例2、要排一张有6个歌唱节目和4个舞蹈节目的演出节目单,任何两个舞蹈节目不得相邻,问有多少不同的排法,
解:先将6个歌唱节目排好,其中不同的排法有6!,这6个节目的空隙及两端共有七个位置中再排4个舞蹈节目有种排法,由乘法原理可知,任何两个舞蹈节目不得相邻的排法为种
例3、高三(一)班学要安排毕业晚会的4各音乐节目,2个舞蹈节目和1个曲艺节目的演出顺序,要求两个舞蹈节目不连排,则不同排法的种数是
A、1800 B、3600 C、4320 D、5040
解:不同排法的种数为=3600,故选B
说明:从解题过程可以看出,不相邻问题是指要求某些元素不能相邻,由其它元素将它隔开,此类问题可以先将其它元素排好,再将特殊元素插入,故叫插空法。
(3)、不全相邻排除法,排除处理
例4、五个人站成一排,其中甲、乙、丙三人有两人相邻,有多少排法?
解:
例5、有两排座位,前排11个座位,后排12个座位,现安排2人就座,规定前排中间的3个座位不能坐,并且这2人不左右相邻,那么不同排法的种数是
解法一: ①前后各一个,有8×12×2=192种方法
②前排左、右各一人:共有4×4×2=32种方法
③两人都在前排:两人都在前排左边的四个位置:
此种情况共有4+2=6种方法
因为两边都是4个位置,都坐右边亦有6种方法,所以坐在第一排总共有6+6=12种方法
④两人都坐在第二排位置,先规定甲左乙右
∴ 甲左乙右总共有种方法.同样甲、乙可互换位置,乙左甲右也同样有55种方法,所以甲、乙按要求同坐第二排总共有55×2=110种方法。综上所述,按要求两人不同排法有 192+32+12+110=346种
解法二:考虑20个位置中安排两个人就坐,并且这两人左右不相邻,4号座位与5号座位不算相邻(坐在前排相邻的情况有12种。),7号座位与8号座位不算相邻(坐在后排相邻的情况有22种。),共有种
(二)、定序问题缩倍法
例6、信号兵把红旗与白旗从上到下挂在旗杆上表示信号,现有3面红旗、2面白旗,把5面旗都挂上去,可表示不同信号的种数是( )(用数字作答)。
解:5面旗全排列有种挂,由于3面红旗与2面白旗的分别全排列均只能作一次的挂法,故有
说明:在排列的问题中限制某几个元素必须保持一定的顺序问题,这类问题用缩小倍数的方法求解比较方便.
例7、某工程队有6项工程需要单独完成,其中工程乙必须在工程甲完成后才能进行,工程丙必须在工程乙完成后才能进行,有工程丁必须在工程丙完成后立即进行。那么安排这6项工程的不同排法种数是 。
解一:依题意,只需将剩余两个工程插在由甲、乙、丙、丁四个工程形成的5个空中(插一个或二个),可得有=30种不同排法。
解二:=30
例8、由数字0、1、2、3、4、5组成没有重复数字的6位数,其中个位数字小于十位的数字的共有( )
A、210个 B、300个 C、464个 D、600个
解: 故选B
(三)、多元问题分类法
例9.某校从8名教师中选派4名教师同时去4个边远地区支教(每地1人),其中甲和乙不同去,甲和丙只能同去或同不去,则不同的选派方案共有 种
解析:某校从8名教师中选派4名教师同时去4个边远地区支教(每地1人),其中甲和乙不同去,甲和丙只能同去或同不去,可以分情况讨论,① 甲、丙同去,则乙不去,有=240种选法;②甲、丙同不去,乙去,有=240种选法;③甲、乙、丙都不去,有种选法,共有600种不同的选派方案.
例10、设集合。选择I的两个非空子集A和B,要使B中最小的数大于A中最大的数,则不同的选择方法共有 (B)
A、 B、 C、 D、
解析:若集合A、B中分别有一个元素,则选法种数有=10种;若集合A中有一个元素,集合B中有两个元素,则选法种数有=10种;若集合A中有一个元素,集合B中有三个元素,则选法种数有=5种;若集合A中有一个元素,集合B中有四个元素,则选法种数有=1种;若集合A中有两个元素,集合B中有一个元素,则选法种数有=10种;若集合A中有两个元素,集合B中有两个个元素,则选法种数有=5种;若集合A中有两个元素,集合B中有三个元素,则选法种数有=1种;若集合A中有三个元素,集合B中有一个元素,则选法种数有=5种;若集合A中有三个元素,集合B中有两个元素,则选法种数有=1种;若集合A中有四个元素,集合B中有一个元素,则选法种 数有=1种;总计有,选B.
解法二:集合A、B中没有相同的元素,且都不是空集,
从5个元素中选出2个元素,有=10种选法,小的给A集合,大的给B集合;
从5个元素中选出3个元素,有=10种选法,再分成1、2两组,较小元素的一组给A集合,较大元素的一组的给B集合,共有2×10=20种方法;
从5个元素中选出4个元素,有=5种选法,再分成1、3;2、2;3、1两组,较小元素的一组给A集合,较大元素的一组的给B集合,共有3×5=15种方法;
从5个元素中选出5个元素,有=1种选法,再分成1、4;2、3;3、2;4、1两组,较小元素的一组给A集合,较大元素的一组的给B集合,共有4×1=4种方法;
总计为10+20+15+4=49种方法。选B.
例11、将4个颜色互不相同的球全部放入编号为1和2的两个盒子里,使得放入每个盒子里的球的个数不小于该盒子的编号,则不同的放球方法有( )
A、10种 B、20种 C、36种 D、52种
解析:将4个颜色互不相同的球全部放入编号为1和2的两个盒子里,使得放入每个盒子里的球的个数不小于该盒子的编号,分情况讨论:①1号盒子中放1个球,其余3个放入2号盒子,有种方法;②1号盒子中放2个球,其余2个放入2号盒子,有种方法;则不同的放球方法有10种,选A.
说明:元素多,取出的情况也多种,可按要求分成互不相容的几类情况分别计算,最后总计。
(四)、元素交叉问题集合法(二元否定问题,依次分类)
例12、从6名运动员中选出4名参加4×100米接力赛,如果甲不跑第一棒,乙不跑第四棒,共有多少种不同的参赛方法?
解:设全集U={6人中任选4人参赛的排列},A={甲跑第一棒的排列},B={乙跑第四棒的排列},根据求集合元素的个数的公式可得参赛方法共有:card(U)-card(A)-card(B)+card(A∩B)=252
例13、某天的课表要排入语文、数学、英语、物理、化学、体育共六门课程,且上午安排
四节课,下午安排两节课。
(1)若第一节不排体育,下午第一节不排数学,一共有多少种不同的排课方法?
(2)要求数学、物理、化学不能排在一起(上午第四节与下午第一节不算连排),有多少种不同的排课方法?
例14、同室4人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送来的贺年卡,则四张贺年卡不同的分配方式有( )
A、6种 B、9种 C、11种 D、23种
解:此题可以看成是将数字1、2、3、4填入标号为1、2、3、4的四个方格里,每格填一数,且每个方格的标号与所填数字不同的填法问题。所以先将1填入2至4的3个方格里有3种填法;第二步把被填入方格的对应数字填入其它3个方格,又有3种填法;第三步将余下的两个数字填入余下的两格中只有一种填法,故共有3×3×1=9种填法。故选B
说明:求解二元否定问题先把某个元素按规定排入,再排另一个元素,如此继续下去,依此即可完成。
例15、安排5名歌手的演出顺序时,要求某名歌手不第一个出场,另一名歌手不最后一个出场,不同排法的总数是 .(用数字作答) 。(答:78种)
说明:某些排列组合问题几部分之间有交集,可用集合中求元素的个数的公式来求解。
(五)、多排问题单排法
例16、两排座位,第一排有3个座位,第二排有5个座位,若8名学生入座(每人一座位),则不同的座法为( )
A、 B、 C、 D、
解:此题分两排座可以看成是一排座,故有 种座法。∴选D
说明:把元素排成几排的问题,可归纳为一排考虑,再分段处理。
(六)、至多、至少问题分类法 或 间接法(去杂处理)
含“至多”或“至少”的排列组合问题,是需要分类问题,或排除法。排除法,适用于反面情况明确且易于计算的情况。
例17、从4名男生和3名女生中选出3人,分别从事三项不同的工作,若这3人中至少有1名女生,则选派方案共有 ( )