放球问题总结(办公室)

1、最近学习了一下组合数学，对其中的放球问题模型感觉比较有用，特来汇总报告一下，纯 当学习笔记。另外好久没更新了。懒癌晚期伤不起。放球模型主要讲的就是将个球放进个盒子中的组合数。其中，根据球是否可区分，篮子是 否可区分，还有是否允许有空盒，可将放球模型分成个类别。（有的博客和书还根据和的大小 进一步分成类，我觉得没有必要。）下面就来汇总报告一下这类放球问题的组合数计算方 法。）球有区别，盒子有区别，允许有空盒。因为球有区别，那么可以单独拿一个球出来讨论，对于第一个球，可以放到个盒子中的任 意一个，因为盒子也是有区别的，有种方法，对于第二个球，因为允许有空盒的存在，所以每 个球的放法是独立的，所以也

2、有种方法。由乘法原理，知前个球有m2种放法，所以个球一共有口“种放法。易知对于和 两种情况公式不变。2）球有区别，盒子有区别，不允许有空盒因为不允许有空盒，一个球的放法需要考虑前面的球的放置位置，所以每个球的放法 不是相互独立的了，不能用上面的方法。这里可以用容斥原理或者母函数的方法计算该问题的技术指导文件数。方法一：母函数。首先可以将该问题转换成一个排列问题，将盒子看成件物品，问题转换成个有标志的 元素取个做有重复的排列，并且每个元素至少取一个。因为求的是排列问题，所以应该用 指数型母函数。其母函数定义如下:Ge（X）二（X22!3!又由泰勒展开公式有23ex 十 +1!2!3!4!mx 八

3、 mh (m _h)x可知 Ge(x)=(e -1)二 C(m,h)(-1) eh=0eg)x=i+mJhx+(m-h)2x + .f 2)、1!2!n n!(同样由泰勒展开):xn m八 ' C(m,h)(-1)h(m-h)n nA n! h =0所以母函数可以化为下式:Ge(x)八 C(m,h)(1)h' (mh) xn hon/n!我们知道，对于上式中xn项的系数就是我们所要求的组合数，所以对于有个有区别的球放入有区别的个盒子的组合数就是:mE C(m,h)(-1)h(m-h)nh 二0方法二：容斥原理设U表示把，分到个有区别的盒子中的划分集合，允许有空盒，由)的结果我们

4、知|U Hmn。接下来考虑确定个空盒的放置技术指导文件。我们从个盒子中选取个作为空盒，有C(m,h)种选法，剩下的()个盒子，它们可以是空的，也可以不是，也就是将个有区 别的球放入()个有区别的盒子中，允许有空盒的技术指导文件数，同样由的结果，我们知 道技术指导文件数为(m-h)n。所以确定个空盒的技术指导文件数为 C(m, h)(m-h)n，由容 斥原理，我们知道总的技术指导文件数为mZ C(m,h)(-1)h(m-h)nh=0易知， 时，技术指导文件为。3) 球有区别，盒子无区别，不允许有空盒 这个问题其实和第一个问题相关，在这个问题中，盒子的次序不重要，那么对于个盒子，就有！个排列，也就

5、是说，对于)中的每一种技术指导文件，在去掉盒子的标号后，它和另外()个技术指导文件是相同的，可以直接运用)中的结果。知道将个有区别的球，放到个无区别的盒子中，不允许盒子为空的组合数为：m工 C(m,h)(-1)h(m-h)nh=0m!另外，这个问题的答案还可以用另外一个序列描述，这个序列叫做第二类斯特林数。设序列S(n,m)满足S(n,O) =0且S(n, n) =1，且满足递推关系：S(n, m)二 mS(n -1, m) S(n - 1,m -1)(仁 m n)称S(n,m)为第二类斯特林数。它恰恰等于将个有区别的球放入个无区别的盒子中，满足没有一个盒子为空的技术指导文件数。下面说明为什么

6、这个序列能描述我们放球模型的组合数。首先S(n,0) =0表示将个球放入个盒子中，这是不可能的，所以技术指导文件数是。另外，S(n,n )=1表示将个球放入个盒子中，因为不允许有空盒，所以只能是每个盒子恰好 放一个球，又盒子没区别，所以只有一种技术指导文件。所以有 S(1,0) =0和S(1,1) =1。下面看接下来的递推关系如何描述我们的放球模型。首考虑S(n ,m),我们首先将第号球拿出来，根据号球的方法来划分总体的放球技术指导文件数，首先，可以让号球单独放入一个盒子 中，这等价于让另外个球放入其他个盒子中的技术指导文件数。也就是S(n- 1,m-1)种技术指导文件数。或者号球不是单独放在

7、一个盒子中，而是和其他一些球放在同一个盒子中，这等价 于将其他个球放入个盒子中后，在将号球放入这个盒子中的一个，有种方法，所以一共有 mS( n- 1,m)种技术指导文件。所以满足递推式：S(n, m)二 mS(n - 1,m) S(n - 1,m T)所以我们说第二类斯特林数S(n ,m)描述的是将个有区别的球放入个无区别的盒子中，满足 无空盒的技术指导文件数。另外容易得知：当 > 时，()。4) 球有区别，盒子无区别，允许有空盒因为这里允许有空盒，所以这里可以根据非空盒的数量来划分答案，当确定了非空盒 的数量后，该问题等价于)中所描述的问题的技术指导文件，即S(n ,m),所以总技术

8、指导文件数为：S(n,0) S(n,1) s(n,2) .S(n,n) m n s(n,o) + s(n,l)+s(n,2) + .s(n,m) mn数学中称这个序列为数，即B(n)=S(n,0)+S(n,1)+s(n,2) + .S(n,n)数同样满足一个递推式。如下：B(n) = C(n-1,0)B(0) C(n-1,1)B(1) . C(n - 1,n - 1)B(n -1)这个递推式同样可以由组合推理证明。考虑和号球在一起的其他元素的数量，假设是，取法有C(n-1,t)种，剩下来不和号球在一起的个球有B(n -t -1)种方法，所以有n Jn JB(n)八 C(n- 1,t)B(n -

9、1-1)=' C(n- 1,t)B(t)t=0t=0得证。5) 球无区别，盒子有区别，不允许有空盒这个比较简单，利用插板法，将每个球看成，那么问题转化为将这个分成份的技术指导文 件数，因为不允许有空盒，那么一共有个位置可以插板，分成份需要块板，所以技术指导文件 数是 C(n -1, m -1)易知 > 时技术指导文件数为6) 球无区别，盒子有区别，允许有空盒设号盒子的放球数为Xi，则问题转化为XiX2X3X4X5 Xm二n方程的解得个数。同样可以由插板法，和)不同的是，这时不考虑板插放的位置。同样将个球看成是个，另外往里 面插入个板子，一共 个元素，我要在这里面选个为板子，那么一

10、共有C(n m -1, m -1) = C(n m -1, n)种技术指导文件。对于 和w两种情况公式不变。7) 球无区别，盒子无区别，不允许有空盒这个问题相当于将分拆成个数的技术指导文件数，等价于用()来分拆。对于这个问题，一般来说没有一个通用的公式来表示它的解得数量，但是可以用母函数来间接的表示。它 的母函数为：G(x) = (x x2)(x2 x4.)(x3 x6)(xm x2m )所以G(x)的xn项系数即为所求。易知当时，技术指导文件数为8) 球无区别，盒子无区别，允许有空盒这个问题与)类似，同样没有一个公式来描述该问题的数量，只能用母函数来间接计 算组合数。与)不同的一点是它允许存在空盒，那么相应的母函数表达式需要一点变化。我们有G(x) = (1