数学

十二类基本组合问题

$$\huge \rm 基本组合问题$$

$\quad$小球入盒问题是所有组合问题的基础，它计算的是形如 “$n$ 个球放进 $m$ 个盒子的方案数” 的一类问题，在这类问题中一般存在三种限制 ：

• 小球是否有编号。
• 盒子是否有编号。
• 盒子中球的数量是无限制，至少一个还是至多一个。

$\quad$记有编号为 $L(labelled)$，无编号为 $U(unlabelled)$，盒子中球的数量限制分别为 $A,B,C$，这样我们就可以将一个问题用三个字母简记，如 $LUA.$

$\quad$可以发现问题共有 $12$ 类，现在我们来一个个分析。

$\large \rm Part1-LLA$

$\quad$将 $n$ 个有标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量没有限制的方案数。

$\quad$可以看作每次从 $m$ 个盒子里任选一个，一共要放 $n$ 次，没有其他限制，故方案数为 ：

$$\boxed{m^n}$$

$\large \rm Part2-ULA$

$\quad$将 $n$ 个无标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量没有限制的方案数。

$\quad$在这个问题中我们只关心对每个盒子里面球的数量，所以这个问题的方案数等于方程 $x_1+x_2+\cdots +x_m=n$ 非负整数解的数量，用隔板法可以求得其为 ：

$$\boxed{\dbinom{n+m-1}{m-1}}$$

$\large \rm Part3-ULB$

$\quad$将 $n$ 个无标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量至少为 $1$ 的方案数。

$\quad$这个问题与上个问题相似，方案数等于方程 $x_1+x_2+\cdots +x_m=n$ 正整数解的数量，用隔板法可以求得其为 ：

$$\boxed{\dbinom{n-1}{m-1}}$$

$\large \rm Part4-LLC$

$\quad$将 $n$ 个有标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量至多为 $1$ 的方案数。

$\quad$我们发现这个问题等价于依次为每个球选择一个盒子，故答案为 ：

$$\boxed{m^{\underline{n}}}$$

$\large \rm Part5-ULC$

$\quad$将 $n$ 个无标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量至多为 $1$ 的方案数。

$\quad$相当于是为每一个盒子选择数量，等价于从 $m$ 个盒子中选出 $n$ 个，让它的数量为 $1$，故方案数为 ：

$$\boxed{\dbinom{m}{n}}$$

$\large \rm Part6-LUC$

$\quad$将 $n$ 个有标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量至多为 $1$ 的方案数。

$\quad$盒子顺序可以任意交换，所以任意一种方案都等价，发现当球数超过盒子数时无解，故方案数为 ：

$$\boxed{[n\leqslant m]}$$

$\large \rm Part7-UUC$

$\quad$将 $n$ 个无标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量至多为 $1$ 的方案数。

$\quad$理由同上，方案数为 ：

$$\boxed{[n\leqslant m]}$$

$\large \rm Part8-LLB$

$\quad$将 $n$ 个有标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量至少为 $1$ 的方案数。

$\quad$考虑使用容斥原理，枚举有多少个盒子为空，剩下的盒子随便填，故方案数为 ：

$$\boxed{\sum_{i=0}^m(-1)^i\dbinom{m}{i}(m-i)^n}$$

$\quad$利用 $\rm Part9$ 中讲到的第二类斯特林数也可以 $\rm LLB$ 问题的方案数表示为 ：

$$\boxed{\begin{Bmatrix}n\\m\end{Bmatrix}m!}$$

$\large \rm Part9-LUB$

$\quad$将 $n$ 个有标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量至少为 $1$ 的方案数。

$\quad$只需要将 $m$ 个盒子排序产生的方案去除即可，故方案数为 :

$$\boxed{\sum_{i=0}^m\frac{(-1)^i(m-i)^n}{i!(m-i)!}}$$

$\quad \rm LUB$ 问题的答案被定义为 “第二类斯特林数”，递推式如下 ：

$$\boxed{\begin{Bmatrix}n\\m\end{Bmatrix}=m\begin{Bmatrix}n-1\\m\end{Bmatrix}+\begin{Bmatrix}n-1\\m-1\end{Bmatrix}}$$

$\quad$其含义为考虑新加入一个有标号小球，可以将其加入之前的任意一个盒子，也可以为它单独开一个盒子，方案数相加。

$\large \rm Part10-LUA$

$\quad$将 $n$ 个有标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量无限制的方案数。

$\quad$记 $\rm LUA$ 问题的方案数为 $B_n$，读作贝尔数。因为若某个盒子为空可以看作没有这个盒子，故 $B_n$ 表示将 $n$ 个数划分成任意个集合的方案数，有 ：

$$\boxed{B_n=\sum_{i=1}^n\begin{Bmatrix}n\\i\end{Bmatrix}}$$

$\quad$同时，我们发现它也可以递推，有递推式 ：

$$\boxed{B_{n+1}=\sum_{i=0}^n\dbinom{n}{i}B_i}$$

$\quad$其含义为第 $n+1$ 个数若和之前的 $i$ 个数放在一起，方案数为 $\tbinom{n}{i}B_{n-i}.$

$\large \rm Part11-UUA$

$\quad$将 $n$ 个无标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量无限制的方案数。

$\quad$我们发现其实这就是划分数，求法如下 ：

$\quad$记 $f_{i,j}$ 表示将 $i$ 划分成不超过 $j$ 的数的方案数，当计算 $f_{i,j}$ 时，其方案数可以从 $f_{i-j,j}$ 继承，表示分出去一个大小为 $j$ 的数，其方案数也可以从 $f_{i,j-1}$ 继承，表示不选大小为 $j$ 的数。故有转移方程 ：

$$f_{i,j}=f_{i-j,j}+f_{i,j-1}$$

$\quad$我们发现 $f$ 的转移就是一个完全背包，所以考虑将其改写为一维形式，即 ：

$$f_j=\sum_{i=1}^nf_{j-i}$$

$\quad$记 $g_{i,j}$ 表示将 $i$ 划分成 $j$ 个数的方案，当计算 $g_{i,j}$ 时，其方案数可以从 $g_{i-j,j}$ 继承，表示将所有数 $+1$，其方案数也可以从 $g_{i-1,j-1}$ 继承，表示新增一个大小为 $1$ 的数。我们发现后增加的数一定比前增加的数小，所以不重，这样一定能遍历到所有合法的划分，所以不漏，故有转移方程 ：

$$g_{i,j}=g_{i-j,j}+g_{i-1,j-1}$$

$\quad$这两种方式都可以做到 $\Theta(n^2).$

$\quad$我们分析两种方式的优劣，发现第一种算法主要依赖于划分成的数大小的上界，第二种算法主要依赖于划分成数的数量，于是考虑根号分治。将问题看成一个完全背包，物品按照占用空间小于等于 $\sqrt{n}$ 和大于 $\sqrt{n}$ 分类即可。

$\quad$同时，由于 $g$ 计算的只有物品占用空间大于 $\sqrt{n}$ 的情况，所以转移方程要改写成 :

$$g_{i,j}=g_{i-j,j}+g_{i-\sqrt{n},j-1}$$

$\quad$每次加入一个 $\sqrt{n}$ 就可以保证所有数都大于 $\sqrt{n}$ 了。

$\quad$最后统计答案的时候直接枚举 $i$，然后将 $f_i$ 和 $g_{n-i,k}$ 乘起来即可。

$\quad$时间复杂度 $\Theta(n\sqrt{n}).$

$\large \rm Part12-UUB$

$\quad$将 $n$ 个无标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量 至少为 $1$ 的方案数。

$\quad$我们发现只需要先在每个盒子中放 $1$ 个球就可以了，等价于 $\rm UUA$ 问题中 $n-m$ 个球，$m$ 个盒子的情况。