How many different ways do there exist to split the set $A=\{1,2,…,n\}$ into at most $m$ non-empty disjoint subsets, whose union is $A$.
For example, if $m=3$ then we have the following:
$n=1: \quad$ there is only 1 such subset;
$n=2: \quad$ we have the following possible splittings:
$\quad\quad\quad\quad\big\{\{1\}, \{2\}\big\}, \big\{\{1,2\}\big\}$ – $2$ in total;
$n=3: \quad$ we have the following possible splittings:
$\quad\quad\quad\quad\big\{\{1\}, \{2\},\{3\}\big\}, \big\{\{1,2\}, \{3\}\big\}, \big\{\{1,3\}, \{2\}\big\}, \big\{\{1\}, \{2,3\}\big\}, \big\{\{1,2,3\}\big\}$ – $5$ in total.
Best Answer
Let $S(n,k)$ be the so-called Stirling number of the second kind which is the number of ways to partition a set of $n$ objects into exactly $k$ non-empty subsets. Hence the number of ways to split the set $\{1,2,...,n\}$ into at most $m$ non-empty disjoint subsets, whose union is $A$ is $$\sum_{k=0}^m S(n,k)=\sum_{k=0}^m\frac{1}{k!}\sum_{j=0}^k (-1)^j\binom{k}{j}(k-j)^n.$$
.