about formulas and identies for Stirling numbers of the second kind

Question

How the two following formulas can be proved (algebraically preferred)? $$\sum_{n=k}^{∞}S\left(n,k\right)\ \frac{x^{n}}{n!}=\frac{1}{k!}\left(e^{x}-1\right)^{k}$$ $$x^{n}=\sum_{m=0}^{n}S\left(n,m\right)\left(x\right)_{m}$$ where $S\left(n,m\right)$ is the Stirling number of the second kind and $\left(x\right)_{m}$ is falling factorial. any Hint or full proof is highly appreciated (since I'm new to this numbers and their relations so a full proof is better).

Answer 1

If you are familiar with combinatorial classes the first equation represents a set of $k$ elements, each of these themselves a set of labeled elements, with a non-zero number of elements (here we are distributing $n$ distinguishable balls into $k$ indistinguishable boxes with no box being empty):

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}_{=k} (\textsc{SET}_{\ge 1}(\mathcal{Z})).$$

The exponential generating function for $\textsc{SET}_{=k}(\mathcal{Z})$ is $$\frac{z^k}{k!}.$$ This yields for set partitions into $k$ sets

$$\frac{1}{k!} \left(\sum_{q=1}^\infty \frac{z^q}{q!}\right)^k = \frac{1}{k!} (\exp(z)-1)^k.$$

This is because in a combinatorial class constructed by distributing a repertoire of source objects into a row of $k$ slots with a group $G$ permuting the slots and creating equivalence classes, the EGF of the class is given by

$$\frac{S(z)^k}{|G|}.$$

where $S(z)$ is the EGF of the source objects. For sets $G$ is the symmetric group and $|G|=k!.$ These combinatorial classes may be nested. Another example are cycles with $|G|=k$ where we get the generating function

$$\sum_{q\ge 1} \frac{z^q}{q} = \log\frac{1}{1-z}$$

for the class of cycles. Of course permutations are sets of cycles and we have

$$n! [z^n] \exp \log\frac{1}{1-z} = n! [z^n] \frac{1}{1-z} = n!.$$

For the second equation we have the following claim where $x$ is a positive integer:

$$x^n = \sum_{m=0}^n {n\brace m} x^{\underline m} = \sum_{m=1}^n {x\choose m} m! {n\brace m}.$$

Suppose we throw $n$ different balls into $x$ different boxes, there are $x^n$ ways of doing this. On the other hand we may classify every distribution of balls obtained in this way by the number $m$ of boxes that were not empty. To get this kind of distribution we choose the $m$ boxes in ${x\choose m}$ ways and partition the $n$ balls into $m$ sets in ${n\brace m}$ ways. These $m$ sets can be matched to the chosen $m$ boxes in $m!$ ways and every such configuration constitutes a distribution of the balls, and we have equality.

Given that LHS and RHS may be viewed as polynomials in $x$ and they are equal at all positive integer values, they are the same polyonmial.