You Ask! We Count!

Number of unrooted trees

How many unrooted trees are there?

Nu=(2n-5)*(2n-7)*…*3*1=(2n-5)!/[2n-3*(n-3)!]

Not too many people know that in mathematics and computer science, a free tree or unrooted tree is a connected undirected graph with no cycles.  Keep in mind that the vertices with one neighbor are the leaves of the tree, and the remaining vertices are the internal nodes of the tree.  It is important to know that in an unrooted binary tree with n leaves, there will be n ? 2 internal nodes.  The number of unrooted trees can be calculated this way: Nu=(2n-5)*(2n-7)*…*3*1=(2n-5)!/[2n-3*(n-3)!].

This fact is verified on : November 12, 2013.





Leave a Response