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:

The number of blocks in the set partition.
The size of the orbit of the set partition under rotation.
The rank of the set partition.
Sum of the difference between the maximal and the minimal elements of the blocks ....
Sum of the minimal elements of the blocks of a set partition.
Sum of the maximal elements of the blocks of a set partition.
The number of crossings of a set partition.
The number of nestings of a set partition.
The number of singleton blocks of a set partition.
The number of anti-singletons of a set partition.
The number of singletons (St000247) plus the number of antisingletons (St000248) ....
The number of blocks (St000105) plus the number of antisingletons (St000248) of a....
The number of nonsingleton blocks of a set partition.
The crossing number of a set partition.
The nesting number of a set partition.
The intertwining number of a set partition.
The number of inversions of a set partition.
The rob statistic of a set partition.
The los statistic of a set partition.
The rcs statistic of a set partition.
The lcb statistic of a set partition.
The lcs statistic of a set partition.
The rcb statistic of a set partition.
The number of successions of a set partitions.
The maximal difference between two elements in a common block.
The cardinality of the first block of a set partition.
The biggest entry in the block containing the 1.
The number of occurrences of the pattern {{1,2},{3}} in a set partition.
The number of occurrences of the pattern {{1,3},{2}} in a set partition.
The number of occurrences of the pattern {{1},{2,3}} in a set partition.
The number of occurrences of the pattern {{1},{2},{3}} in a set partition.
The number of occurrences of the pattern {{1,2}} in a set partition.
The number of occurrences of the pattern {{1,3},{2,4}} in a set partition.
The number of occurrences of the pattern {{1,2},{3,4}} in a set partition.
The number of occurrences of the pattern {{1,2,3}} in a set partition.
The number of internal points of a set partition.
The number of overlapping pairs of blocks of a set partition.
The number of occurrences of the pattern {{1},{2}} in a set partition.
The major index of a set partition.
The dimension exponent of a set partition.
The number of occurrences of the pattern {{1},{2}} such that 1 is a singleton and 2 ....
The number of occurrences of the pattern {{1},{2}} such that 1 is a minimal and 2 a ....
The number of occurrences of the pattern {{1},{2}} such that 1 is a maximal element ....
The number of occurrences of the pattern {{1},{2}} such that 1 is a maximal and 2 a ....
The number of occurrences of the pattern {{1},{2}} such that 1 is a maximal element.....
The number of occurrences of the pattern {{1},{2}} such that 1 is a singleton.
The number of occurrences of the pattern {{1},{2}} such that 2 is a maximal element.....
The number of occurrences of the pattern {{1},{2},{3}} such that 2 is minimal, 3 is m....
The number of occurrences of the pattern {{1,3},{2}} such that 1 is minimal, 2 is ma....
The number of occurrences of the pattern {{1,3},{2}} such that 1 is minimal, 3 is ma....
The number of occurrences of the pattern {{1},{2},{3}} such that 3 is minimal, 1,2 ar....
The number of occurrences of the pattern {{1},{2},{3}} such that 1 is minimal, 3 is m....
The number of occurrences of the pattern {{1,3},{2}} such that 2 is maximal, (1,3) a....
The number of occurrences of the pattern {{1},{2,3}} such that 2 is minimal.
The number of occurrences of the pattern {{1},{2},{3}} such that 1 is minimal.
The number of occurrences of the pattern {{1},{2},{3}} such that 1,3 are minimal, 2 i....
The number of occurrences of the pattern {{1},{2,3}} such that 1 is maximal, (2,3) a....
The number of occurrences of the pattern {{1},{2,3}} such that 2 is minimal, 1 is ma....
The number of occurrences of the pattern {{1},{2},{3}} such that 2 is maximal.
The number of occurrences of the pattern {{1},{2},{3}} such that 1 is maximal.
The number of occurrences of the pattern {{1},{2},{3}} such that 1,2 are minimal.
The number of occurrences of the pattern {{1,3},{2}} such that 1,2 are minimal, (1,3....
The number of occurrences of the pattern {{1},{2,3}} such that 1 is minimal.
The number of occurrences of the pattern {{1},{2},{3}} such that 3 is minimal, 1 is m....
The number of occurrences of the pattern {{1},{2,3}} such that 2 is minimal, (2,3) a....
The number of occurrences of the pattern {{1},{2,3}} such that 1,2 are minimal, 3 is....
The number of occurrences of the pattern {{1},{2,3}} such that (2,3) are consecutive....
The number of occurrences of the pattern {{1,3},{2}} such that 1 is minimal, (1,3) a....
The number of occurrences of the pattern {{1},{2,3}} such that 1,2 are minimal, (2,3....
The number of occurrences of the pattern {{1,3},{2}} such that 1 is minimal.
The number of occurrences of the pattern {{1},{2},{3}} such that 2,3 are minimal.
The number of occurrences of the pattern {{1},{2},{3}} such that 3 is minimal, 2 is m....
The number of occurrences of the pattern {{1},{2,3}} such that 3 is maximal, (2,3) a....
The number of occurrences of the pattern {{1},{2,3}} such that 1,3 are maximal, (2,3....
The number of occurrences of the pattern {{1},{2,3}} such that 2 is minimal, 3 is ma....
The number of occurrences of the pattern {{1},{2},{3}} such that 1,2 are minimal, 3 i....
The number of occurrences of the pattern {{1},{2,3}} such that 1,2 are minimal.
The number of occurrences of the pattern {{1,3},{2}} such that 2 is maximal.
The number of occurrences of the pattern {{1},{2,3}} such that 1 is maximal.
The number of occurrences of the pattern {{1},{2,3}} such that 1 is minimal, (2,3) a....
The number of occurrences of the pattern {{1,3},{2}} such that 2 is minimal, 3 is ma....
The number of occurrences of the pattern {{1},{2,3}} such that 1 is minimal, 3 is ma....
The number of occurrences of the pattern {{1},{2},{3}} such that 1,3 are maximal.
The number of blocks in the first part of the atomic decomposition of a set parti....
The dimension of a set partition.
The minimal arc length of a set partition.
The maximal arc length of a set partition.
A variant of the major index of a set partition.
The major index of the permutation obtained by flattening the set partition.
The length of the longest partition in the vacillating tableau corresponding to a....
The number of unsplittable factors of the set partition.
The largest opener of a set partition.

# 6. Maps

We have the following 5 maps in the database:

shape
to permutation
Cyclic rotation
reverse
Kasraoui-Zeng

# 8. Sage examples

SetPartitions (last edited 2015-10-30 15:50:50 by ChristianStump)