Simplifying a sum of binomial coefficients multiplied by power of choice number

Question

Let $n$ be a positive integer. Prove that $$ \sum_{k=0}^n \binom{n}{k}(k+1)^{k-1}(n+1-k)^{n-k} = (n+2)^n$$

Trying to generalize a combinatorial problem, my collegue have obtained the LHS with some numerical evidences which indicates the equation may holds. I have tried to prove it elementarily but failed.

What I have succeeded is to prove it using exponential generating function with Lambert omega function.

The exponential generating function of the LHS is $$ \sum_{n=0}^{\infty} \frac{x^n}{n!} \sum_{k=0}^n \frac{n!}{k!(n-k)!} (k+1)^{k-1} (n+1-k)^{n-k} $$ which can be arranged $$ \left( \sum_{k=0}^{\infty}\frac{(k+1)^k}{(k+1)!}x^k \right) \left( \sum_{l=0}^{\infty} \frac{(l+1)^l}{l!} x^l \right) $$ Let $L(x) = -W_0(-x)$ where $W_0$ is the principal branch of the Lambert $W$ function. Then the series expression $L(x) = \sum_{n=1}^{\infty} \frac{n^{n-1}}{n!} x^n$ and the differential equation $xL'(x) = \frac{L(x)}{1-L(x)}$ and hence the series expression $\sum_{n=1}^{\infty} \frac{n^n}{n!} x^n = \frac{L(x)}{1-L(x)}$ holds. These observations at hands, the exponential generating function of the LHS can be written as $$ \left(L(x)/x \right) \left(\frac{ L(x)}{x(1-L(x))} \right) = \frac{L(x)^2}{x^2(1-L(x))} $$

On the otherhand the exponential generationg function of the RHS is $\left( L(x)/x \right)'$. But then $$ \left(\frac{L(x)}{x}\right)' = \frac{xL'(x)-L(x)}{x^2} = \frac{L(x)^2}{x^2(1-L(x))} $$ which completes the proof.

However, I thing there would be a beautiful combinatorial argument which proves the identity. Is there anyone who can help to find such a proof?

Answer 1

Hint: This is a variant of Abel's identity which is sometimes considered as deep generalisation of the binomial theorem. This formulation can be found e.g. in the classic Advanced Combinatorics by Louis Comtet in section 3.1. The identity is stated there in the form \begin{align*} \sum_{k=0}^n\binom{n}{k}x(x-kz)^{k-1}(y+kz)^{n-k}=(x+y)^{n}\tag{1} \end{align*} valid for all x,y,z in a commutative ring. If we put $z=0$ we recover the binomial identity.

Using the substitution $x\to 1, y\to n+1, z\to -1$ we obtain OPs identity \begin{align*} \color{blue}{\sum_{k=0}^n \binom{n}{k}(k+1)^{k-1}(n+1-k)^{n-k} = (n+2)^n} \end{align*}

• An elementary algebraic proof is given here.

• A combinatorial proof based upon Cayley's formula $n^{n-2}$, the number of trees with $n$ labeled vertices, is also provided there.

Answer 2

For completeness, here are the details of the combinatorial proof referenced in epi163sqrt's answer.

Let $[n]$ denote $\{1,\dots,n\}$, for any $n\in \Bbb N$.

By Cayley's formula, $(n+2)^{n}$ is the number of labeled trees on the set $[n]\cup \{x,y\}$, where $x$ and $y$ are two special symbols which are not in $[n]$.

Alternatively, to specify a tree on $[n]\cup\{x,y\}$, you can

• choose a number $k\in \{0,1,\dots,n\}$.

• choose a subset $K$ of $[n]$ with $k$ elements, in $\binom{n}k$ ways.

• choose a labeled tree on $K\cup \{x\}$, in $(k+1)^{k-1}$ ways.

• choose a labeled, rooted tree on $([n]\setminus K)\cup \{y\}$, in $(n-k+1)^{n-k}$ ways,

• finally, unite these two trees by joining $x$ to the root of the second tree with an edge.

This operation defines a tree on the entire set $[n]\cup \{x,y\}$. Furthermore, it is reversible. Given a tree on $[n]\cup \{x,y\}$, consider the path joining $x$ to to $y$, and deleted the edge of this path with is incident to $x$. What remains are two disjoint trees, where one tree has the $x$ vertex and the other has the $y$ vertex. Furthermore, the vertex of the second tree which was originally adjacent to $x$ is special, so is singled out as the root.

Since the numbered of ways to complete the bulleted steps is $\sum_{k=0}^n \binom nk(k+1)^{k-1}(n-k+1)^{n-k}$, the equality is proved.