How to prove $ \sum_{r=1}^{k-1} \binom{k}{r}\cdot r^r \cdot (k-r)^{k-r-1} = k^k-k^{k-1} $ How to prove the following identity:
$$
\sum_{r=1}^{k-1} \binom{k}{r}\cdot r^r \cdot (k-r)^{k-r-1} = k^k-k^{k-1}
$$
I have no idea how to tackle it because of the $r^r$. Any help is highly appreciated!
 A: 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_{r=1}^{k-1} {k\choose r} r^r (k-r)^{k-r-1}
= k^k - k^{k-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) = \sum_{q\ge 1} \frac{q^q}{q!} z^q
\quad\text{and}\quad
B(z) = \sum_{q\ge 1} \frac{q^{q-1}}{q!} z^q.$$
The species of labelled 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).$$
Extracting coefficients via Lagrange inversion we have
$$Q_n
= n! \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) dz.$$
Put $T(z)=w$ so that $z=w/\exp(w) = w\exp(-w)$ and 
$dz = \exp(-w) - w\exp(-w) \; dw$ 
to get
$$n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(w(n+1))}{w^{n+1}} 
\times w\times (\exp(-w) - w\exp(-w)) dw
\\ = n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(wn)}{w^n} (1 - w) dw.$$
But we have 
$$n! [w^{n-1}] \exp(w n) = 
n! \times \frac{n^{n-1}}{(n-1)!} = n^n$$
and
$$n! [w^{n-2}] \exp(w n) = 
n! \times \frac{n^{n-2}}{(n-2)!} = n (n-1) n^{n-2} = (n-1) n^{n-1}$$
which means that $T(z)$ is the exponential generating function
of $$n^n - (n-1) n^{n-1} = n^{n-1}
\quad\text{i.e.}\quad
T(z) = \sum_{q\ge 1} \frac{q^{q-1}}{q!} z^q.$$
This also follows from Cayley's theorem.
The  equality  that  we seek  to  prove  is  the convolution  the  two
exponential generating functions $A(z)$ and $B(z)$ and to verify it we
must show that
$$k! [z^k] A(z) B(z) = k^k - k^{k-1}.$$
But we have (differentiate termwise)
$$A(z) = z \frac{d}{dz} T(z)
\quad\text{and}\quad B(z) = T(z).$$
Observe that
$$z T'(z) = z \left(\exp T(z) + z \exp T(z) T'(z) \right)
= T(z) + z T(z) T'(z)$$
which implies that
$$z T'(z) = \frac{T(z)}{1-T(z)}.$$
It follows that
$$k! [z^k] A(z) B(z)
= k! \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+1}} \frac{T(z)^2}{1-T(z)} dz.$$
Using the same substitution as before this becomes
$$k! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(w(k+1))}{w^{k+1}} 
\times \frac{w^2}{1-w}\times (\exp(-w) - w\exp(-w)) dw
\\ = k! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(wk)}{w^{k-1}} dw
= k! \frac{k^{k-2}}{(k-2)!}
= (k-1) k^{k-1} = k^k - k^{k-1}.$$

The labelled tree function recently appeared at this 
MSE link.
A: 
This identity is a special case 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}
\end{align*}
  valid for all x,y,z in a commutative ring. If we put $z=0$ we recover the binomial identity.

A rather elementary proof of OPs claim is given in this answer.

With the usual convention $0^0:=1$ you can start the summation with $r=0$ and write the formula as
  \begin{align*}
\sum_{r=0}^{k-1} \binom{k}{r} r^r  (k-r)^{k-r-1} = k^k
\end{align*}
  Reverting the summation $r \rightarrow k-1-r$ gives
  \begin{align*}
\sum_{r=0}^{k-1} \binom{k}{r+1} (k-r-1)^{k-r-1}  (r+1)^{r+1} = k^k
\end{align*}
  Finally shifting the index $r$ by one is precisely the identity which is proved in the referred answer.
  \begin{align*}
\sum_{r=1}^{k} \binom{k}{r}  r^r(k-r)^{k-r}  = k^k
\end{align*}

A: There is also a quick combinatorial proof. Both sides of the equation answer the question

How many ways are there to choose a rooted tree on the distinct vertices $\{1,2,\dots,k\}$, and then choose one of the edges?

The right hand side is $(k-1)k^{k-1}$. We interpret $k^{k-1}$ as the number of rooted trees on $k$ vertices, while $(k-1)$ gives the choice of an edge.
Given a rooted tree on $k$ vertices, along with a distinguished edge, removing the edge leaves two disconnected trees, one which contains the root of the original tree. It follows that another way of choosing a rooted tree with a distinguished edge is to...


*

*Select $r$ vertices from $\{1,2,\dots,k\}$, in $\binom{k}r$ ways,

*Choose a rooted tree on these $r$ vertices in $r^{r-1}$ ways,

*Choose an unrooted tree on the remaining $k-r$ vertices in $(k-r)^{k-r-2}$ ways, and

*Choose a vertex from the rooted tree (in $r$ ways) and a vertex from the unrooted tree (in $k-r$ ways) and join them with a distinguished edge.

