MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.


share|cite|improve this question
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
up vote 0 down vote accepted

What is the question? This proof is in "Proofs from the Book" and credited to Jim Pitman.

share|cite|improve this answer
The question is: why does this not get closed? – Igor Rivin Sep 19 '11 at 19:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.