How to find the number of inequivalent partitions of the powerset of a set of $n$ elements

41 Views Asked by At

Consider the partitions of the powerset of $\{1,2,\cdots,n\}$, which are the sets of the form $\mathcal{A}=\{S_\lambda:\lambda\in\Lambda\}$, where each $S_\lambda$ is nonempty, $S_\lambda$ and $S_{\lambda'}$ are disjoint for distinct $\lambda$ and $\lambda'$, and $\displaystyle\bigcup_{\lambda\in I}S_\lambda = \mathcal{P}(\{1,2,\cdots,n\})$. Two partitions $\mathcal{A}$ and $\mathcal{B}$ are called equivalent if they are the same after relabelling of elements, that is to say, if there exists a bijection $\varphi:\{1,2,\cdots,n\}\to\{1,2,\cdots,n\}$ such that $$ \mathcal{B} = \{\{\varphi(i):i\in S\}:S\in\mathcal{A}\}. $$ For example, for $n=2$, the following pairs of partitions of $\mathcal{P}(\{1,2\})$ are equivalent:

$\bullet$ $\{\{\{1\}\}\}, \{\emptyset, \{2\}, \{1,2\}\}\}$ and $\{\{\{2\}\}\}, \{\emptyset, \{1\}, \{1,2\}\}\}$;

$\bullet$ $\{\{\{1\}\}\}, \{\emptyset\}, \{\{2\}, \{1,2\}\}\}$ and $\{\{\{2\}\}\}, \{\emptyset\}, \{\{1\}, \{1,2\}\}\}$;

$\bullet$ $\{\{\{1\}\}\}, \{\{1,2\}\}, \{\emptyset, \{2\}\}\}$ and $\{\{\{2\}\}\}, \{\{1,2\}\}, \{\emptyset, \{1\}\}\}$;

$\bullet$ $\{\{\emptyset, \{1\}\}, \{\{2\}, \{1,2\}\}\}$ and $\{\{\emptyset, \{2\}\}, \{\{1\}, \{1,2\}\}\}$.

Since the number of ways to partition a set of $2^2=4$ labeled elements is $15$, we obtain $11$ inequivalent partitions of $\mathcal{P}(\{1,2\})$. It seems that finding the answer for $n=3$ would be exhausting, because there are $4140$ partitions of a set of $2^3=8$ labeled elements.

I'm not asking to find an answer for general $n$; on the other hand, I was wondering that if the question can be converted into a more well-known or more well studied problem. Also, is there a clever way to calculate the answer for $n=3$?