Proof of a combinatorial equation How can we use elementary methods to prove that
$$\sum_{i = 2}^{n}{{n \choose i} i! n^{n - i}} = \sum_{i = 1}^{n - 1}{{n \choose i}i^i (n - i)^{n - i}}$$
for any integer $n \geq 0$?
The values of each side for fixed $n$ are 0, 0, 2, 24, 312, 4720, ... (A001864 - OEIS).
 A: A standard approach to proving this kind of identity is to use differences of polynomials.
First note that if change the limits on both sums to 0 and $n$, then we add two terms on the left and two terms on the right, and each of the four additional terms is equal to $n^n$. So we may instead prove the modified identity in which each sum goes from 0 to $n$.
We have
$$
\begin{aligned}
\sum_{i=0}^n \binom ni i^i (n-i)^{n-i}&=\sum_{i=0}^n  \binom ni i^i \sum_{j=0}^{n-i}  \binom{n-i}{j} n^j (-i)^{n-i-j}\\
  &=\sum_{j=0}^n \binom nj  n^j \sum_{i=0}^{n-j}(-1)^{n-i-j}\binom{n-j}{i}i^{n-j}.\end{aligned}
$$
The inner sum on the right is the $(n-j)$th difference of a polynomial in $i$ of degree $n-j$ with leading coefficient 1, and is therefore equal to $(n-j)!$. Thus the sum is equal to 
$$
\sum_j  \binom nj  n^j (n-j)! = \sum_{i=0}^n \binom ni i!\, n^{n-i}.
$$
A: Here is an alternative proof of the Cauchy identity.
Fix constants $x$ and $y$ and consider $C=(x\partial_s+y+\partial_s\partial_t-\partial_t)^n(e^{se^t})|_{s=t=0}$.
Dealing with the $s$ terms and then $t$ terms gives
\begin{align}
C&=\sum_{k=0}^n{n\choose k}(x\partial_s+\partial_s\partial_t)^k(y-\partial_t)^{n-k}(e^{se^t})|_{s=t=0}\\
&=\sum_{k=0}^n{n\choose k}(x+\partial_t)^k(y-\partial_t)^{n-k}(e^{kt+se^t})|_{s=t=0}\\
&=\sum_{k=0}^n{n\choose k}(x+\partial_t)^k(y-\partial_t)^{n-k}(e^{kt})|_{t=0}\\
&=\sum_{k=0}^n{n\choose k}(x+k)^k(y-k)^{n-k}(e^{kt})|_{t=0}\\
&=\sum_{k=0}^n{n\choose k}(x+k)^k(y-k)^{n-k}.
\end{align}
The reverse order gives
\begin{align}
C&=\sum_{k=0}^n{n\choose k}(x\partial_s+y)^k(\partial_s\partial_t-\partial_t)^{n-k}(e^{se^t})|_{s=t=0}\\
&=\sum_{k=0}^n{n\choose k}(x\partial_s+y)^k(\partial_s-1)^{n-k}(p(s)e^{s})|_{s=0},
\end{align}
where $p(s)$ is a polynomial with initial term $s^{n-k}$. Hence
\begin{align}
C&=\sum_{k=0}^n{n\choose k}(x\partial_s+y)^k((n-k)!e^{s})|_{s=0}\\
&=\sum_{k=0}^n{n\choose k}(x+y)^k((n-k)!e^{s})|_{s=0}\\
&=\sum_{k=0}^n\frac{n!}{k!}(x+y)^k.
\end{align}
A: Similar questions can also be dealt with  using generating functions and Lagrange inversion.
Let $T(z)$ (the "tree function") be the formal power series satisfying $T(z)=z\,e^{T(z)}$.
If $F$ is a formal power series  the coefficients of $G(z):=F(T(z))$ are given by (Lagrange inversion)
$$[z^0]G(z)=[z^0] F(z) \mbox{ , }  [z^k]G(z)=\tfrac{1}{k} [y^{k-1}] F^\prime(y)\,e^{ky} =[y^k](1-y)F(y)\,e^{ky}\mbox{ for } k\geq 1\;.$$
In particular
$$T(z)=\sum_{n\geq 1}\frac{n^{n-1}}{n!}z^n \;\mbox{   and   }\;
            \frac{T(z)}{1-T(z)}=\sum_{n\geq 1}\frac{n^{n}}{n!}z^n$$
        When you divide the rhs of your equation above  by $n!$ you clearly get the $n$-th coefficient of the convolution of the  series $a_0:=0, a_k:=\frac{k^k}{k!}\;\;{k\geq 1}$ (i.e. the coefficients of ${T(z) \over 1-T(z)}$) with itself.
