球盒模型的概率问题(4)

下面依次简单说明1到8种情况分配方案数的由来。

1 根据定理2.1.8，把n个不同的球放入m个不同的盒子里，每个盒子可放多个， 也可以不放，其不同的方案数为mn。或者说是m个字母的n元字的个数。

2根据定理2.1.9，把n个完全不同的球放入m个不同的盒子，不允许有空盒的方 案数为m!S2(n,m)。或者说是。元集的有序m部分拆。

3根据定理2.1.10把n个完全不同的球放入m个相同的盒子里，不允许有空盒的 方案数为S2 (n, m)，则把n个完全不同的球放入m个相同的盒子里，允许有空盒的

S(n,i)?方案数为。或者说是n元集分拆成至多m个分部。

2i?1m

4由定义2.1.6知，把n个完全不同的球放入m个相同的盒子里，不允许有空盒的

方案数为S2(n, m)。或者说是n元集的所有m部分拆的个数。

5根据定理2.1.11, m元集上的n元重集(即m元集上的n元可重复组合)的个数记为 ?m???n??。或者说是方程:x1+x2+…+x m=n的非负整数解。 ??6 根据定理2.1.12，把n个完全相同的球放入m个全部不同的盒子里，不允许有

?n?1?空盒的方案数为??m?1??，也即是方程x1+x2+…+x m=n的正整数解。

??7 n个无区别的球放到m个无区别的盒子里，有空盒，相当于把正整数n表示 成k(1≤k≤m)个正整数之和的一种表示法。根据定义2.1.7，把正整数n表示成k个 正整数之和的一种表示法n=n1+n2+…+nk(正整数n的k分拆中，各分布量的次 序无关紧要，一般按递降次序排列，即n1≥n2≥…≥nk≥1)称为n的一个k部分拆， 每个被加数ni称为此分拆的一个分部。n的k部分拆的个数记为P(n, k) ; n的所有 分拆的个数记为P(n)，即p(n)??p(n,k)。所以n个无区别的球放到m个无区别的 盒子里，有空盒的分配方案数为?p(n,k)。也可以简单地说是正整数n分拆成至

k?1nk?1n 6

多m个分部。

8 n个无区别的球放到m个无区别的盒子里，无空盒，相当于n的m部分拆的 个数，由第7种情况可知，其分配方案数记为P(n, m)。也就是正整数n的m部分 拆。

球盒问题，又称占位问题，其实质是分配问题，我们关心的是其分配方案。这里的球可相同可不同，盒子可有标记可无标记，盒子的容量可有限制可无限制，盒子可空非空，球在盒中次序可考虑也可不考虑，盒子的次序可考虑也可不考虑等。显然，这是一个比较复杂的问题，本文就此问题深入研究。

4 本文研究

我们己经知到球盒模型最极端的分配情况有8种，而条件稍微变化一点，哪怕 是一字之差，算法都会截然不同。本章在原有的基础上进行创新，得到其它的分 配模型，即加入一个随机变量x，并且与概率相结合，得到组合恒等式的证明。 用概率证明组合恒等式的主要思路是:针对所要证明的组合恒等式构造出适当的 概率模型，求出该模型中有关事件的概率，然后根据概率的一些性质，推出应有 的结论。

下面的4.14.4中的条件都是n≥m，即球的个数不小于盒子的个数。 4.1 n个不同的球放入m个不同的盒子的情况

如果加入一个随机变量X，相应的问题又该如何解决呢?请看下面的问题: (1)随机变量X表示放球过程中有球的盒子数

问题1:n个不同的球放入m个不同形状的盒子，放球的过程中允许有空盒， 盒子的容量无限制，随机变量X表示放球过程中有球的盒子数，求X的数学期望 E(X)。

先求随机变量X的分布律为

所以X的数学期望为

?根据定义2.2.2的第二条，即(2.2.3)式?pk?1得到下列组合恒等式:

k?1

7

从而变形得到恒等式:

