What is the formula to find the different unlabeled trees that can be formed from a given set of nodes?

I am just d开发者_如何学编程oing 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?

---

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.

---

This is non-isomorphic graph count problem.

For general case, there are 2^(ⁿ₂) non-isomorphic graphs on n vertices where (ⁿ₂) is binomial coefficient "n above 2".

However that may give you also some extra graphs depending on which graphs are considered the same (you also were not 100% clear which graphs do apply).

See this paper. And this article on MathWorld.

EDIT: In case you want to count labeled trees only the formula is n^(n-2).

Wikipedia.