How to Prove : $\frac{2}{(n+2)!}\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^{n+2}=\frac{n(3n+1)}{12}$

Solution 1:

Here’s a fairly straightforward combinatorial argument. Rewrite the equation as

$$\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^{n+2}=\frac{n(3n+1)(n+2)!}{24}\;.\tag{1}$$

The lefthand side of $(1)$ is an inclusion-exclusion calculation of the number of surjections from $[n+2]$ to $[n]$ (where as usual $[m]=\{1,\ldots,m\}$ for each $m\in\Bbb Z^+$). We now count these surjections in a different way.

If $f:[n+2]\to[n]$ is a surjection, either there is a $k\in[n]$ such that $|f^{-1}[\{k\}]|=3$, or there are distinct $k,\ell\in[n]$ such that $|f^{-1}[\{k\}]|=|f^{-1}[\{\ell\}]|=2$; call these surjections Type $1$ and Type $2$, respectively.

To construct a Type $1$ surjection we first choose $k$ in $n$ ways, then choose $f^{-1}[\{k\}]$ in $\binom{n+2}3$ ways, and then define $f$ on $[n+2]\setminus f^{-1}[\{k\}]$ in $(n-1)!$ ways, for a total of

$$n(n-1)!\binom{n+2}3=\frac{n(n+2)!}{3!}$$

Type $1$ surjections.

To construct a Type $2$ surjection we first choose $k$ and $\ell$ in $\binom{n}2$ ways, then choose the preimage of the smaller of $k$ and $\ell$ in $\binom{n+2}2$ ways, then choose the preimage of the larger of $k$ and $\ell$ in $\binom{n}2$ ways, and finally define the rest of $f$ in $(n-2)!$ ways, for a total of

$$\binom{n}2^2\binom{n+2}2(n-2)!=\frac{n(n-1)(n+2)!}8$$

Type $2$ surjections.

The total number of surjections is therefore

$$\frac{n(n+2)!}6+\frac{n(n-1)(n+2)!}8=\frac{n(3n+1)(n+2)!}{24}\;,$$

as desired.

Solution 2:

Fix $n$ and define $f(x)$ by

$$ f(x) = (1 - e^{-x})^n = \sum_{k=0}^{n} \binom{n}{k} (-1)^k e^{-kx}. $$

Then the left-hand side is equal to

$$ \frac{2}{(n+2)!} f^{(n+2)}(0). $$

So it suffices to find the Taylor polynomial of degree $n+2$ for $f(x)$ at $x = 0$. This can be done as follows:

\begin{align*} f(x) &= x^n \left( \frac{1 - e^{-x}}{x} \right)^n \\ &= x^n \exp\left[ n \log\left( \frac{1 - e^{-x}}{x} \right)\right] \\ &= x^n \exp\left( -\frac{n}{2} x + \frac{n}{24} x^2 + \cdots \right) \\ &= x^n \left( 1 - \frac{n}{2} x + \frac{(3n+1)n}{24} x^2 + \cdots \right) \\ &= x^n - \frac{n}{2} x^{n+1} + \frac{(3n+1)n}{24} x^{n+2} + \cdots. \end{align*}

Therefore we have

$$ \frac{2}{(n+2)!} f^{(n+2)}(0) = \frac{2}{(n+2)!} \cdot \frac{(3n+1)n}{24} (n+2)! = \frac{(3n+1)n}{12}. $$

Solution 3:

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

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

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

This is $$(n+2)! [z^{n+2}] (\exp(z)-1)^n.$$

Observe that $\exp(z)-1$ starts with $z + \frac{1}{2} z^2 + \frac{1}{6} z^3 +\cdots.$

There are two possibilities here depending on which term from the series expansion is included in the product of the $n$ terms, the first is a single term with $z^3$ and the rest being $z$ which yields $${n\choose 1} 1^{n-1} \frac{1}{6} = \frac{1}{6} n.$$

The other possibility is two terms in $z^2$ with the rest being $z$ which yields $${n\choose 2} 1^{n-2} \frac{1}{2^2} = \frac{1}{8} n (n-1).$$

Adding these we obtain $$\frac{n(3n+1)}{24}$$

for a final answer of $$(n+2)! \frac{n(3n+1)}{24}.$$

Solution 4:

Note: This is more a hint than a complete answer providing just some additional information.

If we exchange the order of summation $k \rightarrow n-k$ in the LHS of OP's identity we obtain

\begin{align*} \frac{2}{(n+2)!}\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^{n+2} \end{align*}

Note that the Stirling Numbers of the second kind $\begin{Bmatrix}m\\n\end{Bmatrix}$ are defined as \begin{align*} \begin{Bmatrix}m\\n\end{Bmatrix}=\frac{1}{n!}\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^{m} \end{align*}

Setting $m=n+2$ we can write OP's expression as \begin{align*} \frac{2}{(n+2)!}\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^{n+2}=\frac{2}{(n+1)(n+2)}\tag{1} \begin{Bmatrix}n+2\\n\end{Bmatrix} \end{align*}

So, we essentially have to calculate the Stirling number of the second kind $\begin{Bmatrix}n+2\\n\end{Bmatrix}$ in order to prove OP's claim.

These numbers fulfil a lot of nice relations and we could try to prove the claim e.g. using the recurrence relation \begin{align*} \begin{Bmatrix}m\\n\end{Bmatrix}=n\begin{Bmatrix}m-1\\n\end{Bmatrix}+\begin{Bmatrix}m-1\\n-1\end{Bmatrix}\tag{2} \end{align*}

Since $\begin{Bmatrix}m\\n\end{Bmatrix}$ denotes the number of partitioning a set of $m$ elements into $n$ non-empty blocks, the recurrence relation tells us that we can select the $m$-th element and put it into a block by its own or we have $n$ possibilities to put it into one of $n$ already existing blocks.

But this is a little bit cumbersome and we have already answers with nice solutions. So, one additional remark instead. There are different generalisations of the Stirling Numbers of the second kind and one of them are the so-called r-associated Stirling numbers of the second kind, which are denoted as $$\begin{Bmatrix}m\\n\end{Bmatrix}_r$$

They give the number of $n$ different blocks of $m$ elements, each containing at least $r$ elements.

We find in Comtet's classic Advanced Combinatorics in the chapter about Stirling Numbers following relationship of $2$-associated Stirling numbers of the second kind with the Stirling numbers of the second kind \begin{align*} \begin{Bmatrix}n+a\\n\end{Bmatrix}=\sum_{k=a+1}^{2a}\binom{n+a}{k}\begin{Bmatrix}k\\k-a\end{Bmatrix}_2 \end{align*} Using this relationship together with given table values in this chapter, we can write OP's expression as \begin{align*} \frac{2}{(n+1)(n+2)}&\begin{Bmatrix}n+2\\n\end{Bmatrix}\\ &=\frac{2}{(n+1)(n+2)}\left[\binom{n+2}{3}\begin{Bmatrix}3\\1\end{Bmatrix}_2 +\binom{n+2}{4}\begin{Bmatrix}4\\2\end{Bmatrix}_2\right]\\ &=\frac{2}{(n+1)(n+2)}\left[\binom{n+2}{3} +3\binom{n+2}{4}\right]\\ &=\frac{n(3n+1)}{12} \end{align*} and the claim follows.