Therefore
\begin{align*}\sum_{i=1}^{n-1} {n \choose i} i^i(n-i)^{n-i}&=n!\,[z^n] \bigg({T(z) \over 1-T(z)}\bigg)^2\\
                    &=n!\,[y^n] (1-y) {y^2 \over (1-y)^2}\,e^{ny}\\
             &=n!\,[y^{n-2}] {e^{ny}  \over 1-y}=n!\sum_{i=0}^{n-2}{n^i \over i!}
\end{align*}
which is what you want.
Remark: the exponential generating function $\big({T(z) \over 1-T(z)}\big)^2$ for the rhs was already given by Vladeta Jovovic in the notes to A001864 - OEIS
A: Let $\mathbb{N}=\left\{  0,1,2,\ldots\right\}  $. The following fact I have
seen referred to as the "Cauchy identity":

Theorem 1. Let $n\in\mathbb{N}$. Then,
  \begin{equation}
\sum_{k=0}^n \dbinom{n}{k}
\left(  X+k\right)  ^k \left(  Y-k\right)  ^{n-k}
=\sum_{t=0}^n \dfrac{n!}{t!}\left(  X+Y\right)  ^t 
\end{equation}
  in the polynomial ring $\mathbb{Z}\left[  X,Y\right]  $.

One proof of Theorem 1 can be found in Darij Grinberg, 6th QEDMO 2009,
Problem 4 (the Cauchy identity).
A simpler proof can be found in the solution of Exercise 1 (a) in
UMN Fall 2018 Math 5705 midterm #3
(this one was found by Tomoya Imaizumi, a student in that class).
(My exercise uses two rational numbers $x$ and $y$ instead of the
indeterminates $X$ and $Y$, but the proof does not care.)
Alternatively, Theorem 1 is the particular case
(for $\mathbb{L}=\mathbb{Z}\left[  X,Y\right]  $, $S=\left\{  1,2,\ldots
,n\right\}  $ and $x_{s}=1$) of Theorem 2.2 in Darij Grinberg,
Noncommutative Abel-like identities.
More directly, it is the particular case (for
$Z=1$) of equality (1) in the latter reference, where I also cite other sources.

Corollary 2. Let $n\in\mathbb{N}$. Then,
  \begin{equation}
\sum_{i=0}^n \dbinom{n}{i}i^i \left(  n-i\right)  ^{n-i}
=\sum_{i=0}^n \dbinom{n}{i}i!n^{n-i}.
\end{equation}

Proof of Corollary 2. Theorem 1 is an equality between two polynomials.
Renaming the summation index $k$ as $i$ in this equality, we obtain
\begin{equation}
\sum_{i=0}^n \dbinom{n}{i}\left(  X+i\right)  ^i \left(  Y-i\right)
^{n-i}=\sum_{t=0}^n \dfrac{n!}{t!}\left(  X+Y\right)  ^t .
\end{equation}
Substituting $0$ and $n$ for $X$ and $Y$ in this equality, we find
\begin{align*}
& \sum_{i=0}^n \dbinom{n}{i}i^i \left(  n-i\right)  ^{n-i}\\
& =\sum_{t=0}^n \dfrac{n!}{t!}n^t \\
& =\sum_{i=0}^n \underbrace{\dfrac{n!}{\left(  n-i\right)  !}}_{=\dbinom
{n}{i}i!}n^{n-i}\qquad\left(
\begin{array}
[c]{c}
\text{here, we have substituted }n-i\text{ for }t\\
\text{in the sum}
\end{array}
\right)  \\
& =\sum_{i=0}^n \dbinom{n}{i}i!n^{n-i}.
\end{align*}
This proves Corollary 2. $\blacksquare$
Are there combinatorial proofs of Corollary 2? I'm pretty sure that the answer
is "Yes", and I suspect that they involve counting some sort of functions from
$\left\{  1,2,\ldots,n\right\}  $ to $\left\{  1,2,\ldots,n\right\}  $ with
some specific conditions on their recurrent values.

Corollary 3. Let $n\in\mathbb{N}$. Then,
  \begin{equation}
\sum_{i=2}^n \dbinom{n}{i}i!n^{n-i}
=\sum_{i=1}^{n-1}\dbinom{n}{i}i^i \left( n-i\right)  ^{n-i}.
\end{equation}

