Consider the recursion:

$\displaystyle f(n)=\sum_{k=1}^{n-1} (-1)^{k+1} {n \choose k} (n-k)^k f(n-k)$

Where $\displaystyle n \geq 3, f(1)=f(2)=1$.

I got this recursion when i tried to prove the cayley's theorem which says that there are $\displaystyle n^{n-2}$ distinct labelled trees on $\displaystyle n$ vertices.

I have checked that $\displaystyle f(n)=n^{n-2}$ satisfies the equation for $\displaystyle n=3,4,5,6$. Any idea how to prove that the solution to this recursion is $\displaystyle f(n)=n^{n-2}$.