以上是用概率的方法得出的组合恒等式，如果用组合学的方法证明(4.1)又 该怎样证明呢?下面予以说明。

设有n只不同的球，有m个盒子，它们的编号为1,2,…,m。由定理2.1.8知把这n只球放入盒子中，允许有空盒且不限制放入盒子内的球数，总共有mn种方式。这是由于每一个球放到m个盒子中一共有m种方式。于是由乘法规则，有n只不 同的球放到m个有编号的盒子中去共有mn种方式。

另一方面，由定理2.1.9知n只不同的球放入特定的k个不同编号的盒子中去，并

?m?且没有一个空盒的方式数为k!S2(n,k)。而从m个盒子中选取k个盒子的方式数??k??(显

??然，有m-k个盒子为空)，于是由乘法规则知，将n只不同的球放到m个不同的盒子中

?m?且恰有k个盒子为空的方式总数为??k???S2(n,k)?k!。其中1<_k<_m并把这些数相加所

??得的和，就是将n只不同的球放到m个不同的盒子中且允许有空盒的方式数。于是有

?m?在上式中k>m时，??k???0

??

4.2 n个不同的球放入m个全部相同的盒子的情况

问题2: n个不同的球放入m个形状全部相同的盒子，放球的过程中允许有空盒，随机变量X表示放球过程中有球的盒子数，求X的数学期望E(X) 。

m个盒子是无区别的，相当于选出的x个盒子，即n个有区别的球放入x个无区别的盒子，求不允许有空盒的放法数。随机变量X的分布律为

8

所以X的数学期望为

如果本题再变换一下结论：(1)恰好有一个空盒的概率P1是多少?(2)恰好有r(r ≤m -1)个空盒的概率是P2多少?”这样变换题意则毫无意义，因为盒子是一样的，则(1)相当于问题2中的盒子个数是m-1, (2)中相当于问题3中的盒子个数是m-r。 4.3 n个全部相同的球放入m个不同的盒子的情况

根据定理2.1.11得m元集上的n元重集(即m元集的n元可重复组合，或者解 释为n个相同的球放入m个不同的盒子里，盒子可以空的放法数)的个数记为 ??m????m???n?m?1???????，则????n?由第3章表中数据，即由 ??n????n??????????????得:

(1>随机变量X表示放球过程中有球的盒子数

问题3 n个全部相同的球放入m个形状全部不同的盒子，放球的过程中允许有空盒，随机变量X表示放球过程中有球的盒子数，求X的数学期望E(X)。

m个盒子是有区别的，n个球是无区别的，如果放球的过程中允许有空盒， 相当于求方程x1+x2+…+xk = n的非负整数解得个数。而x表示有球的盒子数， 即ξ个盒子有球，且不允许有空盒的放法，相当于求方程x1 + x2 +…+xξ= n的正整 数解的个数。所以随机变量X的分布律为

所以X的数学期望为

根据定义2.2.2的第二条，即由(2.2.3)式?pk?1得到下列组合恒等式:

k?1?

9

即进一步变形得到Vandermode恒等式:

这就是m元集上的n元重集(即m元集的n元可重复组合)的个数的概率方法 证明，其组合解释为:现有m个红球，n-1个白球，并把红球和白球放在一个盒子 里。现从这m+n-1个球中无放回地取出n个球的组合，问共有多少种不同的取法? 即((4.9)式的证明如下:

而取法必定是下列情形之一:有k个红球，n-k个白球，其中(k=0,1,2…,m)，对于固定

?m??n?1??m??n?1??n?1?的k，应有??k????k?1?????k????n?k??种选法，并事先规定??n???0成立，然后按照加法

??????????法则对k求和即得:

即得Vandermode卷积公式:

比较组合恒等式的概率方法证明以及组合方法证明可知，概率法证明简单、 明确、可行。

如果我们进一步考虑此问题:现有m个红球，n-1个白球，事件Xi表示第i个 红球被 …… 此处隐藏：1692字，全部文档内容请下载后查看。喜欢就下载吧 ……