排列组合：小球入盒.doc

_小球入盒模型的推广应用摘 要：小球入盒是排列组合的典型问题，本文从小球同与不同及盒子同与不同几方面对小球入盒模型的加以推广应用。小球入盒是排列组合的典型问题，与之相关的有名额分配、人员分配等问题，形式多样.“小球入盒问题”问题可以分为四类：不同的小球放入不同的盒子里；不同的小球放入相同的盒子里；相同的小球放入不同的盒子里；相同的小球放入相同的盒子里（此类不做重点讨论）。解答小球入盒问题的最有效、最易于操作的方法是“先分组后分配”，即先将元素分组、再分配到位置.分组时应注意平均分组与非平均分组的区别；放入相同盒子可看作分组无分配问题；解答相同小球入不同盒子问题的最有效、最易于操作的方法是隔板法。【引例】把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个盒子中(mn)，每个盒子中至少有一个小球的不同放法总数为。【解析】n个相同小球串成一串从n-1个间隙里选m-1个结点剪成m段（或者看作插入m1块隔板），有种方法.模型2 将n个相同的小球放入编号分别为1，2，3，4,m的m个盒子中(mn)，每个盒子可空的放法总数为。【解析】任意分组，可出现某些组含元素为0个时，其不同分组方式为：m个盒子排成一行，中间有m-1块隔板，把n个球放入m个盒子，不同的放法对应着n个球和m-1块隔板的不同排列，于是在n+m-1个位置中选m-1个位置安排隔板，所以放法总数为。 模型3 将n个相同的小球放入编号分别为1，2，3，4,m的m个盒子中(mn)，要求每个盒子中的球数不少于它的编号数的放法总数为。【解析】法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）若nm,将n个小球当做n个元素，这样问题实质即在n个元素中取m个元素的排列问题，有种。（2）若nm,将m个小盒当做m个不同元素，这样问题实质即在m个元素中取n个元素的排列问题，有种。（3）若n=m, 有 =n!模型6. 在n个不同的小球中取m个放入m个不同的盒子中，每盒只放一个，其中某一个小球必须放在某一个指定的盒子中，有多少种不同的放法？【解析】先将某一个小球放在指定的盒子中，然后从剩下的n-1个不同的小球中任取m-1个，放入m-1个不同的小盒中，共有种放法。模型7 在n个不同的小球中取m个放入m个不同的盒子中(mn)，每盒只放一个，其中某一个小球不能放在某一个指定的盒子中，有多少种不同的放法？【解析】第一类：某一小球没有取到，则从n-1个小球中取出m个小球放入m个盒子中，共有种；第二类：某一小球被取到，它只能被放到指定小盒以外的m-1个盒子中。第一步放指定小球有m-1种，第二步从n-1个小球中取m-1个放入剩下的m-1个盒子中，有种，所以有种。综上共 +种放法。应用4. （1） 5本不同的书全部送给6人，每人至多1本，有多少种不同的送书方法？（2）6本不同的书送给5人，每人至多1本，有多少种不同的送书方法？（3）6本不同的书送给5人，每人至少1本，有多少种不同的送书方法？（4）6本不同的书送给5人，每人1本，且其中一本麻将技巧不能送给小学生章子怡，则有多少种不同的送书方法？【解析】（1）相当于5个不同小球放入6个不同的盒子中，每盒至多一球，所以有种不同送书方法。（2）相当于6个不同小球放入5个不同的盒子中，每盒至多一球，所以有种不同送书方法。（3）第一步先将6本书分成5堆，其中一堆2本书，有种方法，第二步把5堆书分给5个人，有种方法，所以共有1800种不同送书方法.（4）第一类：麻将技巧没送出，有种方法；第二类：麻将技巧送给章子怡以外的4人中某一人，有4种方法；然后从剩下的5本书中取4本送另外4个人，有种方法,所以有480种方法；综上，知有120+480=600种方法.应用5. 四位选手争夺三个运动项目的金牌，则有多少不同的金牌结果种数？【解析】可看作3个不同小球放在4个不同盒子中的放法，共种结果。三n个不同的小球放入m个相同的盒子模型模型8. n个不同的小球放入m个相同的盒子可看作将n个元素分成m组无分配的分法种数，我们有下面的结论：（1）若k1+ k2+ k3+ +km=n且k1，k2，k3， km互不相等，则将n个元素分成m个组（其中第一个组k1个元素，第二个组k2个元素，第m个组km个元素）的不同分法种数为（2）若将n个元素平均分成m个组，每组k个元素（n=mk），则所有不同的分法种数为 (3)一般地，n个不同的元素分成m组，各组内元素数目分别为k，k，其中h组内元素数目相等，那么分组方案是。应