八种球盒模型总结

发表于 更新于 分类于 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 6 分钟

球可分辨、不可分辨；盒子可分辨、不可分辨；允不允许空盒子

顺便介绍一下Stirling数以及母函数法

问题的开始

概统书上有两道题，是这样的

  1. 将12个球随机放入3个盒子，求第一个盒子里面有3个球的概率
  2. 将12个完全相同的（不可分辨的）球随机放入3个盒子，求第一个盒子里面有3个球的概率

乍一看，没问题，但是仔细想起来，就会有很多问题，比如

  • 什么是不可分辨的球
  • 可分辨的球可以一个一个放入盒子，那么不可分辨的球是怎么“随机放入”的
  • 这种情况在物理世界真的存在吗？第二个问题有意义吗
  • ...

问了老师，没有得到满意的答案。

和很多人讨论了这个问题，我现在觉得我明白了：

是这个题出的不好！

讨论概率的前提是有一个具体的事件，并且可以检验，而这个题目连怎么放球都没说清楚，这个题目只不过想考这个组合计数的模型，结果弄巧成拙。

在物理世界，球总是有区别的，因此当我们真的把球放进盒子，只能是第一个题的情况，经典物理学不允许完全相同的“球”出现。

也就是说，谈论“不可区分的球放入盒子，有几种组合方式“这个问题是有意义的，就算我们的球里面掺着一堆西瓜球、苹果球，我们也可以把他看成一样的，因为我们关注的只是每个盒子里面球的数量，而不是”是哪只球“。而且，就算我们真的拿着一堆一模一样的东西，我们也可以把它们当做可区分的，因为我们可以把放球的顺序当做他们之间的区别。

但是谈论“不可区分的球放入盒子，形成某种分布的概率是多少”这个问题是没有意义的。原因前面已经说过了。

既然走到这里了，那就研究研究八种球盒模型吧~

球盒模型概述

把n个球放进k个盒子，求有多少种可能情况

哪八种？ 球可不可辩，盒子可不可辩，允不允许空盒子

其实完整的应该有16种，还有还是，但是这两种情况方法类似，所以我们讨论的时候默认

先看几种简单情况

情况 组合数
盒子可以辨别；球可以辨别；允许空盒子
盒子可以辨别；球不能辨别；允许空盒子
盒子可以辨别；球不能辨别；不允许空盒子

高中学过的数学能做到的很有限啊（笑

其实我们还可以知道，如果算出来“盒子不能辨别；球可以辨别；不允许空盒子”的情况（如果等于p)，就可以得到“盒子可以辨别；球可以辨别；不允许空盒子”的情况，等于

嗯，还剩下四个问题。

斯特林数

斯特林数的计算主要体现了递推的思想

第二类斯特林数

组合模型：将集合{1,2，...n}分为k个互不相交的非空集合（），这些子集合之间不做区分，有种方法。

既然说了是递推，那就开门见山： 解释如下：

取元素1，考察1是否单独处于一个集合

  • 如果{1}是一个集合，那么将剩下的n-1个元素分为k-1组，这是
  • 如果1不在一个单元素的集合里面，那么可以看做是先将其他n-1个元素划分为k个集合，然后选择一个集合把1放进去，这是

边界条件：

这个组合模型和“盒子不可区分、球可以区分、不允许空盒子”的情况是一样的，因此这种情况的组合数为，由前面的论证可知，“盒子可以辨别；球可以辨别；不允许空盒子”这种情况我们也知道了。

另一种模型：“盒子不可区分、球可以区分、允许空盒子”也可以用Stirling数解决，如果有k个盒子，我们可以分别考察"有k-1个空盒子"，"有k-2个空盒子"，……"有0个空盒子"这些情况，答案是

第一类斯特林数

组合模型：

表示将n个不同元素构成k个圆排列的数目。

同样有递推公式 解释和第二类斯特林数相似。

又有边界条件

这样就能计算出所有的第一类Stirling数了

一件有意思的事情是，n个数字的每个置换（permutation)对应一种圆排列

因此（不过这个好像没什么用

母函数方法

由前面可知，还剩下2种情况没有解决。

母函数方法介绍

当两个看起来毫无关联的数学方法被某种神秘力量联系在一起的时候，我总是觉得很精妙

例子

求满足的整数解有多少组

这个问题可转化为

求这个多项式展开式中的系数 这样，我们就可以通过等比级数求和、泰勒展开等数学方法求解组合数了！

定义

一个数列对应一个多项式，这个多项式（看做关于变量的函数）就是这个序列的母函数（又叫生成函数）。

可以用母函数解决的组合问题一般可以表示为 其中是满足一定条件的整数

用母函数方法求解球盒模型问题

还剩下这三种：

都是盒子不可区分

  • 球不可区分，允许空盒
  • 球不可区分，不允许空盒

球不可区分就代表我们只关心球的数量，这与上面的例子有相似之处

  1. 球不可区分，允许空盒

    这种模型中，每个盒子都是一样的，显然不能直接用上面的方法做，要先将问题转化一下。

    因为每个盒子都是一样的，所以三个盒子分到球的数量1,2,3和2,3,1属于同一种情况，有什么办法把这些情况统一呢？答案是排序。

    假设k个盒子分到的球的数量为。，其中

    这个方程 解的数量就是我们想要的结果。

    到这一步还不能解决，因为我们无法用母函数方法的语言表示

    直觉告诉我，处理这种东西一般是逐项求差

    设

    由此

    而 只要求解出解的组合数就能得到解的数目

    而这就是母函数 中项的系数

  2. 如果不允许空盒

    那就先往每个盒子里面放一个球，剩下n-k个球再放入盒子，答案是上式中项的系数。

    那这个系数怎么求呢？（我也不知道

[唠叨一下]

在数学建模课上摸鱼看组合数学，觉得这个这个学期能学数学的时间已经很稀有了

但是组合数学真的好好玩！我没选上离散3，不过没关系因为我知道自己就算没选上也是会自己学的

这个学期全是一些奇奇怪怪的课，我没有办法抽出时间去想想想自己到底应该做什么，想要怎么样。

是否从最开始，一切就已经决定了？

另外，很感谢愿意和我讨论问题的朋友们

我很大程度上由此感受了到自己的存在

所以没事可以多找我胡说八道，我一般不会嫌烦的