# Math Help - proof of cayley's theorem; graph theory

1. ## proof of cayley's theorem; graph theory

Consider the recursion:
$f(n)=\sum_{k=1}^{n-1} (-1)^{k+1} {n \choose k} (n-k)^k f(n-k)$
Where $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 $n^{n-2}$ distinct labelled trees on $n$ vertices.
I have checked that $f(n)=n^{n-2}$ satisfies the equation for $n=3,4,5,6$. Any idea how to prove that the solution to this recursion is $f(n)=n^{n-2}$.

2. ## Re: proof of cayley's theorem; graph theory

I don't have a solution but could you please explain how you got that recursion?