1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – darij grinberg
    Commented Sep 19, 2011 at 18:26
  • $\begingroup$ 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. $\endgroup$
    – user17931
    Commented Sep 19, 2011 at 19:38
  • $\begingroup$ 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. $\endgroup$
    – Ira Gessel
    Commented Apr 29, 2013 at 16:02

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ The question is: why does this not get closed? $\endgroup$
    – Igor Rivin
    Commented Sep 19, 2011 at 19:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .