【学习笔记】浅谈组合数球盒模型

【学习笔记】浅谈组合数球盒模型

MiniLong

·

2023-07-30 12:05:02

·

算法·理论

球盒模型是指将一些相同或不同的球放入一些相同或不同的盒子的方案数。这个模型也广泛运用于组合数学中的常见问题。（其实就是小奥）

关于盒子和球相同或者不同的区别在学习的过程中很容易搞混或者不理解，这里给出一种比较好区分的理解方式。

定义

球异：每个小球都有自己的编号，如五个小球的编号为 1,2,3,4,5，将它们分为三组，因为它们的编号都不同，所以对于两种方案 [1,2][3,4][5] 和 [1,3][2,4][5] 是不同的。

球同：每个小球都没有编号，或者每个小球的编号都是相同的，五个相同的球编号都为 1,1,1,1,1，这时上述分为三组的两种方案是相同的了，因为 [1,1][1,1][1] 和 [1,1][1,1][1] 完全一样。

盒异：与 球异 类似，每个盒子也有自己的编号。通俗的来讲，也就是这些盒子不能重新排列，它们的位置是固定的，假如说三个盒子里有 [1,2,3] 个东西，那么 [1,2,3] 和 [2,3,1] 是不同的两种方案，因为盒子不能移动。

盒同：与上面相反，这些盒子可以任意排列，可以理解为它们是 有序的，也就是两种方案经过排序后不同才是不同，这时上述两种方案都是相同的了。

非空：每个盒子至少有一个球，也就是正整数。

可空：每个盒子球数量任意，也就是非负整数。

懂了这些，那么下面开始讲球盒模型中的 8 类问题了。

变量规定

在以下问题中，都默认球的数量为 n，盒子的数量为 m。

球异盒异

1.可空

相当于 m 个盒子位置是固定的，且 n 个球有编号（也就是不能说两种方案所有盒子中对应的数量相等就是相等的）。

每个球有 m 种选择，那么一共就有 m^n 种方案。

2.非空

可以考虑容斥来做，用总的方案减掉不合法的方案。

枚举空的个数 i，容斥系数即 (-1)^i

那么答案就是 \sum\limits_{i=0}^m (-1)^i \binom{m}{i} (m-i)^n。

$(m-i)^n$ 就是去掉这 $i$ 个空的盒子，剩下 $(m-i)$ 个盒子**可空**的方案。（不要搞混这里，因为是容斥，所以是**可空**）。

同时，这也是 第二类斯特林数 的变形。（下面会讲，写作 $S(n,m)$）。

所以答案也是 $m! \cdot S(n,m)$。

### 球异盒同

1. 非空

这就是典型的 **第二类斯特林数**。

$S(n,m)$ 的定义就是将 $n$ 个不同元素分到 $m$ 个**非空**不交子集的方案数。

与上面 `球异盒异` 的类似，要消除盒子排序后变得有序的方案数。

一个长度为 $x$ 的排列有 $x!$ 种方案。

那么也就是上述方案除以 $m!$。

所以完整的 **第二类斯特林数** 就是 $S(n,m)= \dfrac{1}{m!}

\sum\limits_{i=0}^m (-1)^i \binom{m}{i} (m-i)^n$。

所以这类问题的答案就是 $S(n,m)$ 啦~

2.可空

因为这 $m$ 个盒子是相同的，考虑直接枚举 $i$ 个是空的，剩下 $m-i$ 个盒子都是非空，那么答案就很显然了：

$\sum\limits_{i=0}^m S(n,m-i) = \sum\limits_{i=0}^m S(n,m)

球同盒异

非空

可以用 插板法 来做。

因为这 n 个球是相同的，也就是说两种方案中每个盒子里对应数量相等即可。

插板法就是把每个东西当成一个单位，用板子隔开就是分成新的一组。

如 1,1,1,1,1 中有 4 个空位，下面是一种插板的方法 1 | 1,1,1 | 1,1，用两个板分成了 3 组，为 [1,3,2]，又因为盒子是不同的，不能重新排列，所以这就是一种方案。

所以现在有 n 个球，n-1 个空位，要分成 m 组，就是插 m-1 个板。

又因为是非空的，所以每个空位最多有一个板，根据组合数，所以方案数为 \binom{n-1}{m-1}。

可空

也可以用 插板法 来做，但是每个空位可以放多个板。

可以先将板子放下去，这时一共有 n+(m-1) 个板子和球，在这些中随意挑 n 个位置来放球，或者选 m-1 个位置放板子，那么方案数就是 \binom{n+m-1}{m-1} = \binom{n+m-1}{n}。

球同盒同

可空

这时候不用考虑球的编号，也就是只用考虑在盒子中的数量情况。又因为盒子相同，所以又只用考虑把盒子排序后的数量情况。

有点复杂，可以尝试使用递推解决。

设 f_{i,j} 表示把 i 个相同的球放到 j 个相同的盒子里。

\forall 0 \le k \le m,f_{0,k}=f_{1,k}=1

\forall 0 \le k \le n, f_{k,1} = 1

f_{i,j} = \left\{\begin{aligned} f_{i,j-1} \quad i

如果球的数量小于盒子的数量，那肯定至少有一个空盒子，所以通过 f_{i,j-1} 转移。

如果球的数量大于盒子的数量，又要保证有序（这里可以更好地理解为从大到小排序），也就是前面的盒子数量必须不小于后面的，所以可以将 j 个盒子全部都加入一个小球，这样不会影响顺序（如果不都加入的话可能影响顺序），又可以加入一个空盒子，因为空盒子是最小的，所以必然排到最后面。

答案就是 f_{n,m}。

非空

因为所有盒子至少要装一个小球，所以考虑先在所有盒子里放一个小球，剩下的就可以使用可空时的方案了，也就是答案为 f_{n-m,m}（在 n < m 无解）。