本篇内容

经典计数问题（分配问题）
整数的分割
Stirling number of the second
容斥原理

经典问题 Distributing Objects into Boxes#

1. 不同的物体放入不同的盒子#

给定 $n$ 个标记对象，要将它们分配到 $k$ 个标记盒子中。注意在这个问题中不会存在空盒。

我们只能假定一个 “理想的” 分配方案是，每个盒子中指定有 $n_i$ 个对象，其中 $i\in [k]$ 。那么方案的数量为 $N_1=\frac{n!}{n_1 ! n_2 ! \cdots n_k !}$

以下为推理过程

$|S| = \binom{n}{n_1} \binom{n-n_1}{n_2} \cdots \binom{n-n_1-\cdots-n_{k-1}}{n_k} = \frac{n!}{n_1 ! n_2 ! \cdots n_k !}$

可以观察到，实际上问题的答案 $N_1$ 就是 $\{n_1 \cdot 1,\ldots,n_k \cdot k\}$ 的排列数。

2. 相同物体放入不同盒子#

我们可以用隔板法来理解，注意在这个问题中我们将允许空盒。

考虑将 $𝑟$ 个球放入 $𝑛$ 个盒子中，每个盒子可以为空，且球没有编号或标识。将球和盒子视为符号，那么我们可以将该问题转化为找到一个长度为 $𝑟+𝑛−1$ 的符号串，其中有 $𝑛−1$ 个盒子符号 ” | ” 和 $𝑟$ 个球符号 ” o “。例如，当 $𝑛=3$ 且 $𝑟=5$ 时，一个合法的符号串可能如下所示：

$o\ |\ o\ \ \ o\ \ \ o\ |\ o\$ $\ \ \ \ o\ \ \ o\ \ \ o\ \ \ o\ \ \ o\ | \ |\$

每个符号串都对应着一种放置球的方案，例如，上述符号串对应着将 $5$ 个球放置在三个盒子中，第一个盒子放 $1$ 个球，第二个盒子放 $3$ 个球，第三个盒子放 $1$ 个球的方案。注意到符号串中的球符号 ” o ” 和盒子符号 ” | ” 的位置都是固定的，因此问题转化为选择 $𝑛−1$ 个位置放置盒子符号 ” | ” 的方案数。由于每个位置都可以选择放置或不放置符号 ” | “，因此总方案数为：

$\binom{r+n-1}{n-1} = \frac{(r+n-1)!}{r!(n-1)!}$

这个问题有更正式一点的描述，求一个每个元素都数量无限的多重集合的组合，也可以称作普通集合的重组合。

3. 不同物体放入相同盒子#

对于这个问题，一般来说我们需要找到所有可能的分配方案，并将它们按照在每个盒子的分配数 $\{𝑛_1,…,𝑛_𝑘\}$ ¹分类，最后再对每种分类单独求解。

解决这个问题的一种常用方法是使用 生成函数 ²。我们可以将每个盒子看作一个指数，然后使用乘积运算符将它们组合起来，以表示所有可能的方案。通过对生成函数进行操作，我们可以找到方案的总数，以及每种分类的方案数。

接下来我们将细讲一个专门解决这类问题的生成函数

Stirling number of the second#

$S_2(n,j)$ 表示将 $n$ 个不同的对象放入 $j$ 个无区别的盒子中，使得每个盒子都至少有一个对象的不同方案数。其中 $n\geq j\geq 1$ 。

以下是其计算公式:

$S_2(n,j)=\frac{1}{j!}\sum_{i=0}^{j-1}(-1)^i\binom{j}{i}(j-i)^n$

有了这个函数，我们可以分别计算 $k$ 个空盒的情况， $1\leq k\leq j$ ，然后再将我们分别求得的方案数相加，便得到了总方案数。

所以我们能对这类问题总结出公式：

$\sum_{j=1}^k S_2(n,j) = \sum_{j=1}^k \frac{1}{j!}\sum_{i=0}^{j-1}(-1)^i\binom{j}{i}(j-i)^n$

4. 相同物体放入相同盒子#

这个问题就答案等同于问题三中的分类的方案数，而这个问题也和另一个数学模型对应，那就是一个整数的分割。

整数的分割#

其实整数的分割（划分）又和问题二的数学模型是对应的，因为我们可以把整数看成多个 $1$ 累计起来的数，而分割整数就相当于把这些 $1$ 分割， $1$ 和 $1$ 之间是没有区别的，所以这相当于问题二，把多个 $1$ 分配到不同的盒子中。

对于整数的分割问题我们有一个定理直接描述其解之间的规律：

$p_j(n+j)=\sum\limits_{k=1}^j p_k(n) \qquad n\in\mathbb{Z}^+, j\in[n]$

这个定理的直观含义是：将 $n+j$ 分解为 $j$ 个正整数的和的不同方式的数量，可以通过将 $n$ 分解为不超过 $j$ 个正整数的和的不同方式的数量相加得到。

例如

p_4 (6)&=p_4 (2+4)=p_1 (2)+p_2 (2)+p_3 (2)+p_4 (2)=1+1+0+0=2\end{align}$$ # 容斥原理 容斥原理（Principle of Inclusion-Exclusion），是组合数学中一个重要的计数方法。该原理用于计算并集的大小，即对于给定的有限集合 $S$ 和它的若干子集 $A_1,A_2,\dots,A_n$，计算它们的并集的元素个数。 其公式可以如下表示： >$$\sum_{i=1}^n A_i = \sum_{k=1}^n (-1)^{k-1} \sum_{1\leq i_1<i_2<\cdots<i_k\leq n} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}|$$ > >其中，$|A|$ 表示集合 $A$ 中元素的个数，$(-1)^{k-1}$ 表示交替求和，$\sum_{1\leq i_1<i_2<\cdots<i_k\leq n}$ 表示对所有 $1\leq i_1<i_2<\cdots<i_k\leq n$ 的组合进行求和，$\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right|$ 表示子集 $A_{i_1},A_{i_2},\dots,A_{i_k}$ 的交集中元素的个数。

注意这是个重集合，里面的元素具有无序性，但是不具有不重复性。 ↩
生成函数（generating function）是一种用于处理数列（sequence）和计数问题的工具，它可以将一个序列表示成一个函数的形式，从而使得序列中的各项可以用函数的形式表示出来，进而运用函数的性质来解决问题。 ↩