A combinatorics identity I happened to find this identity.
\begin{equation*}
\sum_{k=1}^{n-1} \frac{(n-2)!}{k!(n-k)!}\cdot k^{k-1} \cdot (n-k)^{n-k} = n^{n-2}.
\end{equation*}
I got this identity when I tried to approach a Putnam problem: given $j\leq n$, prove the following: the number of functions from $\{1,2,...,n\}$ to itself that satisfy for each $1\leq i\leq n$ there exists $m\geq 0$ such that $f^{(m)}(i)\leq j$, is $jn^{n-1}$. Here, $f^{(m)}(x)=f^{(m-1)}(f(x))=f(f\cdots(f(x)))$ is the $m-$th iteration of $f$.
When $j=1$, let $k$ numbers be mapped to $n$ before mapped to $1$. By some induction and manipulation techniques, I arrive at the above identity. (Later, I found $n^{n-2}$ is the number of trees with $n$ vertices and this multiplied by $n$, the choices for $f(1)$, exactly gives the number of functions for $j=1$.)
It is true for $n\leq 4$ as I checked. Any idea? Any connection to other theory? Really appreciate it.

This is challenging to prove from scratch, let's do it! The given sum essentially is a convolution, which can be computed by extracting a coefficient in the product between
$$ f(x) = \sum_{n\geq 1}\frac{n^n}{n!}x^n \qquad\text{and}\qquad g(x)=\sum_{n\geq 1}\frac{n^{n-1}}{n!}x^n. $$
By Lagrange's inversion theorem we have $g(x)=-W(-x)$ (with $W$ being Lambert function) and $f(x)=x g'(x)$, so the whole exercise boils down to showing that
$$ f(x)g(x) = f(x)-g(x)$$
which is pretty straightforward, since $g'(x)=\frac{g(x)}{x(1-g(x))}
$ follows from the fact that $g(x)$ is the inverse function of $xe^{-x}$.
