中国学术文献网络出版总库

刊名: 教育研究
       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种方法:

  ①(AC)、(BD)E     ②(AC)、(BE)D      (AD)(BE)

  ④ (AD)(CE)B       (AE)(BD)C     (BD)(CE)A  

  ⑦ (ACE)BD

  第二步,将3种农作物种在如上 “3块”试验田里,有A33种方法。

  根据乘法原理,故不同的种植方法种数为:7A33=42

  例2、某城市在中心广场建造一个花圃,花圃分为6个部分(如图)。现要栽种4种颜色的花,每部分栽种一种且相邻部分不能栽种同样颜色的花,不同的栽种方法有多少种。

  解:第一步,根据题目要求,将6块地合并为4块,有如下5种方法:

  ① (24)、(35)、16

  ② (24)、(36)、15

  ③ (25)、(36)、14

  ④ (25)、(46)、13

  ⑤ (35)、(46)、12

  第二步,将4种花种在如上“4块”地里,有A44种方法

  根据乘法原理,不同的栽种方法种数为:5A44=120

  例3、如图,一地区分为5个行政区域,现给地图着色,要求相邻区域不得使用同一颜色。现有4种颜色供选择,则不同的着色方法共有多少种.

  解:本题有二类涂法。

  第一类:用3种颜色涂。第一步,将5个区域合并为3个区域,只有一种方法:

  (24)、(35)、1

 

 

 

 

 

  第二步选3种颜色,共有种方法;第三步涂色,3种颜色涂在3个区域,共有种方法;由乘法原理,不同的着色方法种数为:C43·A33=24

  第二类:用4种颜色涂。第一步,将5个区域合并为4个区域,只有2种方法:

  (24)、13, (35)、124;第二步,用4种颜色为“4个区域”涂色,共有:种方法,由乘法原理,不同的涂色方法种数为:2=48

  综上,涂法总数为:24+48=72

  由上三例可知,求解涂色问题,先要根据题意,理清完成涂色任务至少需要几种颜色,然后按所需颜色种数进行分类。解每一类,根据题意把所有区域合并,其合并数为所用颜色数,然后进行涂色(排列),得出这一类的不同涂色种数。最后由加法原理得出涂法总数。

  分组问题

  分组问题是排列组合问题中较为重要的一个问题,它是解决某些分配问题的基础,要求学生必须掌握。

  例16本不同的书

  ①平均分给甲、乙、丙三人,有多少不同的分法

  ②平均分成三堆,有多少不同的分法

  ③平均分成两堆,其中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个小组或堆):

  ⑴如果每个小组元素数量相同,则分组数=■,如例②;

  ⑵如果每个小组元素数量各不相同,则不除Annn的阶乘)如:例⑤;

  ⑶有“几”个小组元素数量相同,就除以“几”的阶乘、如:例⑥、⑦;

  ⑷如果小组有特殊元素,求分组数要慎重,一般不除Ann,如:例③、④

  ⑥解: 因为有2堆数量是相同的,根据上述规律,不同的分法种数为■=15

  ⑦解: 因为各有2堆数量是相同的,根据上述规律,不同的分法种数为:■=45

  例24个不同的小球,放入编号为12344个盒子里,恰有一个空盒的放法共有多少种

  解:依题意,4个不同的小球放入3个盒子里,必有一个盒子有2球,其余2个盒子各一球。第一步,4个小球分为3组,共有■种方法,第二步,从4个盒子中取3个,共有种方法;第三步,3组小球放入3个盒子里,共有种放法。因而不同的放法总数为:C43A33=144

  例36本不同的书分给4个人,每人至少一本,共有多少不同的分法

  解:依题意,有两类分法,一类为:一人2本,一人2本,一人1本,一人1本;一类为:一人3本,其余3人各1本。

  第一类:第一步,将6本书按上述要求分成4组,共有■种方法;第二步,将4组书分给4个人,共有A44种方法。故不同的分法种数为:■A44=1080

  第二类:第一步,将6本书按上述要求分成4组,共有■种分法;第二步,将4组书分给4个人,共有种分法。故不同的分法种数为■=480

  综上,不同的分法总数为:1080+480=1560

  解决分配问题的原则是:先分组后分配(排列),因而,掌握分组的规律至关重要。

  相同元素的分配问题——隔板法

  排列、组合针对的是不同元素的分配问题,因而,有些相同元素的分配问题不能直接利用排列、组合求解。它的解法比较特殊,需要我们建立合适的数学模型。下面就几个具体实例说明这类题型的解法。

  例112个相同的小球放入编号为12344个盒子里:

  ①每个盒子至少一个小球的不同放法有多少种

  ②如果允许每盒可空,那么不同的放法有多少种

  ③如果要求每个盒子中的小球数不小于其编号数,则不同的放法有多少种

  解:① 将这12个小球排成一排,则其中间产生11个空档;利用3个隔板放入小球之间,可将小球方分成4部分。因而,从11个空档中选出3个来放隔板,不同的放法,对应不同的分法。故分法种数为:C113=165种。

  ②因为每盒可空,所以隔板之间允许无球,插入法不再适应。现建立如下数学模型:将3个隔板(把球分成4部分,需3隔板)和12个球排成一排,共需15个位置,从这15个位置中任取3个放隔板(当然,其余位置放小球),不同的放法,对应不同的分法。(例:一排排列如图00000000——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]《状元之路》,主编:高峰