mjhjmtu

How can we use elementary methods to prove that

$$sum_i = 2^nn choose i i! n^n - i = sum_i = 1^n - 1n choose ii^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).

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 $Ani a$, $Bni b$. If $|A|=i$, $|B|=n-i$, we may fix $A$, $B$ by $binomni$ 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.)

Let $mathbbN=left 0,1,2,ldotsright $. The following fact I have
seen referred to as the "Cauchy identity":

Theorem 1. Let $ninmathbbN$. Then,
beginequation
sum_k=0^ndbinomnkleft( X+kright) ^kleft( Y-kright)
^n-k=sum_t=0^ndfracn!t!left( X+Yright) ^t
endequation
in the polynomial ring $mathbbZleft[ X,Yright] $.

One proof of Theorem 1 can be found in Darij Grinberg, 6th QEDMO 2009,
Problem 4 (the Cauchy identity). Alternatively, Theorem 1 is the particular case
(for $mathbbL=mathbbZleft[ X,Yright] $, $S=left 1,2,ldots
,nright $ 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 $ninmathbbN$. Then,
beginequation
sum_i=0^ndbinomnii^ileft( n-iright) ^n-i=sum_i=0
^ndbinomnii!n^n-i.
endequation

Proof of Corollary 2. Theorem 1 is an equality between two polynomials.
Renaming the summation index $k$ as $i$ in this equality, we obtain
beginequation
sum_i=0^ndbinomnileft( X+iright) ^ileft( Y-iright)
^n-i=sum_t=0^ndfracn!t!left( X+Yright) ^t
endequation
Substituting $0$ and $n$ for $X$ and $Y$ in this equality, we find
beginalign*
& sum_i=0^ndbinomnii^ileft( n-iright) ^n-i\
& =sum_t=0^ndfracn!t!n^t\
& =sum_i=0^nunderbracedfracn!left( n-iright) !_=dbinom
nii!n^n-iqquadleft(
beginarray
[c]c
texthere, we have substituted n-itext for t\
textin the sum
endarray
right) \
& =sum_i=0^ndbinomnii!n^n-i.
endalign*
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,nright $ to $left 1,2,ldots,nright $ with
some specific conditions on their recurrent values.

Corollary 3. Let $ninmathbbN$. Then,
beginequation
sum_i=2^ndbinomnii!n^n-i=sum_i=1^n-1dbinomnii^ileft(
n-iright) ^n-i.
endequation

Proof of Corollary 3. If $nleq1$, then both sides are $0$, whence the
equality follows. Hence, we WLOG assume that $n>1$. Thus,
beginalign*
& sum_i=0^ndbinomnii^ileft( n-iright) ^n-i\
& =underbracedbinomn0_=1underbrace0^0_=1underbraceleft(
n-0right) ^n-0_=n^n+sum_i=1^n-1dbinomnii^ileft(
n-iright) ^n-i+underbracedbinomnn_=1n^nunderbraceleft(
n-nright) ^n-n_=0^0=1\
& =n^n+sum_i=1^n-1dbinomnii^ileft( n-iright) ^n-i+n^n.
endalign*
Comparing this with
beginalign*
& sum_i=0^ndbinomnii^ileft( n-iright) ^n-i\
& =sum_i=0^ndbinomnii!n^n-iqquadleft( textby Corollary
2right) \
& =underbracedbinomn0_=1underbrace0!_=1underbracen^n-0
_=n^n+underbracedbinomn1_=nunderbrace1!_=1n^n-1
+sum_i=2^ndbinomnii!n^n-i\
& =n^n+underbracenn^n-1_=n^n+sum_i=2^ndbinomni
i!n^n-i=n^n+n^n+sum_i=2^ndbinomnii!n^n-i,
endalign*
we obtain
beginalign*
n^n+n^n+sum_i=2^ndbinomnii!n^n-i=n^n+sum_i=1^n-1
dbinomnii^ileft( n-iright) ^n-i+n^n.
endalign*
Subtracting $n^n+n^n$ from both sides of this equality, we obtain
beginequation
sum_i=2^ndbinomnii!n^n-i=sum_i=1^n-1dbinomnii^ileft(
n-iright) ^n-i.
endequation
This proves Corollary 3. $blacksquare$

Corollary 3 is your claim.

Here is an alternative proof of the Cauchy identity.

Fix constants $x$ and $y$ and consider $C=(xpartial_s+y+partial_spartial_t-partial_t)^n(e^se^t)|_s=t=0$.

Dealing with the $s$ terms and then $t$ terms gives
beginalign
C&=sum_k=0^nnchoose k(xpartial_s+partial_spartial_t)^k(y-partial_t)^n-k(e^se^t)|_s=t=0\
&=sum_k=0^nnchoose k(x+partial_t)^k(y-partial_t)^n-k(e^kt+se^t)|_s=t=0\
&=sum_k=0^nnchoose k(x+partial_t)^k(y-partial_t)^n-k(e^kt)|_t=0\
&=sum_k=0^nnchoose k(x+k)^k(y-k)^n-k(e^kt)|_t=0\
&=sum_k=0^nnchoose k(x+k)^k(y-k)^n-k.
endalign
The reverse order gives
beginalign
C&=sum_k=0^nnchoose k(xpartial_s+y)^k(partial_spartial_t-partial_t)^n-k(e^se^t)|_s=t=0\
&=sum_k=0^nnchoose k(xpartial_s+y)^k(partial_s-1)^n-k(p(s)e^s)|_s=0,
endalign
where $p(s)$ is a polynomial with initial term $s^n-k$. Hence
beginalign
C&=sum_k=0^nnchoose k(xpartial_s+y)^k((n-k)!e^s)|_s=0\
&=sum_k=0^nnchoose k(x+y)^k((n-k)!e^s)|_s=0\
&=sum_k=0^nfracn!k!(x+y)^k.
endalign

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
$$
beginaligned
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 binomn-ij n^j (-i)^n-i-j\
&=sum_j=0^n binom nj n^j sum_i=0^n-j(-1)^n-i-jbinomn-jii^n-j.endaligned
$$
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.
$$

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)=tfrac1k [y^k-1] F^prime(y),e^ky =[y^k](1-y)F(y),e^kymbox for kgeq 1;.$$
In particular

$$T(z)=sum_ngeq 1fracn^n-1n!z^n ;mbox and ;
fracT(z)1-T(z)=sum_ngeq 1fracn^nn!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:=frack^kk!;;kgeq 1$ (i.e. the coefficients of $T(z) over 1-T(z)$) with itself.

Therefore
beginalign*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-2n^i over i!
endalign*
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

Here is an alternative.

Define the functions $A_n(t)=sum_kbinomnkt(t+k)^k-1(n-k)^n-k, B_n(t)=sum_kfracn!(n-k)!(t+n)^n-k$ and
$C_n(t)=sum_kbinomnk(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.