Set partition
= Set partition
A <set partition> of a <finite set> $X$ is a <set> $\pi=\{B_1,\ldots,B_k\}$ of nonempty <subsets>, called <blocks of a set partition>, with
$$
B_i\ne\varnothing,\qquad B_i\cap B_j=\varnothing\quad(i\ne j),\qquad \bigcup_{i=1}^k B_i=X.
$$
Thus every <set element> of $X$ belongs to exactly one <block of a set partition>. This is the finite counting version of a <partition of a set>. The <blocks of a set partition> are \b[unlabelled]: their subscripts help describe them, but give them no roles or order. Stanley uses this definition in his classification of counting problems.<Enumerative Combinatorics, Volume 1 (second-edition draft) by Richard Stanley>[section 1.9: set partitions and their blocks]{ref}
\b[All possibilities for three elements.] The <set> $\{1,2,3\}$ has exactly five <set partitions>:
$$
\begin{gathered}
\{\{1,2,3\}\},\\
\{\{1,2\},\{3\}\},\quad \{\{1,3\},\{2\}\},\quad \{\{1\},\{2,3\}\},\\
\{\{1\},\{2\},\{3\}\}.
\end{gathered}
$$
For two <blocks of a set partition>, one must have size two and the other size one; the three choices of the lone element give the middle row. One <block of a set partition> forces the whole <set>, and three <blocks of a set partition> force three <singleton sets>. This proves the enumeration complete, with counts $1,3,1$ by number of <blocks of a set partition>. Their <sum> is the <Bell number> $B_3=5$.
\Image[/set-partitions-stirling-three-elements.png]
{title=Exact enumeration of the five <set partitions> of $\{1,2,3\}$: outlines show <blocks of a set partition>, whose positions and colours carry no labels}
\b[What information is kept?] Exchanging the two <blocks of a set partition> in $\{\{1,2\},\{3\}\}$ leaves the same <set partition>; writing the <tuple> $(\{1,2\},\{3\})$ instead makes an ordered list, different from $(\{3\},\{1,2\})$. Exchanging elements within a <block of a set partition> also changes nothing. In contrast, $\{\{1,3\},\{2\}\}$ is a different <set partition>, because the actual memberships differ. Both have the same <integer partition> $2+1$ of sizes. An <integer partition>, or its <Ferrers diagram>, forgets which distinct objects were grouped together.
For four named people, $\{\{1,2\},\{3,4\}\}$ and $\{\{1,3\},\{2,4\}\}$ therefore describe different ways of making two unnamed teams, although both have sizes $2+2$. If every team must have exactly two people, only three <set partitions> qualify; if any nonempty team sizes are permitted, the <Stirling number of the second kind> $S(4,2)=7$ counts them. Naming the teams changes the counting problem again.
A <set partition> is useful whenever membership matters but category names do not. Define $x\sim y$ when $x$ and $y$ belong to the same <block of a set partition>. This is an <equivalence relation>, and its <equivalence classes> recover the <set partition>. Conversely, an <equivalence relation> supplies its <set partition> of <equivalence classes>. The beautiful simplification is that one grouping can be described by whole <subsets> or by a rule comparing two elements. Additional distinctions are organized by <refinement of a set partition>.
The <empty set> has one <set partition>, the empty collection $\pi=\varnothing$, with zero <blocks of a set partition>. This differs from $\{\varnothing\}$, which is forbidden because its proposed <block of a set partition> is empty.