How can I count the number of partitions of S with exactly n parts?

1.9k Views Asked by At

If I have a set $S$ of $n$ elements, is there a way to find the number of partitions of that set with $k$ "parts/cells"?

For example, if set $S = \{a, b, c, d\}$, there are 15 total partitions of that set, and 6 of them have 3 parts/cells:

$$ [\{a\}, \{b\}, \{c, d\}]\\ [\{a\}, \{c\}, \{b, d\}]\\ [\{a\}, \{d\}, \{b, c\}]\\ [\{b\}, \{c\}, \{a, d\}]\\ [\{b\}, \{d\}, \{a, c\}]\\ [\{c\}, \{d\}, \{a, b\}] $$

1

There are 1 best solutions below

0
On

This is the number of orbits of surjective functions $[k]\leftarrow[n]$ under (composition on the left with) permutations of the elements of $[k]$ (since the parts are not explicitly labeled). Here $[i]$ denotes your favorite $i$-element set, for $i\in\Bbb N$. As such this problem is contained in the Twelvefold Way.