分球入箱问题的常规与特殊解法探究_电线常规解法

　　[摘要]从排列组合中分球入箱问题的最基本题型入手,从常规和特殊两个方面对其解法进行深入探究。 　　[关键词]分球入箱常规特殊 　　中图分类号:O29文献标识码:A文章编号:1671-7597(2009)1110003-01
　　
　　排列组合问题的求解要求具备较强的空间想象能力和对问题内涵的充分理解与认识,因此,从最基础的知识入手,从不同角度对基础问题的解法进行探究,往往能够归纳总结出相应的解题思路与方法,具有较强的理论与应用价值。在排列组合问题中,分球入箱问题对综合素质的要求较高,因此也容易使得这类问题成为难点的重要原因。本文将从最基础的分球入箱题型入手,对其常规与特殊解法进行探究。
　　例题:将n个相同的球放入m个不同的箱子中,如果不允许有空箱,有多少种不同的方法?若允许有空箱,有多少种不同的方法?
　　该例题是分球入箱问题中最为基础的问题,常规解法较为抽象,对于第一问,是将n个球排列成一排,再将箱子想象成m-1个隔板,由于箱子中不能存在空箱,因此隔板之间不能存在相邻的情况,即在n个球形成的n-1个空隙中,选取m-1个空隙,将各个隔板分别插入到这些空隙当中,因此得到的结果就是一共有 种方法。而第二问的常规解法更为抽象,原理同第一问相同,但是因为允许有空箱,因此隔板可以出现任意相邻的情况,此时可以将隔板与球等同看待,将二者组成的n+m-1个物体中再插入m-1个与第一文中相同、无法相邻的隔板,从而将其分开,得到的结果是共有 种方法。
　　可以看到,常规解法较为抽象,直观性不强。考虑到分球入箱问题是较为基础的题型,与其他很多种题型具有较强的共通之处,因此本文认为,可以将这类问题作相应的变形,转化为另外的问题加以研究。
　　方法举例一:题目转型为黑白球排列问题
　　这种方法的特点在于,将球和隔板分别看做是不同颜色的小球,各个颜色的小球之间不存在差异,这样,分球入箱问题就转化为了相对较为简单直观的黑白球排列问题。例题中的第一个问题就转化成为有n个白球和m-1个黑球,对这些小球的排列要求不能将黑球相邻排列,且黑球不能排在首末的位置,求其排法,原理与分球入箱的常规解法相同,是将黑球分别排列于n个白球之间的n-1个空隙中,因此排法的总数为 。而第二问就转化为将所有的黑球和白球任意排列的方法总数,而解法就更为直观,即可以想象有n+m-1个空格,将所有小球排列进去,不难发现,只要将白球或黑球先进行排列,则剩余颜色的球的排列方式就将是一定的,因此若先排列白球,则方法的数量为;先排列黑球则方法的数量为,有组合数的对偶原则可以看到,二者是相等的,该题得解。
　　方法举例二:隔板插入法的变形
　　常规解法中尽管使用了隔板插入法,但是在对第二问的求解过程当中,两次插入隔板,容易造成解题过程中思路的混乱与概念混淆,因此,将隔板插入法作一个简单的变形,将隔板编号,引入隔板插入的顺序就可以解决这个问题。
　　该方法对第一问的解法与常规解法大致相同,将m-1个隔板插入到n个小球形成的n-1个空隙当中,但是由于不能有空箱,因此,隔板之间必须有小球而不能相邻。从n-1个空隙中选取m-1个,按照不同的顺序进行摆放,可以看到有 种方法。
　　而对于问题的第二问,两次插入隔板的方法略微复杂,且其过程不够清楚,对于题目的理解和解法的原理难以准确把握,因此,可以将隔板看作是与小球相同的另外m-1个小球,但是要对这些小球进行标号,因为在该问题中,可以有空箱的存在,因此无论这m-1个小球如何摆放都是可以的。此时将第一个小球插入到原有小球中时,有n+1个空隙可供选择,相应的也就有n+1中插入的方法;将第一个小球插入之后,排列的小球数量变为n+1个,可供第二个小球插入的空隙相应增加到n+2个,以此类推,可以看到,编号的小球插入的方法总数为(n+1)×(n+2)×(n+3)×…×(n+m-1)中,此时应当注意,小球原先是没有编号的,因此对于小球安放的顺序带来的方法总数的增加应当被舍去,因此,实际上得到的方法
　　方法举例三:分类累加法的一般规律
　　在分球入箱中给出数字较为具体的例题当中,分类累加法的运用较多,因为通过这种方法能够直观准确的判断各种情况发生的可能与过程,从而对解决分球入箱问题的激励有一个准确的把握。在本文的例题当中,使用n和m两个未知数可以为这类问题提供分类累加法运用的一般规律,从而解决类似的所有问题。
　　首先来看第一问的解答方法,将所有的小球放置到盒子里并保证每个盒子都不空,如前文所述,得到的组合数为 个,由此可以类推,使得n个球在m-1个箱子里分布且保证箱子不空的方法数有 种。分类累加法的基本原理正是假设空箱子的个数。箱子的总数为m个,因此箱子最多只能有m-1个是空着的,因此,例题第二问的实质就是求当空箱子的个数分别为0,1,2,…,m-1的时候,也就意味着除了这些空箱子之外,其他的箱子保证不空的方法数的总和,为:
　　根据组合数的性质可以得到,求得的N就是 。
　　通过本文对分球入箱问题常规与特殊解法的探究可见,这类问题的基础性较强,可以通过很多不同的角度,与很多其他方面的知识相融合进而得到不同类型的解题思路与方法,并且这些方法的侧重点不同,适于针对不同类型的学生群体进行教学,并通过这些方法的学习与掌握,提高对排列组合相关知识的掌握程度。
　　
　　参考文献:
　　[1]夏春盛,例谈分球入箱问题的解法[J].中学生数学,2006(3).
　　[2]周勇俊,排列组合中分球入箱问题的几种解法[J].上海中学数学,2009(4).
　　
　　作者简介:
　　郁文梁(1981-),男,汉族,苏州人,本科,助教,研究方向:高职数学专业方面。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文