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,\ldots ,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] of the second kind] and is cardinality is termed the Stirling number of the second kind $S(n,k)$. Note that:

• The inverse image of this in the symmetric group is the Stirling set of the first kind which is the set of all permutations having exactly $k$ cycles.
• The forward image of this in theset of unordered integer partitions is the set of partitions into $k$ parts

Number of singletons map

Given an unordered integer partition, we can count the number of times 1 occurs as a part. Composing this with the map from unordered set partitions to unordered integer partitions, we get a map that counts the number of singletons in a partition of a set into subsets.

APS structure

Bell sets form an IAPS

Given two disjoint sets $A$ and $B$, there is a natural injective map:

$Bell(A)\times Bell(B)\to Bell(A\cup B)$

Which partitions the $A$-part according to the component coming from $Bell(A)$ and the $B$-part according to the component coming from $Bell(B)$.

This thus defines maps:

$Bell(m)\times Bell(n)\to Bell(m+n)$

Under these maps the Bell sets form an injective APS. In particular this also shows that the cardinalities of the Bell numbers grow faster than exponentially.

The map from the symmetric group is a map of IAPSes

We know that there is a natural map:

$Sym(A)\times Sym(B)\to Sym(A\cup B)$

this commutes with the maps sending $Sym$ to $Bell$. Thus the map from $Sym$ to $Bell$ is a map of IAPSes.

The map to unordered integer partitions is a map of APSes

We can give an APS structure to unordered integer partitions; however, this APS structure is not injective. The fact that we cannot give an injective structure is clear from the observation that the number of unordered integer partitions grows subexponentially.

The map from $Bell$ to $Part$ is a map of APSes, viz it is compatible with the block concatenation.

Analogues

The role that unordered set partitions play in the context of the symmetric group, is played by unordered direct sum decompositions when we are working with the orthogonal group over a field.