Set Partitions

# 1. Definition

A **set partition** of a set $\mathcal{S}$ is a collection of non-empty pairwise disjoint subsets (also known as the **parts**) of $\mathcal{S}$ whose union is $\mathcal{S}$. Mathematically we have $\mathcal{P} = \{P \subset S\}$ such that

$\emptyset \notin \mathcal{P}$,

$P_1 \cap P_2 = \emptyset$ for all $P_1 \neq P_2 \in \mathcal{P}$,

$\bigcup \mathcal{P} = S$.

# 2. Examples

Let $\mathcal{S} = \{1, 2, 3, 4\}$.

$\{ \{1\}, \{2\}, \{3\}, \{4\} \}$

$\{ \{1\}, \{2\}, \{3, 4\}$

$\{ \{1\}, \{3\}, \{2, 4\}$

$\{ \{1\}, \{4\}, \{2, 3\}$

$\{ \{2\}, \{3\}, \{1, 4\}$

$\{ \{2\}, \{4\}, \{1, 3\}$

$\{ \{3\}, \{4\}, \{1, 2\}$

$\{ \{1, 2\}, \{3, 4\} \}$

$\{ \{1, 3\}, \{2, 4\} \}$

$\{ \{1, 4\}, \{2, 3\} \}$

$\{ \{1\}, \{2, 3, 4\} \}$

$\{ \{2\}, \{1, 3, 4\} \}$

$\{ \{3\}, \{1, 2, 4\} \}$

$\{ \{4\}, \{1, 2, 3\} \}$

$\{ \{1, 2, 3, 4\} \}$

# 3. Properties

The number of set partitions where $|\mathcal{S}| = n$ is known as the $n$-th Bell number $B_n$.

The number of set partitions such that $|\mathcal{S}| = n$ and $|\mathcal{P}| = k$ is known as the Stirling number of the second kind $S(n, k)$.

The set partitions of a fixed set forms a poset by containment. In particular they form a lattice where the infimum of two set partitions is the set partition obtained by intersecting all the parts of both set partitions and the supremum is obtained by transitive closure of the relation $i$ related to $j$ if and only if they are in the same part in at least one of the set partitions.

# 4. Remarks

Note that $B_4 = 15$ and all $15$ set partitions of $\{1, 2, 3, 4\}$ are listed in the examples block.

- The Bell numbers satisfy the recurrence relation
$$B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k.$$

We also have $B_n = \sum_{k=1}^n S(n, k)$.

Set partitions can be ordered, that is to say $( \{1, 2\}, \{3\} ) \neq (\{3\}, \{1, 2\})$, and the number of ordered set partitions is $\sum_{k=1}^n k! S(n, k)$.

A set partition is said to be

**non-crossing**if the parts can not be interlaced. That is to say there does not exist $P, Q \in \mathcal{P}$ which contains elements $a, b \in P$ and $x, y \in Q$ such that $a < x < b < y$. Visually if we draw the set $\{1, 2, \ldots, n\}$ on a line, then we can connect the parts of $\mathcal{P}$ such that the lines do not cross. The number of non-crossing set partitions where $|\mathcal{S}| = n$ is the Catalan number $C_n$.

# 5. Statistics

We have the following **92 statistics** in the database:

# 6. Maps

We have the following **5 maps** in the database:

# 7. References

# 8. Sage examples