Graph theory proof (Unlabeled trees)

[TheMathNoob]

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.

 

[haruspex]

I can't find any mathematical relation between labelled trees and unlabeled trees.

Not even an inequality?
If you take an unlabelled tree and label it, what is the greatest number of distinct labelled trees you might produced?

 

[TheMathNoob]

Not even an inequality?
If you take an unlabelled tree and label it, what is the greatest number of distinct labelled trees you might produced?

I found the different unlabeled trees. As I was saying, there are 3 classes of unlabeled trees on 5 vertices. In the first class, a straight line, we can't use the n! because this generates duplicates. I know that the greatest number of labeled trees on n vertices y n^(n-2), but counting the number of labelled trees from a unlabeled tree is a tough task.

http://mathworld.wolfram.com/Tree.html

My point can be explained better with this picture. Each class on different n vertices is drawn and I am attempting to count each one of them by hand and find some meaningful relation.

 

[haruspex]

counting the number of labelled trees from a unlabeled tree is a tough task.

Yes, but I'm not asking for the precise number, just an upper bound. How many ways could you assign the labels? Could there be some you've missed?

 

[TheMathNoob]

Yes, but I'm not asking for the precise number, just an upper bound. How many ways could you assign the labels? Could there be some you've missed?

n vertices would be n!

 

[haruspex]

n vertices would be n!

Right. Could there be any labelled trees missed by this procedure (generating n! labellings from each unlabelled tree)?

 

[TheMathNoob]

Right. Could there be any labelled trees missed by this procedure (generating n! labellings from each unlabelled tree)?

no intuitively n!>n^(n-2), the last thing I said is wrong, the answer is no. If we apply n! on each unlabeled tree, we miss nothing.

 

[haruspex]

intuitively n!>n^(n-2)

Eh? Not true.

If we apply n! on each unlabeled tree, we miss nothing.

Right. So what inequality can you write relating the number labelled trees on n vertices to the number of unlabelled trees on n vertices?

 

[TheMathNoob]

Eh? Not true.

Right. So what inequality can you write relating the number labelled trees on n vertices to the number of unlabelled trees on n vertices?

n!>unlabeled trees?? I don't know. I need more clues.

 

[haruspex]

n!>unlabeled trees?? I don't know. I need more clues.

Applying all n! possible labellings to every possible unlabelled tree we found every possible labelled tree (though perhaps with repeats). What relationship does that yield between the total number of unlabelled trees and the total number of labelled trees?

 

[TheMathNoob]

Applying all n! possible labellings to every possible unlabelled tree we found every possible labelled tree (though perhaps with repeats). What relationship does that yield between the total number of unlabelled trees and the total number of labelled trees?

if we sum all the n!, we would get something like kn!>n^(n-2) where k is the possible number of unlabeled trees ohhhhhh xd k>n^(n-2)/n!. right?

 

[haruspex]

if we sum all the n!, we would get something like kn!>n^(n-2) where k is the possible number of unlabeled trees ohhhhhh xd k>n^(n-2)/n!. right?

Bingo.

 

[TheMathNoob]

Bingo.

thank you so much sir! really thank you.