集合划分 · aiwiki.page

集合划分是由若干非空且两两不相交的子集组成的集合，这些子集称为块，共同包含给定集合的所有元素。因此，每个元素恰好属于一个块。划分描述的是分组方式，而不规定各组之间或组内元素之间的顺序。集合划分是集合论和组合数学中的基本对象，与等价关系一一对应。(web.mit.edu)

定义与示例

集合 $X$ 的一个划分 $\pi$ 是由 $X$ 的子集组成的集合，满足以下三个条件：

非空性： 对每个 $A\in\pi$ ，都有 $A\ne\varnothing$ 。
不相交性： 若 $A,B\in\pi$ 且 $A\ne B$ ，则 $A\cap B=\varnothing$ 。
覆盖性： $\displaystyle\bigcup_{A\in\pi}A=X$ 。

因此，划分是由子集组成的集合，而不是由 $X$ 的元素组成的某个子集。块的数量不一定是有限的。(web.mit.edu)

例如， $\{1,2,3\}$ 的五个划分为

\begin{aligned} &\{\{1,2,3\}\},\\ &\{\{1\},\{2,3\}\},\\ &\{\{2\},\{1,3\}\},\\ &\{\{3\},\{1,2\}\},\\ &\{\{1\},\{2\},\{3\}\}. \end{aligned}

改变块的排列顺序不会产生新的划分。 $\{\{1,2\},\{2,3\}\}$ 不是划分，因为其中的块有重叠。这些例子都可以直接根据定义判断。(web.mit.edu)

对于非空集合 $X$ ，离散划分由所有单元素子集组成，而非离散划分仅有一个块，即 $X$ 本身。按照块必须非空的约定，空集恰好有一个划分：不含任何块的空集合。(math.ucr.edu)

等价关系与商集

每个划分 $\pi$ 都通过下式定义一个等价关系：

x\sim_\pi y \quad\Longleftrightarrow\quad x\text{ 与 }y\text{ 属于同一个块}.

这一关系具有自反性、对称性和传递性。反过来， $X$ 上任意等价关系的等价类构成 $X$ 的一个划分。这两种构造互为逆过程：给出一个划分与给出一个等价关系，是对同一分组结构的两种等价描述。(web.mit.edu)

由等价类组成的集合称为商集，记作 $X/{\sim}$ 。例如，给定正整数 $m$ ，模算术中的模 $m$ 同余关系将整数划分为 $m$ 个块：

[r]=\{r+km:k\in\mathbb Z\}, \qquad r=0,\ldots,m-1.

尽管块的数量有限，原集合和每个块都是无限集。(web.mit.edu)

另一种相关构造使用函数 $f:X\to Y$ 。函数值相等，即 $f(x)=f(x')$ ，定义了一个等价关系，因此其非空纤维 $f^{-1}(\{y\})$ （其中 $y\in f(X)$ ）构成 $X$ 的一个划分。这是等价关系与划分之间对应关系的直接结果；为同一组纤维赋予不同标签，不会改变这个划分。(math.ucr.edu)

有限集合划分的计数

将一个含 $n$ 个元素的集合划分为恰好 $k$ 个块的方法数，是第二类斯特林数，记作

S(n,k) \quad\text{或}\quad \left\{\begin{matrix}n\\k\end{matrix}\right\}.

元素彼此可区分，但块没有标签。边界条件包括 $S(0,0)=1$ 、当 $n>0$ 时 $S(n,0)=0$ ，以及 $S(n,n)=1$ 。(dlmf.nist.gov)

这些数满足递推关系

S(n,k)=S(n-1,k-1)+kS(n-1,k), \qquad n,k\ge1.

其理由如下：选定一个元素，它要么独自组成一个单元素块，此时其余元素组成 $k-1$ 个块；要么加入其余元素已经组成的 $k$ 个块之一。一个显式公式为

S(n,k)=\frac1{k!} \sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n, \qquad n,k\ge1,

其中， $k!$ 是阶乘， $\binom{k}{j}$ 是二项式系数。特别地，为全部 $k$ 个块赋予互不相同的标签，就得到从原集合到一个固定的 $k$ 元素集合的 $k!S(n,k)$ 个满射函数。(dlmf.nist.gov)

划分的总数是贝尔数

B_n=\sum_{k=0}^{n}S(n,k).

从 $n=0$ 开始，其值依次为

1,\ 1,\ 2,\ 5,\ 15,\ 52,\ 203,\ 877,\ldots.

因此，一个四元素集合有 15 个划分，而一个十元素集合有 115,975 个划分。根据上述对应关系，贝尔数也表示有限集合上等价关系的数量。(dlmf.nist.gov)

贝尔数的指数生成函数为

\sum_{n=0}^{\infty}B_n\frac{x^n}{n!} =\exp(e^x-1).

它们满足递推关系

B_{n+1}=\sum_{j=0}^{n}\binom nj B_j.

对此可以给出一个组合解释：加入一个指定的新元素，从原有元素中选出 $j$ 个，使其不属于新元素所在的块，再任意划分这 $j$ 个元素。(dlmf.nist.gov)

细化与划分格

如果划分 $\pi$ 的每个块都包含于划分 $\sigma$ 的某个块中，就称 $\pi$ 细化了 $\sigma$ ，记作 $\pi\le\sigma$ 。等价地， $\sigma$ 可以通过合并 $\pi$ 的块得到。细化关系定义了一个偏序，其最小元是离散划分，最大元是非离散划分。(math.ucr.edu)

在这一偏序下，所有划分构成一个格（序理论）：

交 $\pi\wedge\sigma$ 是两者的最大公共细化，由所有非空交集 $A\cap B$ 组成，其中 $A\in\pi$ 、 $B\in\sigma$ 。
并 $\pi\vee\sigma$ 是两者的最小公共粗化：若两个元素可以通过一条元素链连接，且链中每对相邻元素都同属于某一个划分的同一块，就将它们归入同一个块。

集合 $\{1,\ldots,n\}$ 的划分格通常记作 $\Pi_n$ 。它刻画不同分组方式之间的关系，而不仅仅是对这些分组方式进行计数。(ocw.mit.edu)

与整数分拆的区别

集合划分不应与整数分拆混淆，后者是将一个正整数表示为若干正整数之和，而不考虑加数的顺序。对于有限集合的划分，各块的大小确定了一个整数分拆，但丢失了哪些元素属于同一块的信息。例如，

\{\{1,2\},\{3,4\}\} \quad\text{与}\quad \{\{1,3\},\{2,4\}\}

是两个不同的集合划分，却有相同的块大小 $2+2$ 。因此，对块大小的组合方式进行计数，与对可区分元素的划分进行计数并不相同。(dlmf.nist.gov)

参考来源

Mathematics for Computer Scienceweb.mit.edu
Lecture 11: The Poset of Partitionsmath.ucr.edu
DLMF: §26.8 Set Partitions: Stirling Numbersdlmf.nist.gov
DLMF: §26.7 Set Partitions: Bell Numbersdlmf.nist.gov
212 S19 Algebraic Combinatorics, Lecture 15: Posets and lattices. Boolean lattice. Partition lattice. Young's latticeocw.mit.edu
Some of My Favorite Posetsmath.mit.edu
DLMF: Chapter 26 Combinatorial Analysisdlmf.nist.gov