Find a closed formula for $\,\mathrm{S}\left(m,4\right)$ ?.
Attempt: I know the recurrence relation for $\,\mathrm{S}\left(m,k\right)$. I know how to find $\,\mathrm{S}\left(m,2\right)$ which is the subsets of $\left[m\right]$, then remove the over counting. We get ${2^{m}\,\, -\,\, 2 \over 2}$.
It seems tedious to use the recurrence equation twice. Is there a better way to solve this ?.
You want to count the ways to partition the integers $1$ through $n$ into $4$ non-empty unlabelled sets. You can do this with an inclusion-exclusion argument.
For now we’ll label the $4$ sets, say $1,2,3$, and $4$. There are altogether $4^n$ ways to assign the members of $[n]=\{1,\ldots,n\}$ to these $4$ sets, but this includes the ways that leave one or more of the sets empty. There are $3^n$ assignments that leave set $1$ empty, $3^n$ that leave set $2$ empty, $3^n$ that leave set $3$ empty, and $3^n$ that leave set $4$ empty, so for a second approximation we should subtract $4\cdot 3^n$, leaving $4^n-4\cdot3^n$ assignments. However, any assignment that leaves both set $1$ and set $2$ empty has now been counted once in the original $4^n$ and subtracted twice in the $4\cdot3^n$; we don’t want to count such assignments, so we need to add them back in to give each of them a net count of $0$. There are $2^n$ assignments that leave both set $1$ and set $2$ empty, so we need to add $2^n$. We need to do that for each of the $\binom42=6$ pairs of sets, so our next approximation is
$$4^n-4\cdot3^n+6\cdot2^n\;.\tag{1}$$
Now consider an assignment that leaves $3$ of the four sets empty; obviously it assigns every member of $[n]$ to the remaining set, so there are $4$ such assignments. How often does $(1)$ count each of them? It counts each one once in the first term, $-3$ times altogether in the second term, and $\binom32=3$ times in the third term, for a net total of $1$ time. We don’t want to count these $4$ assignments at all, so we have to subtract them once each: there are altogether
$$4^n-4\cdot3^n+6\cdot2^n-4\tag{2}$$
assignments that leave none of the four sets empty.
Finally, the Stirling number of the second kind actually counts such assignments to unlabelled sets. Putting $1$ into set $1$, $2$ into set $2$, $3$ into set $3$, and the rest of $[n]$ into set $4$ is the same partition into unlabelled sets as putting $1$ into set $3$, $2$ into set $4$, $3$ into set $2$, and the rest of $[n]$ into set $1$. Since there are $4!=24$ permutations of the $4$ labels, we’ve counted each partition into unlabelled sets $24$ times, and we must therefore divide $(2)$ by $4!=24$. The final result:
$$S(n,4)=\frac{4^n-4\cdot3^n+6\cdot2^n-4}{24}$$