放球问题总结

最近学习了一下组合数学，对其中的放球问题模型感觉比较有用，特来总结一下，纯当学习笔记。另外好久没更新了。懒癌晚期伤不起。放球模型主要讲的就是将n个球放进m个盒子中的组合数。其中，根据球是否可区分，篮子是否可区分，还有是否允许有空盒，可将放球模型分成8个类别。（有的博客和书还根据m和n的大小进一步分成16类，个人觉得没有必要。）下面就来总结一下这8类放球问题的组合数计算方法。1) 球有区别，盒子有区别，允许有空盒。因为球有区别，那么可以单独拿一个球出来讨论，对于第一个球，可以放到m个盒子中的任意一个，因为盒子也是有区别的，有m种方法，对于第二个球，因为允许有空盒的存在，所以每个球的放法是独立的，所以也有m种方法。由乘法原理，知前2个球有种放法，所以n个球一共有 种放法。易知对于 nm和mn两种情况公式不变。2） 球有区别，盒子有区别，不允许有空盒。因为不允许有空盒，一个球的放法需要考虑前面的球的放置位置，所以每个球的放法不是相互独立的了，不能用上面的方法。这里可以用容斥原理或者母函数的方法计算该问题的方案数。方法一：母函数。首先可以将该问题转换成一个排列问题，将m盒子看成m件物品，问题转换成m个有标志的元素取n个做有重复的排列，并且每个元素至少取一个。因为求的是排列问题，所以应该用指数型母函数。其母函数定义如下：又由泰勒展开公式有 可知 其中 （同样由泰勒展开）所以母函数可以化为下式：我们知道，对于上式中项的系数就是我们所要求的组合数，所以对于有n个有区别的球放入有区别的m个盒子的组合数就是： 方法二：容斥原理设表示把1,2,3，.,n分到m个有区别的盒子中的划分集合，允许有空盒，由1）的结果我们知。接下来考虑确定h个空盒的放置方案。我们从m个盒子中选取h个作为空盒，有种选法，剩下的(m-h)个盒子，它们可以是空的，也可以不是，也就是将n个有区别的球放入(m-h)个有区别的盒子中，允许有空盒的方案数，同样由1的结果，我们知道方案数为。所以确定h个空盒的方案数为，由容斥原理，我们知道总的方案数为易知，mn时，方案为0。3） 球有区别，盒子无区别，不允许有空盒这个问题其实和第一个问题相关，在这个问题中，盒子的次序不重要，那么对于m个盒子，就有m！个排列，也就是说，对于1）中的每一种方案，在去掉盒子的标号后，它和另外(m!-1)个方案是相同的，可以直接运用1）中的结果。知道将n个有区别的球，放到m个无区别的盒子中，不允许盒子为空的组合数为：另外，这个问题的答案还可以用另外一个序列描述，这个序列叫做第二类斯特林数。设序列 满足 且，且满足递推关系： 称为第二类斯特林数。它恰恰等于将n个有区别的球放入m个无区别的盒子中，满足没有一个盒子为空的方案数。下面说明为什么这个序列能描述我们放球模型的组合数。首先表示将n个球放入0个盒子中，这是不可能的，所以方案数是0。另外，表示将n个球放入n个盒子中，因为不允许有空盒，所以只能是每个盒子恰好放一个球，又盒子没区别，所以只有一种方案。所以有和。下面看接下来的递推关系如何描述我们的放球模型。首考虑,我们首先将第n号球拿出来，根据n号球的方法来划分总体的放球方案数，首先，可以让n号球单独放入一个盒子中，这等价于让另外n-1个球放入其他m-1个盒子中的方案数。也就是种方案数。或者n号球不是单独放在一个盒子中，而是和其他一些球放在同一个盒子中，这等价于将其他n-1个球放入m个盒子中后，在将n号球放入这m个盒子中的一个，有m种方法，所以一共有种方案。所以满足递推式：所以我们说第二类斯特林数描述的是将n个有区别的球放入m个无区别的盒子中，满足无空盒的方案数。另外容易得知：当mn时，S(n,m)=0。4） 球有区别，盒子无区别，允许有空盒因为这里允许有空盒，所以这里可以根据非空盒的数量来划分答案，当确定了非空盒的数量m后，该问题等价于3）中所描述的问题的方案，即,所以总方案数为：数学中称这个序列为Bell数，即Bell数同样满足一个递推式。如下：这个递推式同样可以由组合推理证明。考虑和n号球在一起的其他元素的数量，假设是t，取法有种，剩下来不和n号球在一起的n-t-1个球有种方法，所以有得证。5） 球无区别，盒子有区别，不允许有空盒这个比较简单，利用插板法，将每个球看成1，那么问题转化为将这n个1分成m份的方案数，因为不允许有空盒，那么一共有n-1个位置可以插板，分成m份需要m-1块板，所以方案数是易知mn时方案数为06） 球无区别，盒子有区别，允许有空盒设i号盒子的放球数为，则问题转化为方程的解得个数。同样可以由插板法，和5）不同的是，这时不考虑板插放的位置。同样将n个球看成是n个1，另外往里面插入m-1个板子，一共 n+m-1个元素，我要在这里面选m-1个为板子，那么一共有种方案。对于 mn和mn两种情况公式不变。7） 球无区别，盒子无区别，不允许有空盒这个问题相当于将n分拆成m个数的方案数，等价于用（1,2,3,.m）来分拆n。对于这个问题，一般来说没有一个通用的公式来表示它的解得数量，但是可以用母函数来间接的表示。它的母函数为：所以的项系数即为所求。易知当mn时，方案数为08） 球无区别，盒子无区别，允许有空盒这个问题与7）类似，同样没有一个公式来描