- #1
TheMathNoob
- 189
- 4
Homework Statement
A. Show that n^n−2/n! < T(n) by looking at how the symmetric group Sn acts on labelled trees. Use |Sn| = n!
T(n) is the number of unlabeled trees on n vertices
Homework Equations
The Attempt at a Solution
I can't find any mathematical relation between labelled trees and unlabeled trees. I drew the non isomorphic graphs on different number of vertices. For example on 5 vertices, there are 3 non isomorphic classes. I counted the number of different trees on each class by hand. I just could notice that I always use the n!. For example the simplest class of a tree on 5 vertices is a straight line with 5 nodes. To count the number of trees you do 5!/2 because of the symmetry of this class. In this case n=5, so my point is that you always use n!.
n^(n-2)=n!/k+n!/y+... n!/z
The number of terms depends on the number of vertices, but I don't know how.
I thought that I could do something like this (n!/k+n!/y+...n!/z)/n!= 1/k+1/y+1/z and find something meaningful in the constants but turns out I couldn't.