2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.