Set of unordered set partitions

Definition

For any integer $n$, the set of unordered set partitions for size $n$ is defined as follows: take any set of size $n$, and consider all the partition of this set into subsets (with no ordering among or between the subsets). This set is termed the set of unordered set partitions for size $n$.

The cardinality of this set is termed the Bell number for $n$ and is denoted as $B_n$. Thus, we shall also call the set of unordered set partitions as the Bell set and denote it as $Bell(n)$. If we want to focus on the set itself, we write $Bell(S)$ where $S$ is the set.

Facts

Independent of the choice of set

Give two sets $A$ and $B$ of the same cardinality, and a bijection $f:A\to B$, we get an induced bijcetion from the set of unordered set partitions of $A$ to the set of unordered set partitions of $B$. Thus, the set of unordered set partitions is independent of the choice of labelling.

Further, this also shows that the symmetric group on a set acts on its set of unordered set partitions, by permuting the labels.

Map from the symmetric group

To every element of the symmetric group there is a corresponding unordered set partition. In other words, there is a natural map, for any set $S$:

$Pr:Sym(S)\to Bell(S)$

which takes as input a permutation and outputs a set partition as follows. It looks at te cycle decomposition of the permutation, and for each cycle, picks the corresponding subset, forgetting the cyclic ordering. For instance, the permutation with cycle decomposition $(135)(24)$ gives rise to the unordered set partition into subsets $\{1,3,5\}$ and $\{2,4\}$

Map to the set of unordered integer partitions

To every unordered set partition, we can associate a corresponding unordered integer partition, which basically just sends each subset to its size. For instance, an unordered set partition into one subset of size 2, and two subsets of size 3, gives an unordered integer partition $2+3+3$.

More formally we get a map:

$Bell(S)\to Part(|S|)$

where $Part(n)$ denotes theset of unordered integer partitions of the integer $n$.

Note that the composite of the map from $Sym(S)$ to $Bell(S)$ and the map from $Bell(S)$ to $Part(|S|)$ is the cycle type map.

Map from the set of ordered set partitions

Given an ordered set partition, we can obtain from that an unordered set partition, by forgetting the ordering.

All these maps are covariant under the action of the symmetric group

The symmetric group acts on itself by conjugation, as well as on the set of ordered as well as unordered set partitions. Its action on the set of unordered integer partitions is trivial. All the maps between these combinatorial structures described above, are covariant under the action of the symmetric group, viz they commute with the action.

Decompositions of this set

Number of parts map

Given any unordered integer partition, we can define the number of parts of that partition. Composing this with the map from unordered set partitions, we get a map:

$Bell(S)\to \{1,2,3,\dots ,n\}$

which sends each unordered set partition to the number of subsets.

The inverse image of an integer $k$ under this map is termed the Stirling set