Proof of a combinatorial equation

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.

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.)

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}. $$