In process of doing some computations on Hilbert schemes, I stumbled across the following identity, for $k \ge 2$:
$$
k^{k-3} = \frac{1}{2} \sum\_{i=1}^{k-1} \binom{k-2}{i-1} i^{i-2} (k-i)^{k-i-2} 
$$
which can be verified computationally for small values of $k$ (I did it for the first 500).


This is actually a special case of a bigger problem, so I'm hoping to get ideas about what methods might be applicable to prove this kind of identity. 


I understand that there are good methods for automatically proving hypergeometric identities, but am I correct in thinking that this is not hypergeometric, due to the $k^{k-3}$ type terms?


**EDIT**
Here is a link to the bigger question that I had that this is a special case of: [Counting some binary trees with lots of extra stucture](https://mathoverflow.net/questions/272820)



Identity with binomial coefficients and k^k
Let's denote $T(x)=\sum\_{n\geq 1}\frac{n^{n-1}x^n}{n!}$ the exponential generating function of labeled rooted trees, and $U(x)=\sum\_{n\geq 1}\frac{n^{n-2}x^n}{n!}$ the corresponding function for unrooted trees. We will use the fact that $xU'=T$ and $xe^T=T$, both of which can be derived algebraically or combinatorially. Your identity follows from the relation
$$2\left(T(x)-U(x)\right)=T^2$$
since the coefficient of $x^{k}$ on the left is $\frac{2k^{k-3}}{(k-2)!}$ and the corresponding coefficient on the right is $\sum\_{i=1}^{k-1}\frac{i^{i-1}}{i!}\cdot\frac{(k-i)^{k-i-1}}{(k-i)!}$.


To get a quick proof of this notice that both sides only have terms of order $x^2$ or higher. Therefore it is enough to prove the derivative of this relation
$$2T'-2U'=2TT'$$
$$\iff xT'-xU'=xTT'\iff xT'(1-T)=T\iff T'(1-T)=e^T$$
$$\iff 1=\frac{d}{dx}\left(\frac{T}{e^T}\right).$$




---


I hope it's clear from above that in principle all such identities follow from the basic relation $xe^T=T$ and all its derivatives. I know it's usually common to give references to books or surveys, but I really like the video lectures by Zagier available [here](https://www.youtube.com/playlist?list=PL9kd4mpdvWcBOyZJgYQ1CMtgyz_RcwP3c), under the title "Partitions, Modular Forms, and Moduli Spaces" (these are based on a forthcoming paper by Dubrovin, Zagier and Yang). In a series of talks he presents how quasimodular forms appear in enumerative geometry. However in the first couple of lectures he focuses on what he calls "Lambert space" (nonstandard terminology from what I can tell, coming from the closely related [Lambert function](https://en.wikipedia.org/wiki/Lambert_W_function)) which is essentially the space of series that are linear combinations of $T$ and its derivatives. He shows, for example, how generating functions of maps or Hurwitz numbers belong to this Lambert space.