Proof of Corollary 3. If $n\leq1$, then both sides are $0$, whence the
equality follows. Hence, we WLOG assume that $n>1$. Thus,
\begin{align*}
& \sum_{i=0}^n \dbinom{n}{i}i^i \left(  n-i\right)  ^{n-i}\\
& =\underbrace{\dbinom{n}{0}}_{=1}\underbrace{0^{0}}_{=1}\underbrace{\left(
n-0\right)  ^{n-0}}_{=n^n }+\sum_{i=1}^{n-1}\dbinom{n}{i}i^i \left(
n-i\right)  ^{n-i}+\underbrace{\dbinom{n}{n}}_{=1}n^n \underbrace{\left(
n-n\right)  ^{n-n}}_{=0^{0}=1}\\
& =n^n +\sum_{i=1}^{n-1}\dbinom{n}{i}i^i \left(  n-i\right)  ^{n-i}+n^n .
\end{align*}
Comparing this with
\begin{align*}
& \sum_{i=0}^n \dbinom{n}{i}i^i \left(  n-i\right)  ^{n-i}\\
& =\sum_{i=0}^n \dbinom{n}{i}i!n^{n-i}\qquad\left(  \text{by Corollary
2}\right)  \\
& =\underbrace{\dbinom{n}{0}}_{=1}\underbrace{0!}_{=1}\underbrace{n^{n-0}
}_{=n^n }+\underbrace{\dbinom{n}{1}}_{=n}\underbrace{1!}_{=1}n^{n-1}
+\sum_{i=2}^n \dbinom{n}{i}i!n^{n-i}\\
& =n^n +\underbrace{nn^{n-1}}_{=n^n }+\sum_{i=2}^n \dbinom{n}{i}
i!n^{n-i}=n^n +n^n +\sum_{i=2}^n \dbinom{n}{i}i!n^{n-i},
\end{align*}
we obtain
\begin{align*}
n^n +n^n +\sum_{i=2}^n \dbinom{n}{i}i!n^{n-i}=n^n +\sum_{i=1}^{n-1}
\dbinom{n}{i}i^i \left(  n-i\right)  ^{n-i}+n^n .
\end{align*}
Subtracting $n^n +n^n $ from both sides of this equality, we obtain
\begin{equation}
\sum_{i=2}^n \dbinom{n}{i}i!n^{n-i}=\sum_{i=1}^{n-1}\dbinom{n}{i}i^i \left(
n-i\right)  ^{n-i}.
\end{equation}
This proves Corollary 3. $\blacksquare$
Corollary 3 is your claim.
A: Here is an alternative.
Define the functions $A_n(t)=\sum_k\binom{n}kt(t+k)^{k-1}(n-k)^{n-k}, B_n(t)=\sum_k\frac{n!}{(n-k)!}(t+n)^{n-k}$ and
$C_n(t)=\sum_k\binom{n}k(t+k)^k(n-k)^{n-k}$. 
From $(t+k)^k=t(t+k)^{k-1}+k(t+k)^{k-1}$ and on the basis of Abel's identity, 
one gets $C_n(t)=A_n(t)+nC_{n-1}(t+1)=(t+n)^n+nC_{n-1}(t+1)$. It is easy to check that $B_n(t)=(t+n)^n+nB_{n-1}(t+1)$. Since both $B_n$
and $C_n$ satisfy the same initial conditions, it follows $B_n(t)=C_n(t)$. So, $B_n(0)=C_n(0)$ gives the desired result. 
A: Everything is already contained in OEIS comments for A001864 and A000435 (a remarkable  comment is that A000435 is the sequence that started it all: the first sequence in the database!)
We take $n$ labelled vertices, consider all trees on them, and sum up the distances between all pairs of vertices (each distance counted twice). 
One way to do it is the following: this sum is the number of 5-tuples $(T,a,b,c,d)$ such that $T$ is a tree, $a,b,c,d$ are vertices, $ab$ is an edge of $T$ and this edge belongs to the path between $c$ and $d$ (in the order $cabd$ on the path). If we remove $ab$, we get two connected components $A\ni a$, $B\ni b$. If $|A|=i$, $|B|=n-i$, we may fix $A$, $B$ by $\binom{n}i$ ways, after that fix restrictions of $T$ onto $A$, $B$ by $i^{i-2}(n-i)^{n-i-2}$ ways and fix $a,b,c,d$ by $i^2(n-i)^2$ ways. Totally we get RHS of your formula.
Why we get LHS is explained in Claude Lenormand's comment for A000435 (there we count the sum of distances from the fixed vertex 0 to other vertices in all trees, of course it is $n$ times less than the sum of all distances.)
