组合学 [6]

发表于 更新于 分类于 ,
本文字数: 4k 阅读时长 ≈ 25 分钟

本篇内容

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

经典问题 Distributing Objects into Boxes

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

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

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

以下为推理过程

∣S∣=(nn1)(n−n1n2)⋯(n−n1−⋯−nk−1nk)=n!n1!n2!⋯nk!|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 !}

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

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

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

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

o ∣ o   o   o ∣ o o\ |\ o\ \ \ o\ \ \ o\ |\ o\

    o   o   o   o   o ∣ ∣ \ \ \ \ o\ \ \ o\ \ \ o\ \ \ o\ \ \ o\ | \ |\

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

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

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

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

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

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

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

Stirling number of the second

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

以下是其计算公式:

S2(n,j)=1j!∑i=0j−1(−1)i(ji)(j−i)nS_2(n,j)=\frac{1}{j!}\sum_{i=0}^{j-1}(-1)^i\binom{j}{i}(j-i)^n

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

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

∑j=1kS2(n,j)=∑j=1k1j!∑i=0j−1(−1)i(ji)(j−i)n\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. 相同物体放入相同盒子

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

整数的分割

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

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

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

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

例如

p3(6)=p3(3+3)=p1(3)+p2(3)+p3(3)=1+1+1=3p4(6)=p4(2+4)=p1(2)+p2(2)+p3(2)+p4(2)=1+1+0+0=2\begin{align}p_3 (6)&=p_3 (3+3)=p_1 (3)+p_2 (3)+p_3 (3)=1+1+1=3 \\ 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），是组合数学中一个重要的计数方法。该原理用于计算并集的大小，即对于给定的有限集合 SS 和它的若干子集 A1,A2,…,AnA_1,A_2,\dots,A_n，计算它们的并集的元素个数。

其公式可以如下表示：

∑i=1nAi=∑k=1n(−1)k−1∑1≤i1<i2<⋯<ik≤n∣Ai1∩Ai2∩⋯∩Aik∣\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| 表示集合 AA 中元素的个数，(−1)k−1(-1)^{k-1} 表示交替求和，∑1≤i1<i2<⋯<ik≤n\sum_{1\leq i_1<i_2<\cdots<i_k\leq n} 表示对所有 1≤i1<i2<⋯<ik≤n1\leq i_1<i_2<\cdots<i_k\leq n 的组合进行求和，∣Ai1∩Ai2∩⋯∩Aik∣\left|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\right| 表示子集 Ai1,Ai2,…,AikA_{i_1},A_{i_2},\dots,A_{i_k} 的交集中元素的个数。

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