现在有10个球,要放进3个盒子里
●●●●●●●●●●
隔2个板子,把10个球被隔开成3个部份
●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、......
如此类推,10个球放进3个盒子的方法总数为
n个球放进k个盒子的方法总数为
问题等价于求的可行解数,其中为正整数。
**如果允许有空盒子**:
现在有10个球,要放进3个盒子里,并允许空盒子。考虑10+3个球的情况:
●|●|●●●●●●●●●●●
从3个盒子里各拿走一个,得到一种情况,如此类推:
||●●●●●●●●●●、|●|●●●●●●●●●、|●●|●●●●●●●●、|●●●|●●●●●●●、|●●●●|●●●●●●、......
n个球放进k个盒子的方法总数(允许空盒子)为[2]
问题等价于求的可行解数,其中为非负整数。
也是展开式的项数,这是因为展开后每一项肯定是a1^x1*a2^x2*......*ak^xk,而且x1+x2+...+xk=n.那就转化为上面那个问题了。
另一种变形:
减少球数用隔板法
将20个相同的小球放入编号分别为1,2,3,4的四个盒子中,要求每个盒子中的球数不少于它的编号数,求放法总数。
分析:先在编号1,2,3,4的四个盒子内分别放0,1,2,3个球,剩下14个无区别的球,问题等价于将14个球放入4个编号为1,2,3,4的四个盒子里,每个盒子至少有一个球的问题。
剩下14个无区别的球排成一列,共形成13个空,可以理解为有3块隔板,将排成一列的球隔成4段,每段至少1个,有C3/13=286(种)。