What is the formula to find the different unlabeled trees that can be formed from a given set of nodes?
I am just doing a research on a project and came across a problem. I would be very grateful if anybody could help me out with this. Consider the figure below:
Two dots joined by a line results in only one diagram, three dots joined by single lines also results in one figure no matter how you join the dots, the result is the same. But as we increase the dots there are different possibilities, as seen with four dots.
Is there a formula for counting the number of unlabeled trees that can be formed from a set of nodes?
Answer
As suggested in the comments, your question can be phrased as determining the number of unlabeled trees on n vertices. Notice this differs significantly from the question of counting labeled trees (of which there are n^{n-2}) or labeled graphs (of which there are 2^\binom{n}{2}).
The Online Encyclopedia of Integer Sequences has a lot of good data about this problem (including code to generate the sequence): https://oeis.org/A000055. In particular, it gives a generating function A(x) for these numbers, which is the best solution known to date (from a mathematician's perspective):
A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2, where T(x) = x + x^2 + 2x^3 + ...
If you are not familiar with generating functions, think of it as a carefully designed polynomial whose coefficients form the desired sequence. That is, the coefficient of x^n in this polynomial would be the number of unlabeled trees on n vertices.
As a final plug, you may find this reference useful: http://austinmohr.com/work/trees. It gives some counts and images for trees of up to ten vertices.