小球入盒模型的推广应用
小球入盒是排列组合的典型问题,与之相关的有名额分配、人员分配等问题,形式多样.“小球入盒问题”问题可以分为四类:不同的小球放入不同的盒子里;不同的小球放入相同的盒子里;相同的小球放入不同的盒子里;相同的小球放入相同的盒子里(此类不做重点讨论)。
解答小球入盒问题的最有效、最易于操作的方法是“先分组后分配”,即先将元素分组、再分配到位置.分组时应注意平均分组与非平均分组的区别;放入相同盒子可看作分组无分配问题;解答相同小球入不同盒子问题的最有效、最易于操作的方法是隔板法。
【引例】
①把4个相同的小球放入3个相同的盒子,共有多少种不同的放法
②把4个不同的小球放入3个不同的盒子,共有多少种不同的放法
③把4个不同的小球放入3个相同的盒子,共有多少种不同的放法
④把4个相同的小球放入3个不同的盒子,共有多少种不同的放法
【解析】①由于小球相同,盒子也相同,故小球数目的不同分组就对应不同的放法,小球数目分组有4+0+0型、3+1+0型、2+2+0型、2+1+1型,故只有4种放法.
②(乘法原理)分4步,把小球一个一个地放入盒子,每一个小球都有3种放法,由乘法原理,共有 种放法.
③(先分组后分配)先将不同小球分为三组,有4+0+0型(种方法)、3+1+0型(种方法)、2+2+0型(种方法)、2+1+1型(种方法),共14 种分组方法,再将三组小球分配到三个盒子,由于盒子相同,故都只有1种方案,故共有14 种放法.
④法1:(先分组后分配)先将小球分为三组,有4+0+0型、3+1+0型、2+2+0型、2+1+1型,由于小球相同,故各只有1种分组方法;再将三组小球分配到三个盒子,由于盒子不同,故有 种放法.
法2:(隔板法)每种放法对应于将4个相同小球与2个相同“隔板”进行的一次排列,即从6个位置中选2个位置安排隔板,故共有 =15种放入的方式。
一. n个相同的小球放入m个不同的盒子模型
在排列组合中,对于将不可分辨的球装入到可以分辨的盒子中而求装入方法数的问题,常用隔板法。
模型1 将n个相同的小球放入编号分别为1,2,3,4,…,m的m个盒子中(m≤n),每个盒子中至少有一个小球的不同放法总数为。
【解析】n个相同小球串成一串从n-1个间隙里选m-1个结点剪成m段(或者看作插入m-1块隔板),有种方法.
模型2 将n个相同的小球放入编号分别为1,2,3,4,…,m的m个盒子中(m≤n),每个盒子可空的放法总数为。章子怡多大
【解析】任意分组,可出现某些组含元素为0个时,其不同分组方式为:m个盒子排成一行,
中间有m-1块隔板,把n个球放入m个盒子,不同的放法对应着n个球和m-1块隔板的不同排列,于是在n+m-1个位置中选m-1个位置安排隔板,所以放法总数为。
模型3 将n个相同的小球放入编号分别为1,2,3,4,…,m的m个盒子中(m≤n),要求每个盒子中的球数不少于它的编号数的放法总数为。
【解析】法1:先在编号1,2,3,4,…,m的m个盒子内分别放0,1,2,3,4,…,m-1个球,剩下个球分成m组,每组至少1个,由模型1方法知有(种)方法。
法2:第一步先在编号1,2,3,4,…,m的m个盒子内分别放1,2,3,4,…,m个球,剩下个球放入m个盒子,不同的放法对应着个球和m-1块隔板的不同排列,于是在个位置中选m-1个位置安排隔板,有(种)方法。
隔板法:将放有小球的盒子紧挨着成一行放置,便可看作成一行的小球的空隙中插入了若干隔板,相邻两块隔板形成一个“盒”.每一种插入隔板的方法对应着小球放人盒子的一种方法,此法称为隔板法.隔板法专门解决相同元素的分配问题.
应用1(求不定方程整数解)
1.不定方程的正整数解的个数为。
【解析】可看作n个相同的小球放入m个不同盒子中,要求每个盒子不空时球的放法数,于是将n个小球排成一行,它们形成n-1个空挡,只插m-1个隔板,故有种方法。
2.不定方程的非负正整数解的个数为。
【解析】可看作n个相同的小球放入m个不同盒子中,要求每个盒子可空时球的放法数,由模型2知非负正整数解的个数为。
应用2(多项式定理中展开式项数问题)
3.三项式展开式共有多少不同的项
【解析】 的展开式中每一项的指数和均是 n,相当于 n个无区别的球放入 、 、 三个不同的盒子里,每个盒放入的球数不限,由模型2知为展开式中共有不同的项数为。
应用3(名额分配问题)
4.将10个优秀的指标分配给3个班级,
(1)每班至少一个,则共有多少种分配方法
(2)任意分配共有多少种分配方法
(3)若班级为一、二、三班,若名额数不小于班级数,则共多少种分配方法
【解析】:由于10个优秀指标是相同的,该题等价于10个相同的小球放入3个不同盒子模型。可采用“隔板法”。
(1)插隔板,即9个空格中插入2个隔板,共有种分配方法。
(2)排隔板,即10个指标和2个隔板,共12个位置选2个放隔板,共有种分配方法。
(3)先给一班0个优秀名额,二班1个优秀名额,三班2个优秀名额,再对剩下的7个优秀名额用插隔板法,共有种分配方法。
总之,凡是处理与“相同元素有序分组”模型时,我们都可采用“隔板法”。若每组元素数目至少一个时,可用插“隔板”,若出现每组元素数目为0个时,可用排“隔板”。
二.n个不同的小球放入m个不同的盒子模型
模型4. 把n个不同的小球放入m个不同的盒子,有多少种不同放法
【解析】每个小球有m种放法,共有种放法。
模型5. 把n个不同的小球放入m个不同的盒子,每盒放球不超过1个,直至球放完或盒子放满为止,有多少种不同放法
【解析】(1)若n>m,将n个小球当做n个元素,这样问题实质即在n个元素中取m个元素的排列问题,有种。
(2)若n<m,将m个小盒当做m个不同元素,这样问题实质即在m个元素中取n个元素的排列问题,有种。
(3)若n=m, 有 ==n!
模型6. 在n个不同的小球中取m个放入m个不同的盒子中,每盒只放一个,其中某一个小球必须放在某一个指定的盒子中,有多少种不同的放法
发布评论