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](https://oeis.org/A001864)).



Proof of a combinatorial equation
Everything is already contained in OEIS comments for [A001864](http://oeis.org/A001864) and [A000435](http://oeis.org/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.)


