[“隔板模型”在排列组合中的应用技巧]排列组合中的隔板例题

  大家都知道,当今社会,数学在金融、经济、工程技术以及自然科学中有着广泛的应用,它的重要性已逐渐成为人们的共识。用数学方法解决实际问题,就是要求从实际错综复杂的关系中找出其内在联系和规律,然后用数学语言、图形语言、符号语言和公式把它表示出来。这种把实际问题进行简化并归结为数学问题进行求解的过程就是建立数学模型,简称“建模”。如有关方程的正整数解,非负整数解以及在线性规划中的有关整数解问题,排列组合中的“将相同的元素分配给不同的人”这样的问题,我们都可以通过建立“隔板模型”来解决这类问题。本文中,笔者主要就以下几个问题举例说明如下:
  题目:(1)现有10个优秀生名额拟分配给高三6个班,每班至少1个名额,试问共有多少种不同的分配方案。
  初做本题,有学生用如下方法来解这道题,解法如下:
  解:10个优秀生名额拟分配给高三6个班,每班至少1个名额,可以先给每个班1个名额,故要处理的问题是将余下的4个名额如何分给6个班,我们可以分给1个班,最多可以分给4个班。分给1个班,只要选班级即可;分给2个班,可先选班级,有种选法,再将4个名额分2份,有3种分法。依此类推,本题共有
  
  注:名额没有区别,属于相同的元素分配给不同的人的问题,故可建立“隔板模型”。
  解法如下:
  解:用一个“0 ”表示1个名额,将10个名额排列如下:
  0000000000
  这10个名额中间产生9个“空”,从这9个“空”中选出5个插入5块“隔板”,事先约定:第1块“隔板”前的名额分给1班,第1块“隔板”与第2块“隔板”之间的名额给2班,依此类推,第5块“隔板”后的名额给6班,比如在下图中,1班1个,2班2个,3班3个,4班1个,5班2个,6班1个。
  
  我们知道,从9个“空”任取5个插入5块“隔板”,共c =126有种方法,而每一种插法都对应着一种名额分配方案,所以一共有126种不同的分配方案。
  说明:(1)“事先约定”是必须的,没有事先约定,名额就无法分配。
  (2) “至少1个名额”是利用“隔板法”处理有关名额分配问题的特定情境。
  变题:
  ① 求方程x + y + z = 10的正整数解的组数。
  此题貌似与排列组合无关,但应用“隔板模型”该题即可转化为组合问题轻易解决。
  仔细想来,此题事实上与“10个名额分配给3个班,每班至少1个名额的问题”一回事。至此,可建立“隔板模型”。故本题有c =36组解。
  问题:若本题改为:求方程x + y + z = 10的非负整数解的组数。
  分析:此题事实上可以转化为“10个名额分配给3个班,允许部分班级没有名额”的问题。为此,我们先看下题:
  ②现有10个优秀生名额拟分配给高三6个班,如果允许部分班级没有名额,试问共有多少种不同的分配方案。
  分析:本题允许部分班级没有名额,要创设“隔板”情境,必须每班至少1个名额。为此,我们可以先给每个班1个“虚”的名额,这样,可以将原题转化为:“现有16个优秀生名额拟分配给高三6个班,每班至少1个名额,试问共有多少中不同的分配方案。”
  解:仿照上例,本题共有c =3003种不同的分配方案。比如在下图中,1班1个,2班没有,3班2个,4班3个,5班4个,6班没有。注:每个班都有1个“虚”的名额,应该去掉。
  0 0 | 0 | 0 0 0 | 0 0 0 0 | 0 0 0 0 0 | 0
  由此,方程x + y + z = 10的非负整数解的组数为c =66组。
  注:本题也可以另解如下:
  10个优秀生名额拟分配给高三6个班,如果允许部分班级没有名额,那么最少可以分配给1个班,最多可以分配给6个班,共有6种可能。若分给1个班,有c ×1种可能;若分给2个班,可先选班级,有c 种选法,再将10个名额分两份。此时再次创设“隔板情境”,利用“隔板模型”,故有c 种分法,这样有c ×c 种分配方法。依此类推,本题可列式如下:
  
  题目:(2)现有25个优秀生名额拟分配给高三6个班,每班至少3个名额,试问共有多少种不同的分配方案。
  要创设“隔板”情境,即每班至少1个名额。为此,可先给每班分配2个名额,原题即可转化为“现有13个优秀生名额拟分配给高三6个班,每班至少1个名额”的问题。从而本题有c =792种不同的分配方案。
  创设“隔板模型”的情境,即要求每个个体至少分配到1个元素,为此:
  (1)“事先约定”是必须的,没有事先约定,元素就无法分配。
  (2)“至少1个元素”是利用“隔板法”处理有关元素分配问题的特定情境。
  (3)一般的,n个元素分配到m(m≤n;m,n∈N )个个体,每个个体至少1个元素,共有c 种不同的分配方案。
  (4)一般的,n个元素分配到m(m≤n;m,n∈N )个个体,允许有的个体没有分配到元素,共有c 种不同的分配方案。
  
  注:“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文

推荐访问:隔板 应用技巧 模型 排列组合