Set Partition

A set partition is a collection of nonempty, mutually disjoint subsets, called blocks, that together contain every element of a given set. Each element therefore belongs to exactly one block. Partitions describe grouping without assigning an order to the groups or to their members. They are fundamental objects in set theory and combinatorics, and correspond precisely to equivalence relations. (web.mit.edu)

Definition and examples

A partition $\pi$ of a set $X$ is a collection of subsets of $X$ satisfying three conditions:

1. Nonemptiness: $A\ne\varnothing$ for every $A\in\pi$.
2. Disjointness: $A\cap B=\varnothing$ whenever $A,B\in\pi$ and $A\ne B$.
3. Exhaustiveness: $\displaystyle\bigcup_{A\in\pi}A=X$.

Thus, a partition is a set of subsets, not a subset of elements of $X$. The number of blocks need not be finite. (web.mit.edu)

For example, the five partitions of $\{1,2,3\}$ are

Reordering the blocks does not produce another partition. The collection $\{\{1,2\},\{2,3\}\}$ fails because its blocks overlap. These examples follow directly from the definition. (web.mit.edu)

For a nonempty set $X$, the discrete partition consists of all singleton subsets, while the indiscrete partition has the single block $X$. Under the nonempty-block convention, the empty set has exactly one partition: the empty collection of blocks. (math.ucr.edu)

Equivalence relations and quotient sets

Every partition $\pi$ defines an equivalence relation by

This relation is reflexive, symmetric, and transitive. Conversely, the equivalence classes of any equivalence relation on $X$ form a partition of $X$. The two constructions are inverse to one another: specifying a partition and specifying an equivalence relation are equivalent descriptions of the same grouping structure. (web.mit.edu)

The collection of equivalence classes is called the quotient set, written $X/{\sim}$. For example, congruence modulo a positive integer $m$ partitions the integers into $m$ blocks:

Both the underlying set and each block are infinite, although the number of blocks is finite. (web.mit.edu)

A related construction uses a function $f:X\to Y$. Equality of outputs, $f(x)=f(x')$, is an equivalence relation, so its nonempty fibers $f^{-1}(\{y\})$, for $y\in f(X)$, partition $X$. This follows from the equivalence-relation correspondence; different labels for the same fibers do not change the partition. (math.ucr.edu)

Counting finite partitions

The number of partitions of an $n$-element set into exactly $k$ blocks is the Stirling number of the second kind, denoted

The elements are distinguishable, but the blocks are unlabeled. The boundary conditions include $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,n)=1$. (dlmf.nist.gov)

These numbers satisfy the recurrence

To see why, distinguish one element. It either forms a singleton block, leaving $k-1$ blocks among the remaining elements, or joins one of their $k$ existing blocks. An explicit formula is

where $k!$ is a factorial and $\binom{k}{j}$ is a binomial coefficient. In particular, assigning distinct labels to all $k$ blocks gives $k!S(n,k)$ surjective functions onto a fixed $k$-element set. (dlmf.nist.gov)

The total number of partitions is the Bell number

Beginning at $n=0$, the values are

Thus, a four-element set has 15 partitions, whereas a ten-element set has 115,975. Bell numbers also count equivalence relations on a finite set, by the correspondence described above. (dlmf.nist.gov)

Their exponential generating function is

They satisfy the recurrence

A combinatorial explanation chooses the $j$ elements outside the block containing a distinguished new element, then partitions those $j$ elements arbitrarily. (dlmf.nist.gov)

Refinement and the partition lattice

A partition $\pi$ refines a partition $\sigma$, written $\pi\le\sigma$, if every block of $\pi$ is contained in a block of $\sigma$. Equivalently, $\sigma$ can be obtained by merging blocks of $\pi$. Refinement defines a partial order, whose least element is the discrete partition and whose greatest element is the indiscrete partition. (math.ucr.edu)

Under this order, partitions form a lattice:

• The meet $\pi\wedge\sigma$, their greatest common refinement, consists of all nonempty intersections $A\cap B$, with $A\in\pi$ and $B\in\sigma$.
• The join $\pi\vee\sigma$, their least common coarsening, groups elements connected by chains in which consecutive elements share a block of either partition.

The lattice of partitions of $\{1,\ldots,n\}$ is conventionally denoted $\Pi_n$. It organizes the relationships between different groupings, rather than merely counting them. (ocw.mit.edu)

Distinction from integer partitions

A set partition must not be confused with an integer partition, which expresses a positive integer as an unordered sum of positive integers. For a finite set partition, the block sizes determine an integer partition, but discard information about which elements belong together. For example,

are different set partitions with the same block sizes $2+2$. Counting block-size patterns therefore differs from counting partitions of distinguishable elements. (dlmf.nist.gov)

References

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