# 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 94 statistics in the database:

St000105
Set partitions ⟶ ℤ
The number of blocks in the set partition.
St000163
Set partitions ⟶ ℤ
The size of the orbit of the set partition under rotation.
St000211
Set partitions ⟶ ℤ
The rank of the set partition.
St000229
Set partitions ⟶ ℤ
Sum of the difference between the maximal and the minimal elements of the blocks ....
St000230
Set partitions ⟶ ℤ
Sum of the minimal elements of the blocks of a set partition.
St000231
Set partitions ⟶ ℤ
Sum of the maximal elements of the blocks of a set partition.
St000232
Set partitions ⟶ ℤ
The number of crossings of a set partition.
St000233
Set partitions ⟶ ℤ
The number of nestings of a set partition.
St000247
Set partitions ⟶ ℤ
The number of singleton blocks of a set partition.
St000248
Set partitions ⟶ ℤ
The number of anti-singletons of a set partition.
St000249
Set partitions ⟶ ℤ
The number of singletons (St000247) plus the number of antisingletons (St000248) ....
St000250
Set partitions ⟶ ℤ
The number of blocks (St000105) plus the number of antisingletons (St000248) of a....
St000251
Set partitions ⟶ ℤ
The number of nonsingleton blocks of a set partition.
St000253
Set partitions ⟶ ℤ
The crossing number of a set partition.
St000254
Set partitions ⟶ ℤ
The nesting number of a set partition.
St000490
Set partitions ⟶ ℤ
The intertwining number of a set partition.
St000491
Set partitions ⟶ ℤ
The number of inversions of a set partition.
St000492
Set partitions ⟶ ℤ
The rob statistic of a set partition.
St000493
Set partitions ⟶ ℤ
The los statistic of a set partition.
St000496
Set partitions ⟶ ℤ
The rcs statistic of a set partition.
St000497
Set partitions ⟶ ℤ
The lcb statistic of a set partition.
St000498
Set partitions ⟶ ℤ
The lcs statistic of a set partition.
St000499
Set partitions ⟶ ℤ
The rcb statistic of a set partition.
St000502
Set partitions ⟶ ℤ
The number of successions of a set partitions.
St000503
Set partitions ⟶ ℤ
The maximal difference between two elements in a common block.
St000504
Set partitions ⟶ ℤ
The cardinality of the first block of a set partition.
St000505
Set partitions ⟶ ℤ
The biggest entry in the block containing the 1.
St000554
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,2},{3}} in a set partition.
St000555
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,3},{2}} in a set partition.
St000556
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} in a set partition.
St000557
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} in a set partition.
St000558
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,2}} in a set partition.
St000559
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,3},{2,4}} in a set partition.
St000560
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,2},{3,4}} in a set partition.
St000561
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,2,3}} in a set partition.
St000562
Set partitions ⟶ ℤ
The number of internal points of a set partition.
St000563
Set partitions ⟶ ℤ
The number of overlapping pairs of blocks of a set partition.
St000564
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2}} in a set partition.
St000565
Set partitions ⟶ ℤ
The major index of a set partition.
St000572
Set partitions ⟶ ℤ
The dimension exponent of a set partition.
St000573
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2}} such that 1 is a singleton and 2 ....
St000574
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2}} such that 1 is a minimal and 2 a ....
St000575
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2}} such that 1 is a maximal element ....
St000576
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2}} such that 1 is a maximal and 2 a ....
St000577
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2}} such that 1 is a maximal element.....
St000578
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2}} such that 1 is a singleton.
St000579
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2}} such that 2 is a maximal element.....
St000580
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 2 is minimal, 3 is m....
St000581
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,3},{2}} such that 1 is minimal, 2 is ma....
St000582
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,3},{2}} such that 1 is minimal, 3 is ma....
St000583
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 3 is minimal, 1,2 ar....
St000584
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 1 is minimal, 3 is m....
St000585
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,3},{2}} such that 2 is maximal, (1,3) a....
St000586
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 2 is minimal.
St000587
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 1 is minimal.
St000588
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 1,3 are minimal, 2 i....
St000589
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 1 is maximal, (2,3) a....
St000590
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 2 is minimal, 1 is ma....
St000591
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 2 is maximal.
St000592
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 1 is maximal.
St000593
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 1,2 are minimal.
St000594
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,3},{2}} such that 1,2 are minimal, (1,3....
St000595
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 1 is minimal.
St000596
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 3 is minimal, 1 is m....
St000597
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 2 is minimal, (2,3) a....
St000598
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 1,2 are minimal, 3 is....
St000599
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that (2,3) are consecutive....
St000600
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,3},{2}} such that 1 is minimal, (1,3) a....
St000601
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 1,2 are minimal, (2,3....
St000602
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,3},{2}} such that 1 is minimal.
St000603
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 2,3 are minimal.
St000604
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 3 is minimal, 2 is m....
St000605
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 3 is maximal, (2,3) a....
St000606
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 1,3 are maximal, (2,3....
St000607
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 2 is minimal, 3 is ma....
St000608
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 1,2 are minimal, 3 i....
St000609
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 1,2 are minimal.
St000610
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,3},{2}} such that 2 is maximal.
St000611
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 1 is maximal.
St000612
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 1 is minimal, (2,3) a....
St000613
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1,3},{2}} such that 2 is minimal, 3 is ma....
St000614
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2,3}} such that 1 is minimal, 3 is ma....
St000615
Set partitions ⟶ ℤ
The number of occurrences of the pattern {{1},{2},{3}} such that 1,3 are maximal.
St000695
Set partitions ⟶ ℤ
The number of blocks in the first part of the atomic decomposition of a set parti....
St000728
Set partitions ⟶ ℤ
The dimension of a set partition.
St000729
Set partitions ⟶ ℤ
The minimal arc length of a set partition.
St000730
Set partitions ⟶ ℤ
The maximal arc length of a set partition.
St000747
Set partitions ⟶ ℤ
A variant of the major index of a set partition.
St000748
Set partitions ⟶ ℤ
The major index of the permutation obtained by flattening the set partition.
St000793
Set partitions ⟶ ℤ
The length of the longest partition in the vacillating tableau corresponding to a....
St000823
Set partitions ⟶ ℤ
The number of unsplittable factors of the set partition.
St000839
Set partitions ⟶ ℤ
The largest opener of a set partition.
St000925
Set partitions ⟶ ℤ
The number of topologically connected components of a set partition.
St000971
Set partitions ⟶ ℤ
The smallest closer of a set partition.

# 6. Maps

We have the following 8 maps in the database:

Mp00079
Set partitions ⟶ Integer partitions
shape
Mp00080
Set partitions ⟶ Permutations
to permutation
Mp00091
Set partitions ⟶ Set partitions
Cyclic rotation
Mp00092
Perfect matchings ⟶ Set partitions
to set partition
Mp00112
Set partitions ⟶ Set partitions
reverse
Mp00115
Set partitions ⟶ Set partitions
Kasraoui-Zeng
Mp00128
Set partitions ⟶ Integer compositions
to composition
Mp00138
Dyck paths ⟶ Set partitions
to noncrossing partition