球盒模型

01引言

最近代组课讲了组合计数问题，其中很多内容和高中数学相关内容有所重叠，但是我觉得比高中数学（包括竞赛）那块讲得更清晰更有条理。其中有一类问题是关于小球放盒子的模型，还记得高中学这个的时候总是头疼，为什么一下子用排列公式一下子用组合公式，还有的时候分母还需要额外除以一个阶乘。经过高三总复习以及高考，我才大概摸清楚了里面的门道：不同公式的选用取决于小球和盒子是否无差别。其实高考结束的暑假就想总结一下这一类问题的，但毕竟考完了，只想着玩去了，没有这种心情，故直到最近在代组课上又重新学习以及延拓这部分知识时，才终于有机会把它们总结如下：

02基础知识

排列组合公式

n元集合S，从中选取r个元素的方法数

定理1：（不重复有序排列）

从n元集合S中有序、不重复选取r个元素，称为S的一个r-排列，S的所有r-排列数目为：

$P(n,r)=\left\{ \begin{array}{cl} \frac{n!}{(n-r)!} & r\leq n \\ 0 & r>n\\ \end{array} \right.$

定理2：（不重复无序组合）

从n元集合S中无序、不重复选取r个元素，称为S的一个r-组合，S的所有r-组合数目为：

$C(n,r)=\frac{P(n,r)}{r!}\tag{1}$

定理3：（多重集的排列）

设 $S=\{n_1*a_1,n_2*a_2,\dots,n_k*a_k\}(0<n_i\leq+\infin)$ ，其中 $n_i*a_i$ 表示 $a_i$ 有 $n_i$ 个，求S的r-排列计数结果 $N$ 。

通常情况下没有统一的公式，但是在以下特殊情况，有如下结果：

全排列（ $r=n=\sum_{i=1}^k n_k$ ）时，

$\begin{aligned} N&=C(n,n_1)C(n-n_1,n_2)\ldots C(n-n_1-\ldots-n_{k-1},n_k)\\ &=\frac{n!}{n_1!n_2!\ldots n_k!}\\ \end{aligned}\tag{2}$

元素数量足够多时， $r\leq n_i$ ，

$N=k^r\tag{3}$

定理4：（多重集的组合）

$S$ 同上，从 $S$ 中取r个元素，我们只考虑各种元素足够多，即 $r\leq n_i$ 的情况，显然这对应于不定方程

$x_1+x_2+\ldots+x_k=r\tag{4}$

的非负整数解的个数，也即：

$N=C(k+r-1,r)\tag{5}$

定义1：（第二类Stirling数）

把n元集合S划分为m个不相交非空子集的方法数，记为S(n,m)。此问题的解为第二类Stirling数 $\{n,m\}$ ，也即：

$S(n,m):=\left\{ \begin{array}{c} n\\ m \end{array} \right\}$

满足递推式： $S(n+1,m)=S(n,m-1)+mS(n,m)$

原因：把n+1个元素放在m个子集中，可以先把前n个放在m个子集中，然后把最后一个放在m个子集任何一个里面=> $mS(n,m)$ ，也可以把前n个放在m-1个子集中，最后一个单独放在一个子集里面=> $S(n,m-1)$ .

另外，利用容斥原理可以得到通项式：

记 $A_i$ 表示第 $i$ 个盒子为空的放法数，显然 $\lvert{\cap_{i=1}^k A_{j_i}}\rvert=(m-k)^n$ ，则

$\begin{aligned} m!S(n,m)&=\lvert{\cup_{i=1}^m A_i}\rvert\\ &=\sum_{k=0}^m(-1)^kC(m,k)(m-k)^n \end{aligned}\tag{6}$

PS：先把盒子视作不同，最后再除以m!即可

【因为n个元素互不相同，即使两个子集元素数相同，它们也是不一样的，因此m个子集每个组合对应m!个排列，所以才能直接除，参见下面】

03球盒模型

基本问题：把r个小球放入n个盒子里，求放法的个数。

根据小球与盒子之间是否有区别，我们分为四类进行讨论：

n个不同小球放入r个不同盒子

解：显然，每个小球有r种放法，因此总方法数为 $n^r$ .

变式：附加要求每个盒子非空

解：利用基础知识部分的结论，答案为 $r!S(n,r)$

注1：一开始想着直接每个盒子减去一个小球不就变成n-r个小球放r个盒子且没有非空要求了，但是注意到这里小球是不同的，不能直接减去（无法构造一一对应）

注2：用变式的结论重新算上面的问题，我们得到：

$n^r=\sum_{k=0}^r P(r,k)S(n,k)$ （讨论几个盒子非空）
n个不同小球放入r个相同盒子

具体而言，又有两种子问题：
- 每个盒子放球数目预先规定好了，不妨设为 $k_1,k_2,\ldots,k_r$ ，满足 $n=\sum_{i=1}^{r}k_i$ ；
  
  这是高中练习题中常见的分堆问题，常常表现为n本书分成r堆的形式；
  
  不妨假设 $\{k_i\}_{i=1}^r$ 里面有t个不同的值，记作 $\{a_j\}_{j=1}^t$ ，其中 $a_j$ 出现次数为 $s_j$ 次；
  注意到放球数量相同的盒子之间顺序没有区别，所以总的放法数为:
  
  $\frac{C(n,k_1)C(n-k_1,k_2)\ldots C(n-k_1-\ldots-k_{r-1},k_r)} {s_1!s_2!\ldots s_t!}$
  
  如果说盒子不同（比如分给不同人），还需要乘以 $r!$ .
- 每个盒子球数没有规定
  
  枚举空盒个数，得 $\sum_{i=0}^r S(n,i)$
  
  注：显然这个结果也是所有可能的分堆方式的方法数求和
n个相同小球放入r个不同盒子

解：设第 $i$ 个盒子放 $x_i$ 个小球，则对应于 $x_1+x_2+\ldots+x_r=n$ 的非负整数解个数，因此方法数为： $N=C(n+r-1,n)$ .

注：此时若要求非空，则可以直接每个盒子减去一个小球转化为n-r个小球放r个盒子且没有非空要求
n个相同小球放入r个相同盒子

解：等价于把n拆成r个自然数之和的允许重复的无序拆分方法数目，也即n拆成不超过r个正整数的方法数目，我们可以用母函数方法解出来：

令 $f_{i}(x)=1+x^i+x^{2i}+\ldots=\frac{1}{1-x^i}$

则n允许重复拆分成若干个正整数的拆分方法为 $\prod_{i=1}^nf_i(x)$ 的n次项系数，可用某些方法得到（好吧我还没想到，实在不行就Taylor展开）

那么允许重复拆分成不超过r个正整数的方法有多少个呢？可以转换为对偶问题，也即允许重复拆分成大小不超过r的若干个正整数的方法。

课堂上用的是Ferrers图的转置来解释，但是显然有更直观的解释：按从大到小顺序排列大小不超过r的一列正整数 $\{a_i\}$ ，考虑不超过r个的数列 $\{b_i\}$ ，建立 $\{a_i\}$ 与 $\{b_i\}$ 的关系为： $a_i$ 表示 $\geq i$ 的 $b_k$ 个数，可以验证是一一对应。所以这个问题的生成函数是 $\prod_{i=1}^rf_i(x)$ ，求出n次项系数即可。

注意：不要直接用3中的结果直接除以r!，因为球相同，所以球数相同的盒子状态完全一样，例如{3,3,2}，不能直接通过乘以3!来得到有序排列的数目。

04总结

球盒模型按照球与盒是否有区别分成四大类：

若球盒均不同，那么是简单的乘法公式；

若球不同盒同，是分堆或第二类Stirling数的变形；

若球同盒不同，化为非负整数解个数；

若球盒均相同，等价于正整数的划分问题；

2022/05/31补充

今天在课堂上进行了一个更全面的总结，简单列表如下：

n球	m盒	空盒	方法数	对应组合问题
同	同	不允许	$P_m(n)-P_{m-1}(n)$	将n剖分成m个正整数
同	同	允许	$P_m(n)$	将n剖分成m个自然数
同	不同	不允许	$C_{n-1}^{m-1}$	$x_1+\dots+x_m=n$ 的正整数解个数
同	不同	允许	$C_{n+m-1}^n$	$x_1+\dots+x_m=n$ 的非负整数解个数
不同	同	不允许	$S(n,m)$	第二类Stirling数
不同	同	允许	$\sum_{i=0}^mS(n,i)$	第二类Stirling数求和
不同	不同	不允许	$m!S(n,m)$	第二类Stirling数排列
不同	不同	允许	$m^n$	乘法原理

（来自《离散数学教程》北京大学出版社 $P_{393}$ ，有删改）

May 15, 2022 Views:

球盒模型

01引言

02基础知识

03球盒模型

04总结