Proof that
$k^n = \sum_{j=1}^{k}\binom{k}{j}j!S(n,j)$
To justify this last equality you have to consider, firstly, that if $X$ and $Y$ are two sets with $n$ and $k$ elements, respectively, then there are $k^{n}$ applications of $X$ and $Y$. To reach the equality it have to use that these applications can be constructed in the following way: the images of the elements of X are a series of elements of Y, say j of them, where $1\leq j\leq k$ (the rest will not have preimage). Then, first, we decided that elements of Y have preimagenes and, once decided that the elements "arrives" the application, it only remains to build a suprayective application that has only these elements as an image. This is the process that should lead to the desired formula.