Simplifying $\sum_{r = 0}^{n} {{n}\choose{r}}r^k(-1)^r$ Is there any way that I could simplify the following expression?
$$\sum_{r = 0}^{n} {{n}\choose{r}}r^k(-1)^r$$ 
where $n,k$ are natural numbers (and in my particular problem, $k \gg n$, so maybe some sort of asymptotic behaviour?)
I tried finding some sort of generating function (without any luck, though I haven't really learnt much about them yet), looking at differences between terms, but I haven't really been able to make any progress whatsoever. 
 A: The defining equation for Stirling numbers of the second kind is
$$
\newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}}
\sum_{j=0}^n\stirtwo{k}{j}\binom{r}{j}j!=r^k\tag{1}
$$
Thus,
$$
\begin{align}
\sum_{r=0}^n\binom{n}{r}r^k(-1)^r
&=\sum_{r=0}^n\binom{n}{r}\sum_{j=0}^n\stirtwo{k}{j}\binom{r}{j}j!(-1)^r\\
&=\sum_{j=0}^n\stirtwo{k}{j}\sum_{r=0}^n\binom{n}{r}\binom{r}{j}j!(-1)^r\\
&=\sum_{j=0}^n\stirtwo{k}{j}\frac{n!}{(n-j)!}\sum_{r=0}^n\binom{n-j}{r-j}(-1)^r\\
&=\sum_{j=0}^n\stirtwo{k}{j}\frac{n!}{(n-j)!}(-1)^j[n=j]\\
&=(-1)^n\stirtwo{k}{n}n!\tag{2}
\end{align}
$$
A: It’s useful to be comfortable with inclusion-exclusion calculations, so I’ll suggest a different approach.
The summation
$$\sum_{r=0}^n\binom{n}rr^k(-1)^r\tag{1}$$
has exactly the general form that one would expect for an inclusion-exclusion calculation, so one way to simplify it is to work out what it might be counting and see whether there’s some simpler way to count the same thing.
The $\binom{n}r$ and $(-1)^r$ factors are part of the inclusion-exclusion machinery, so we should focus first on the $r^k$ factor. It’s the number of functions from $[k]$ to $[r]$. The largest value of $r$ is $n$; what if we’re trying to count the surjections from $[k]$ to $[n]$? (This guess is easier to make if one has had some experience with such arguments.) There are altogether $n^k$ functions from $[k]$ to $[n]$; we want to subtract the number of functions that are not surjections.
For each $i\in[n]$ let $A_i$ be the set of functions from $[k]$ to $[n]$ whose ranges do not include $i$. If $\varnothing\ne I\subseteq[n]$, it’s not hard to see that
$$\left|\,\bigcap_{i\in I}A_i\,\right|=(n-|I|)^k$$
and hence that
$$\begin{align*}
\left|\,\bigcup_{i=1}^nA_i\,\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|-1}\left|\,\bigcap_{i\in I}A_i\,\right|\\
&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|-1}(n-|I|)^k\\
&=\sum_{\ell=1}^n\binom{n}\ell(-1)^{r-1}(n-\ell)^k\;.
\end{align*}$$
This is the number of non-surjective functions from $[k]$ to $[n]$, so we want
$$\begin{align*}
n^k-\sum_{\ell=1}^n\binom{n}\ell(-1)^{\ell-1}(n-\ell)^k&=n^k+\sum_{\ell=1}^n\binom{n}\ell(-1)^\ell(n-\ell)^k\\
&=\sum_{\ell=0}^n\binom{n}\ell(-1)^\ell(n-\ell)^k\\
&=\sum_{\ell=0}^n\binom{n}{n-\ell}(-1)^\ell(n-\ell)^k\\
&=\sum_{r=0}^n\binom{n}r(-1)^{n-r}r^k\\
&=(-1)^n\sum_{r=0}^n\binom{n}r(-1)^{-r}r^k\\
&=(-1)^n\sum_{r=0}^n\binom{n}r(-1)^rr^k\;.
\end{align*}$$
In other words, the original summation $(1)$ is $(-1)^n$ times the number of surjections from $[k]$ to $[n]$.
On the other hand, there are ${k\brace n}$ ways to partition $[k]$ into $n$ parts1, where ${k\brace n}$ is a Stirling number of the second kind, and those $n$ parts can then be assigned to the elements of $[n]$ in $n!$ different ways, so there are $n!{k\brace n}$ surjections from $[k]$ to $[n]$. Thus,
$$\sum_{r=0}^n\binom{n}rr^k(-1)^r=(-1)^nn!{k\brace n}\;.$$
1 Unlike robjohn, I take this as the definition of the Stirling numbers of the second kind; for me his defining relation is a derived result.
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\mrm}[1]{\,\mathrm{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\color{#f00}{\sum_{r = 0}^{n}{n \choose r}r^{k}\,\pars{-1}^{r}} & =
\sum_{r = 0}^{n}{n \choose r}\pars{-1}^{r}\ \overbrace{%
\pars{k!\oint_{\verts{z} = 1}{\expo{rz} \over z^{k + 1}}
\,{\dd z \over 2\pi\ic}}}^{\ds{r^{k}}}
\\[5mm] & =
k!\oint_{\verts{z} = 1}{1 \over z^{k + 1}}
\sum_{r = 0}^{n}{n \choose r}\pars{-\expo{z}}^{r}\,{\dd z \over 2\pi\ic} =
k!\oint_{\verts{z} = 1}{\pars{1 - \expo{z}}^{n} \over z^{k + 1}}
\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\pars{-1}^{n}\, k!\oint_{\verts{z} = 1}
{\pars{\expo{z} - 1}^{n} \over z^{k + 1}}\,{\dd z \over 2\pi\ic}\tag{1}
\end{align}

However
$$
\pars{\expo{z} - 1}^{n} =
n!\sum_{m = n}^{\infty}\mrm{S}\pars{m,n}\,{z^{m} \over m!} 
$$
where $\ds{\mrm{S}\pars{m,n}}$ is a Stirling Number of the Second Kind ( see identity $\pars{13}$ in a
Stirling Number of the Second Kind page ).
Expression $\ds{\pars{1}}$ is reduced to:
\begin{align}
\color{#f00}{\sum_{r = 0}^{n}{n \choose r}r^{k}\,\pars{-1}^{r}} & =
\pars{-1}^{n}\, k!\,n!\sum_{m = n}^{\infty}
{\mrm{S}\pars{m,n} \over m!}
\oint_{\verts{z} = 1}{1 \over z^{k - m + 1}}\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\pars{-1}^{n}\, k!\,n!\sum_{m = n}^{\infty}
{\mrm{S}\pars{m,n} \over m!}\,\delta_{k - m,0}\,\,\,\, =\,\,\,
\pars{-1}^{n}\, k!\,n!
\bracks{\mrm{S}\pars{k,n} \over k!}
\\[5mm] & =
\color{#f00}{\pars{-1}^{n}\,\, n!\mrm{S}\pars{k,n}}
\end{align}
