# 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.

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.

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}

$\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}