排列组合：小球入盒.doc

《排列组合：小球入盒.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、小球入盒模型的推广应用摘要：小球入盒是排列组合的典型问题，本文从小球同与不同及盒子同与不同几方面对小球入盒模型的加以推广应用。小球入盒是排列组合的典型问题，与之相关的有名额分配、人员分配等问题，形式多样.“小球入盒问题”问题可以分为四类：不同的小球放入不同的盒子里；不同的小球放入相同的盒子里；相同的小球放入不同的盒子里；相同的小球放入相同的盒子里（此类不做重点讨论）。解答小球入盒问题的最有效、最易于操作的方法是“先分组后分配”，即先将元素分组、再分配到位置.分组时应注意平均分组与非平均分组的区别；放入相同盒子可看作分组无分配问题；解答相同小球入不同盒子问题的最有效、最易于操

2、作的方法是隔板法。【引例】①把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、方法)、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个不同的盒子模型在排列组合中，对于将不可分辨的球装入

4、到可以分辨的盒子中而求装入方法数的问题，常用隔板法。模型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个

5、位置中选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个位置安排隔板，有（种）方法。隔板法：将放有小球的盒子紧挨着成一行

6、放置，便可看作成一行的小球的空隙中插入了若干隔板，相邻两块隔板形成一个“盒”．每一种插入隔板的方法对应着小球放人盒子的一种方法，此法称为隔板法．隔板法专门解决相同元素的分配问题．应用1（求不定方程整数解）1.不定方程的正整数解的个数为。【解析】可看作n个相同的小球放入m个不同盒子中,要求每个盒子不空时球的放法数，于是将n个小球排成一行，它们形成n-1个空挡，只插m-1个隔板，故有种方法。2．不定方程的非负正整数解的个数为。【解析】可看作n个相同的小球放入m个不同盒子中,要求每个盒子可空时球的放法数,由模型2知非负正整数解的个数为。应用2（多项式定理中展开式项数问题）3.三项

7、式展开式共有多少不同的项?【解析】的展开式中每一项的指数和均是n，相当于n个无区别的球放入、、三个不同的盒子里，每个盒放入的球数不限，由模型2知为展开式中共有不同的项数为。应用3（名额分配问题）4.将10个优秀的指标分配给3个班级，（1）每班至少一个，则共有多少种分配方法？（2）任意分配共有多少种分配方法？（3）若班级为一、二、三班，若名额数不小于班级数，则共多少种分配方法？【解析】：由于10个优秀指标是相同的，该题等价于10个相同的小球放入3个不同盒子模型。可采用“隔板法”。（1）插隔板，即9个空格中插入2个隔板