Compute the following sum $ \sum_{i=0}^{n} \binom{n}{i}(i+1)^{i-1}(n - i + 1) ^ {n - i - 1}$? I have the sum 
$$ \sum_{i=0}^{n} \binom{n}{i}\cdot (i+1)^{i-1}\cdot(n - i + 1) ^ {n - i - 1},$$
but I don't know how to compute it. It's not for a homework, it's for a graph theory problem that I try to solve.
 A: What follows  makes no claim to  originality and is  based on material
from  OEIS  A000272.  This computation  is
very      similar      to      the      one     at      this      MSE
link.

We  can  prove this  using  the labelled  tree
function that is known from combinatorics.
The idea that we use a convolution is sound but we actually have to do
the algebra.

This will  provide a  closed form  of  the exponential
generating function of the two terms that are involved.

We seek to show that
$$\sum_{k=0}^n {n\choose k} (k+1)^{k-1} (n-k+1)^{n-k-1}
= 2 \times (n+2)^{n-1}.$$

The combinatorial class of labelled rooted trees has the specification
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\mathcal{T} = 
\mathcal{Z} \times \textsc{SET}(\mathcal{T})$$
which gives the functional equation
$$T(z) = z \exp T(z).$$

We have $n!  [z^n] T(z) = n^{n-1}$, for a proof  consult the link from
the introduction. This implies that
$$\frac{1}{z} T(z) = \frac{1}{z} \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}
= \sum_{n\ge 1} n^{n-1} \frac{z^{n-1}}{n!}
= \sum_{n\ge 1} n^{n-2} \frac{z^{n-1}}{(n-1)!}.$$

Observe that when we  multiply two exponential generating functions of
the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} 
\sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0} 
\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0} 
\sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0} 
\left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the  product of  the two generating  functions is  the generating
function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

In the present case we have
$$A(z) = B(z) =
\sum_{q\ge 0} \frac{(q+1)^{q-1}}{q!} z^q.$$
The  equality  that  we seek  to  prove  is  the convolution of the  two
exponential generating functions $A(z)$ and $B(z)$ and to verify it we
must show that
$$n! [z^n] A(z) B(z) = 2 \times (n+2)^{n-1}$$
But we have
$$A(z) = B(z) = \frac{1}{z} T(z).$$
It follows that
$$n! [z^n] A(z) B(z)
= n! \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{T(z)^2}{z^2} dz.$$
Using the same substitution as before (consult link) this becomes
$$n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(w(n+3))}{w^{n+3}} 
\times w^2\times (\exp(-w) - w\exp(-w)) dw
\\ = n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(w(n+2))}{w^{n+1}} (1-w) dw
\\ = n!
\left(\frac{(n+2)^n}{n!} - \frac{(n+2)^{n-1}}{(n-1)!}\right)
\\ = (n+2)^n - n \times (n+2)^{n-1}
= (n+2)^{n-1} (n+2-n) = 2\times (n+2)^{n-1}.$$
The labelled tree function recently appeared at this
MSE link.
A: Look up Abel's binomial theorem,
for example, here:
http://en.wikipedia.org/wiki/Abel's_binomial_theorem
I find this funny because,
immediately preceding this,
I answered a question
by giving a reference to
Abel's summation formula.
This means,
of course,
that somebody will ask
about solving the quintic.
