1
$\begingroup$

Find a closed form for $a_n:=\sum_{k=0}^{n}\binom{n}{k}(n-k)^n(-1)^k$ using generating functions.

  • 5
    With that tone of question, it might help if you showed us what you have tried.2012-06-27
  • 0
    @akotronis: (+1) for the interesting question.2012-06-28

2 Answers 2

4

We have $$\begin{eqnarray*} \sum_{k=0}^{n}(-1)^k \binom{n}{k}(n-k)^n &=& \sum_{k=0}^{n}(-1)^k \binom{n}{n-k}(n-k)^n \\ &=& \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} k^n \\ &=& \left.\sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} (x D)^n x^k\right|_{x=1} \\ &=& \left.(x D)^n \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} x^k\right|_{x=1} \\ &=& \left.(x D)^n (x-1)^n\right|_{x=1}, \end{eqnarray*}$$ where $D = \partial/\partial x$. But $$(x D)^n = x^n D^n + (\mathrm{const}) x^{n-1}D^{n-1} + \ldots.$$ and $D^k(x-1)^n|_{x=1} = 0$ unless $k\ge n$. Therefore, $\left.(x D)^n (x-1)^n\right|_{x=1} = D^n(x-1)^n|_{x=1} = n!,$ and so $$\begin{equation*} \sum_{k=0}^{n}(-1)^k \binom{n}{k}(n-k)^n = n!.\tag{1} \end{equation*}$$


The argument above immediately implies that $$\sum_{k=0}^{n}(-1)^k \binom{n}{k}(n-k)^m = 0$$ if $m\in\mathbb{N}$ and $m. It also gives us a method to calculate the sum for $m>n$. Sums of this type are related to the Stirling numbers of the second kind, $$\begin{eqnarray*} \sum_{k=0}^{n}(-1)^k \binom{n}{k}(n-k)^m &=& \sum_{k=0}^{n}(-1)^{n-k} \binom{n}{k}k^m \\ &=& n! \left\{m\atop n\right\}. \end{eqnarray*}$$ The operator $(x D)^n$ and it's connection to the Stirling numbers has been discussed here.

0

Suppose we are trying to evaluate $$\sum_{k=0}^n {n\choose k} (n-k)^n (-1)^k.$$

Observe that $$(n-k)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n-k)z) \; dz.$$

This gives for the sum the integral $$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{k=0}^n {n\choose k} (-1)^k \exp((n-k)z) \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \left(-1+\exp(z)\right)^n \; dz.$$

Now we have $$[z^n] \left(-1+\exp(z)\right)^n = 1$$ by inspection, which then gives $$n!$$ for the sum.