刊名: 教育研究
Educational
Research
主办: 中国教育科学研究院
周期: 月刊
出版地:北京市
语种: 中文;
开本: 16开
ISSN: 1002-5731
CN: 11-1281/G4
邮发代号:
2-277
投稿邮箱:jyyj79@126.com
历史沿革:
现用刊名:教育研究
创刊时间:1979
该刊被以下数据库收录:
中国人文社会科学引文数据库(CHSSCD—2004)
核心期刊:
中文核心期刊(2008)
中文核心期刊(2004)
中文核心期刊(2000)
中文核心期刊(1996)
中文核心期刊(1992)
排列组合中的三类问题
【作者】 董新青
【机构】 河北省任丘市职教中心
【摘要】 排列、组合问题的背景丰富,情景陌生,题型多彩,变化万千,方法多样,似乎无特定的模式和规律可循,学生学习起来,大多无从下手,难度很大。本文从万千题型中,归纳总结出三类问题,这三类问题,虽远不能涵盖所有的排列组合问题,但掌握了它,通过“举一反三”,对于学好排列组合问题将大有裨益。【关键词】合并;取法数;模型
涂色问题
涂色问题是排列、组合问题中的一类,也是近年来高考的热点,下面就几例高考题浅谈一下这类题型的解法。
例1、将3种农作物种植在如下图的5块试验田里,每块种植一种农作物且相邻的试验田不能种植同一农作物,不同的种植方法共有多少种。
解: 第一步,根据题目要求,将5块试验田合并为3块,
有如下7种方法:
①(A、C)、(B、D)、E ②(A、C)、(B、E)、D ③ (A、D)、(B、E)、C
④ (A、D)、(C、E)、B ⑤ (A、E)、(B、D)、C ⑥ (B、D)、(C、E)、A
⑦ (A、C、E)、B、D
第二步,将3种农作物种在如上 “3块”试验田里,有A33种方法。
根据乘法原理,故不同的种植方法种数为:7A33=42
例2、某城市在中心广场建造一个花圃,花圃分为6个部分(如图)。现要栽种4种颜色的花,每部分栽种一种且相邻部分不能栽种同样颜色的花,不同的栽种方法有多少种。
解:第一步,根据题目要求,将6块地合并为4块,有如下5种方法:
① (2、4)、(3、5)、1、6
② (2、4)、(3、6)、1、5
③ (2、5)、(3、6)、1、4
④ (2、5)、(4、6)、1、3
⑤ (3、5)、(4、6)、1、2
第二步,将4种花种在如上“4块”地里,有A44种方法
根据乘法原理,不同的栽种方法种数为:5A44=120
例3、如图,一地区分为5个行政区域,现给地图着色,要求相邻区域不得使用同一颜色。现有4种颜色供选择,则不同的着色方法共有多少种.
解:本题有二类涂法。
第一类:用3种颜色涂。第一步,将5个区域合并为3个区域,只有一种方法:
(2、4)、(3、5)、1;
第二步选3种颜色,共有种方法;第三步涂色,3种颜色涂在3个区域,共有种方法;由乘法原理,不同的着色方法种数为:C43·A33=24
第二类:用4种颜色涂。第一步,将5个区域合并为4个区域,只有2种方法:
(2、4)、1、3、5 , (3、5)、1、2、4;第二步,用4种颜色为“4个区域”涂色,共有:种方法,由乘法原理,不同的涂色方法种数为:2=48
综上,涂法总数为:24+48=72
由上三例可知,求解涂色问题,先要根据题意,理清完成涂色任务至少需要几种颜色,然后按所需颜色种数进行分类。解每一类,根据题意把所有区域合并,其合并数为所用颜色数,然后进行涂色(排列),得出这一类的不同涂色种数。最后由加法原理得出涂法总数。
分组问题
分组问题是排列组合问题中较为重要的一个问题,它是解决某些分配问题的基础,要求学生必须掌握。
例1:6本不同的书
①平均分给甲、乙、丙三人,有多少不同的分法
②平均分成三堆,有多少不同的分法
③平均分成两堆,其中A,B两本在一堆
④平均分成三堆,其中A,B两本不在同一堆
⑤分成一堆3本,一堆2本,一堆一本,有多少不同的分法
⑥分成一堆4本,一堆1本,一堆1本,有多少不同的分法
⑦分成一堆2本,一堆2本,一堆1本,一堆一本,有多少不同的分法
①解:第一步,从6本不同的书中任取2本给甲,有C62种取法;第二步,从剩余的4本书中任取2本给乙,有C42种取法;第三步,剩余的2本给丙,只有一种取C22法。故不同的取法总数为C62C42C22=90种(这样的数C62C42C22权且称为取法数)。
②解:将6本不同的书平均分成3堆,设有种方法。问题①可以分为两步来完成,第一步:将6本不同的书平均分成3堆,共有种方法;第二步:将这3堆书分给甲、乙、丙3个人,共有A33种不同方法。则由乘法原理得:C62C42C22=xA33;因此,x=■=15种,即:将6本不同的书平均分成3堆,共有■种方法
③解:第一步:从A,B以外的4本书中任取1本和A,B两本构成一堆,有C41种方法;第二步:其余3本构成一堆,有C33种方法;故不同的分法总数为:C33C41=4种
④解:第一步:从A,B以外的4本数中任取1本与A为一堆,有C41种方法;第二步:从剩余的三本中任取1本与B为一堆,有C31种方法;第三步剩余的2本为一堆,有C22种方法;故不同的分法总数为:C41C31C22=12种
⑤ 解:第一步,从6本不同的书中任取3本为一堆,共有C63种取法;第二步,从剩余的3本中任取2本为一堆,共有C32种取法;第三步,剩余的1本为一堆,只有一种取法C11;因此不同的取法总数为:C63C32C11=60种
由上5小题,我们可以归纳出分组问题有如下规律(假设分n个小组或堆):
⑴如果每个小组元素数量相同,则分组数=■,如例②;
⑵如果每个小组元素数量各不相同,则不除Ann(n的阶乘)如:例⑤;
⑶有“几”个小组元素数量相同,就除以“几”的阶乘、如:例⑥、⑦;
⑷如果小组有特殊元素,求分组数要慎重,一般不除Ann,如:例③、④
⑥解: 因为有2堆数量是相同的,根据上述规律,不同的分法种数为■=15
⑦解: 因为各有2堆数量是相同的,根据上述规律,不同的分法种数为:■=45种
例2、4个不同的小球,放入编号为1、2、3、4的4个盒子里,恰有一个空盒的放法共有多少种
解:依题意,4个不同的小球放入3个盒子里,必有一个盒子有2球,其余2个盒子各一球。第一步,4个小球分为3组,共有■种方法,第二步,从4个盒子中取3个,共有种方法;第三步,3组小球放入3个盒子里,共有种放法。因而不同的放法总数为:C43■A33=144种
例3、6本不同的书分给4个人,每人至少一本,共有多少不同的分法
解:依题意,有两类分法,一类为:一人2本,一人2本,一人1本,一人1本;一类为:一人3本,其余3人各1本。
第一类:第一步,将6本书按上述要求分成4组,共有■种方法;第二步,将4组书分给4个人,共有A44种方法。故不同的分法种数为:■A44=1080种
第二类:第一步,将6本书按上述要求分成4组,共有■种分法;第二步,将4组书分给4个人,共有种分法。故不同的分法种数为■=480种
综上,不同的分法总数为:1080+480=1560种
解决分配问题的原则是:先分组后分配(排列),因而,掌握分组的规律至关重要。
相同元素的分配问题——隔板法
排列、组合针对的是不同元素的分配问题,因而,有些相同元素的分配问题不能直接利用排列、组合求解。它的解法比较特殊,需要我们建立合适的数学模型。下面就几个具体实例说明这类题型的解法。
例1、12个相同的小球放入编号为1、2、3、4的4个盒子里:
①每个盒子至少一个小球的不同放法有多少种
②如果允许每盒可空,那么不同的放法有多少种
③如果要求每个盒子中的小球数不小于其编号数,则不同的放法有多少种
解:① 将这12个小球排成一排,则其中间产生11个空档;利用3个隔板放入小球之间,可将小球方分成4部分。因而,从11个空档中选出3个来放隔板,不同的放法,对应不同的分法。故分法种数为:C113=165种。
②因为每盒可空,所以隔板之间允许无球,插入法不再适应。现建立如下数学模型:将3个隔板(把球分成4部分,需3隔板)和12个球排成一排,共需15个位置,从这15个位置中任取3个放隔板(当然,其余位置放小球),不同的放法,对应不同的分法。(例:一排排列如图000—00000——0000,则1盒放3个,2盒放5个,3盒放0个,4盒放4个)因而,小球不同的放法种数为:C153=455种。
③ 解法一:用①的处理方法。
首先,4个盒子里分别放入0个、1个、2个、3个小球,则剩余6个小球,它们之间产生5个空档。然后,利用插入法,从5个空档中取3个放隔板,则共有不同的分法:C53=10种
解法二:用②的处理方法。
首先,每个盒子里放入与其编号数相同的小球,用去10个小球,还剩2个小球,此时允许每个盒子可空。2个小球与3个隔板排成一排,共需5个位置。然后,从5个位置中任取3个放隔板,则不同的分法共有:C53=10种。
例2、某校高二有7个班,从中选择10人参加数学竞赛:
①每班至少一人,共有多少不同的选法
②如果允许有的班无人参赛,共有多少不同的选法
解: 参赛的10人,在此题中为10个名额,它们是相同的元素。因而,需用隔板法来处理。
① 10个名额之间产生9个空档,从中任取6个放隔板,可将10个名额分成7部分。则不同的选法数共有:C96=C93=84种
②10个名额和6个隔板(把10个名额分成7部分只需6个隔板)排成一排,共占用16个位置,从中任取6个位置放隔板,则不同的选法数共有:C166种
参考书目:
[1]《轻巧夺冠》,主编:刘强
[2]《状元之路》,主编:高峰