I recently posted a question regarding placing $6$ distinguishable balls into $4$ indistinguishable boxes. In summary I feel somewhat certain that the solution to that question is $$\sum_{r=0}^{4}S(6,r)=187$$ Where $S(n,k)$ is The Stirling numbers of the second kind.
To continue I wished to find the number of combinations if the boxes also where distinguishable; for which I came up with $$\sum_{r=0}^{4}\frac{4!}{(4-r)!}S(6,r)=4096$$ At first i thougt the $4096=2^{12}$ was a coincidence but: $$\begin{align*}\sum_{r=0}^{4}\frac{4!}{(4-r)!}S(7,r)=16384=2^{14}\\ \sum_{r=0}^{4}\frac{4!}{(4-r)!}S(8,r)=65536=2^{16}\end{align*}\\ \sum_{r=0}^{4}\frac{4!}{(4-r)!}S(9,r)=262144=2^{18} $$ So my question is if $$\sum_{r=0}^{4}\frac{4!}{(4-r)!}S(m,r)=2^{2m}$$ always holds and if it relates to combinatorics in some nice way?
Yes. Assume $x\in \mathbb{Z}$(you can even do it for $x$ general by using falling factorials). In general $$x^m=\sum _{r=0}^mS(m,r)\cdot \frac{x!}{(x-r)!},$$ This is because $x^m$ counts the number of functions from $[m]$ to $[x]$ where $[n]=\{1,2,3,\cdots ,n\}$(which is like assigning balls to bins, the balls are the domain and the bins are the codomain) and every function can be decomposed in an injective function(Notice that if you just allow 1 ball per bin you can count it in $x!/(x-r)!=\binom{x}{r}r!$ ways, which represent choosing the bins and permuting all possibilities of assignments of bins and balls) and a partition of the balls. Check that basically you put balls together in groups and then you put them in the bins.
Your particular question is for $x=4.$