# Cayley's Theorem regarding marked trees

Hello,

I have the following proof of Cayley's Theorem: Proof.

This proof counts orderings of directed edges of rooted trees in two ways and concludes the number of rooted trees with directed edges of order $n$.

However, I know a version of Cayley's Theorem in which $n^{n-2}$ is the number of marked trees spanning $K_{n}$.

What I need is to show that the number of marked trees spanning $K_{n}$ is equal to the number of rooted trees with directed edges of order $n$. This way, the proof given above will be valid for the version I know of the theorem.

As I understand, rooted trees and rooted trees with directed edges are the same thing. It shouldn't be hard to prove anyway. The rest, I don't know.

Thanks.

-
I think you are misunderstanding the lecture notes you are reading. Nobody is EVER talking about unmarked trees. Sometimes the author is just omitting the word "marked" for brevity. Unmarked rooted trees (i. e., trees up to isomorphism) are impossible to count, I believe. –  darij grinberg Sep 19 '11 at 18:26
I think this is sort of what confused me a bit. t(n) is simply the number of marked trees spanning $K_{n}$. Because the tree is marked there are $n$ options for choosing the root. If the trees weren't marked, there'd be less options. Thanks. I guess I needed something to be cleared. –  user17931 Sep 19 '11 at 19:38
Unlabeled (the usual term) trees are not impossible to count. They were first counted by Cayley (before he counted labeled trees, I believe). The numbers are A000055 in the OEIS. –  Ira Gessel Apr 29 '13 at 16:02