Proving Stirling numbers formulas I have two questions that I need to prove. I used induction for proving, which is easy, but I specifically want to prove it with Stirling numbers of the second kind. I know that these are already it's formula but I couldn't match everything in my mind so I want to see that how and why we are writing it like these.
For positive integers $m,n$ with $m < n$ :
$$\sum_{k=0}^n (-1)^k\binom{n}{n-k}(n-k)^m = 0$$
For positive integers $n$ :
$$n! = \sum_{k=0}^n (-1)^k\binom{n}{n-k}(n-k)^n$$

Suppose that we want to count the partitions of $[n]=\{1,2,\ldots,n\}$ into $k$ unlabelled parts. It’s a little easier to count the partitions of $[n]$ into $k$ labelled parts, so let’s start with that. If we label the parts $1,2,\ldots,k$, a partition of $[n]$ into these parts is essentially a surjection $f:[n]\to[k]$: for each $i\in[n]$, $f(i)$ is the number of the part containing $i$. Thus, we are in effect counting the surjections from $[n]$ to $[k]$.
For each $i\in[k]$ let $A_i$ be the set of functions $f:[n]\to[k]$ such that $i$ is not in the range of $f$. The surjective functions from $[n]$ to $[k]$ are the ones that are not in any of the sets $A_i$ with $i\in[k]$.
Suppose that $\varnothing\ne I\subseteq[k]$; how many functions from $[n]$ to $[k]$ are in $\bigcap_{i\in I}A_i$? A function $f:[n]\to[k]$ is in $\bigcap_{i\in I}A_i$ if and only if $f(i)\in[k]\setminus I$ for each $i\in[n]$. In other words, $\bigcap_{i\in I}A_i$ is the set of functions from $[n]$ to $[k]\setminus I$, and there are $(k-|I|)^n$ of those, so
$$\left|\bigcap_{i\in I}A_i\right|=(k-|I|)^n\;.$$
It follows from the inclusion-exclusion principle that
$$\begin{align*}
\left|\bigcup_{i\in[k]}A_i\right|&=\sum_{\varnothing\ne I\subseteq[k]}(-1)^{|I|+1}\left|\bigcap_{i\in I}A_i\right|\\
&=\sum_{j=1}^k(-1)^{j+1}\binom{k}j(k-j)^n\;,
\end{align*}$$
since there are $\binom{k}j$ subsets of $[k]$ of cardinality $j$. There are altogether $k^n$ functions from $[n]$ to $[k]$, so there are
$$\begin{align*}
k^n-\sum_{j=1}^k(-1)^{j+1}\binom{k}j(k-j)^n&=k^n+\sum_{j=1}^k(-1)^j\binom{k}j(k-j)^n\\
&=\sum_{j=0}^k(-1)^j\binom{k}j(k-j)^n
\end{align*}$$
surjections from $[n]$ to $[k]$ and the same number of partitions of $[n]$ into $k$ labelled parts.
Finally, each partition of $[n]$ into $[k]$ unlabelled parts corresponds to $k!$ partitions of $[n]$ into $[k]$ labelled parts, since we can label the $k$ parts in $k!$ different orders. Thus,
$${n\brace k}=\frac1{k!}\sum_{j=0}^k(-1)^j\binom{k}j(k-j)^n\;.$$
This is of course $0$ when $n>k$ and $1$ when $n=k$.
