The On-Line Encyclopedia of Integer Sequences
17/3/08, 15:24
(No Ratings Yet)
Loading ...
(No Ratings Yet) Loading ...I was trying to answer this question – how many labeled rooted trees with n nodes are there?
A quick search didn’t find the answer (I’m sure a more detailed search would have). Then I had this idea – find the answer for small values of n, and look in the OEIS. I typed 1,2,9,64 in the search and quickly found the answer (which is n^(n-1) for those interested). I thought about it for a couple of minutes but still hadn’t come up with an answer as to why this is true.
Anonymous:
The number of labeled trees on n nodes, which is n^{n-2} by Prüfer’s theorem, times n for the selection of which label is the root.
17/3/08, 17:10ripper234:
Right you are, thanks 🙂
I’m curious, who is this?
What I immediately found in Wikipedia is the number of unrooted trees is n^{n-2}, but I didn’t make the trivial jump to rooted trees.
17/3/08, 17:18Adam Morrison:
It was me, didn’t notice the option to leave a name instead of being anonymous.
18/3/08, 18:28