组合数学——“盒子与小球”问题详解（1）
“盒子与小球”问题
“盒子与小球”问题指的是如下这一类问题：把k个小球放到n个盒子里，求一共有多少种方案。这类问题的约束条件有很多种，诸如盒子编号的，小球是编号的，盒子不编号（任意两个盒子没有区别），小球不编号（任意两个小球没有区别），允许有空盒，不允许有空盒，允许小球不放完，不允许小球不放完等等。
基础问题：n个一样的小球，放到k个编号盒子里，不允许盒子空，一共有多少种方案？
小球不编号，盒子编号，把小球放到盒子里，相当于分为若干组，允许某些盒子是空的，小球必须放完。
记g(n,k)= n个一样的小球，放到k个编号盒子里，不允许盒子空，一共有多少种方案？
插板法是解决这个问题的基本方法。插板法解决的问题描述为：把n个一样的元素分为k个不同的组（即编号组），每组至少有1个元素（不允许空盒）的方案数有多少？由于是直接划分，所以肯定是“小球必须放完”的。
插板法实际上是在n个一样的元素之间的空位上插入若干个板子，达到把元素分组的目的。这里有几个方面必须强调一下：
（1）插板法形成的分组是有编号的。示意图：
O：没有编号的元素
| ：插板
（）：空位
5个一样的元素，分成3组：
O （） O （|）O（|）O（）O
第1组...........第2组.......第3组
如示意图所示，在图示位置插板，把5个元素分为了三组。这三组从左往右分别是第1组、第2组、第3组。这个方案把元素分为了2-1-2三个部分。如果组与组之间是一样的，即不编号，那么2-1-2与1-2-2，2-2-1的分组方案是一样的。因此，按照插板法做的方案一定是编号的。
那么，有同学会说，如果分组不编号，能否从编号的情况下进行去重计算出无分组编号的情况下的方案数呢？先看上面的例子，分为1-2-2的方案，按照插板法可以产生3个重复方案。那么如果是6个元素，分成1-2-3的方案，就会有6个重复方案，而分成1-1-4的有3个重复方案。这样，重复方案数和方案本身有关系。想去重无疑和枚举法差不多麻烦。
所以，插板法产生的方案，只能用于分组编号的情形。
（2）插板法不能应用于元素有编号的情形。
以五个编号元素为例：
1（）2（）3（）4（）5
（）内是可以插板的空位。不难发现，无论如何插板，分到一组的元素一定是连续编号的，而且前面一组的编号一定比后面一组的编号小。可见，插板产生的方案无法包括元素编号分组的所有情形。
那么，如果先把元素看作没有编号，分组后再把元素编号，分步处理然后用乘法原理计算方案数量呢？这又会遇到另一个麻烦：分在同一组内的元素不能考虑顺序，重复的方案数量与分在同一组的元素个数有关系，这个情况很复杂，几乎也是每一个方案都必须单独考虑。因此，插板法产生的方案，不能用于元素编号的情形。
综上，插板法的适用问题是：元素无编号，分组有编号，把k个一样的元素分成n个不同的组，每一组至少有一个元素，所有的组内元素之和与元素总量一致，这个问题下的方案数量用插板法计算。
一般的描述是：
把n个苹果放到k个不同的盘子里，不允许盘子空，有多少种方法？
把n个不同的小球放到k个不同的盒子里，不允许盒子空，有多少种方法？
以7个元素为例，计算的模型示意图是：
O()O()O()O()O()O()O
n个元素，有n-1个插板空位，插上k-1个板子能分为k个不同的组。插板间的元素个数就是每组分到的元素个数。
问题的解是：