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$$
 A: 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$.
A: Well $$\left\{{n \atop k}\right\}={\frac  {1}{k!}}\sum _{{j=0}}^{{k}}(-1)^{{k-j}}{\binom  {k}{j}}j^{n}:=\text{ Number of ways to partition $\{1,\cdots,n\}$ in $k$ blocks },$$
For blocks i mean disjoint subsets of $\{1,\cdots ,n\}$ that their union is the whole set.

So $$k!\left\{{n \atop k}\right\}=\sum _{{j=0}}^{{k}}(-1)^{{k-j}}{\binom  {k}{j}}j^{n}=\sum _{{j=0}}^{{k}}(-1)^{{j}}{\binom  {k}{k-j}}(k-j)^{n},$$
So your two equations are $$\text{if $m<n$, then  } n!\left\{{m \atop n}\right\}=0,$$
and $$n!\left\{{n \atop n}\right\}=n!,$$
Think in terms of the partition problem and you will have your answer.
A: For any polynomial $f$, define $\Delta f(x) = f(x+1) - f(x)$. Clearly, if $f$ is of degree $m$, then $\Delta f$ is of degree $m-1$. Now,
\begin{align*}
\Delta^2 f(x)&= \Delta(f(x+1) - f(x)) \\
&= (f(x+2) - f(x+1)) - (f(x+1) - f(x))\\
&= f(x+2) - 2f(x+1) + f(x)
\end{align*}
Continuing, an easy induction shows that
\begin{align*}
\Delta^n f(x) = f(x+n) - \binom{n}{1}f(x+n-1) + \binom{n}{2}f(x+n-2) + \cdots + (-1)^n f(x)
\end{align*}
If $f(x) = x^m$, then for any $n > m$, $\Delta^n f(x) \equiv 0$. The given equality is just an expansion of $\Delta^n f(0)$
