How many distinct trees with N nodes?

Question

I need help on this question regarding how many distinct trees exist given N nodes in the tree. "Distinct" here means that two isomorphic trees are counted as one. For 3 nodes, would the number of trees be 1 (since every other tree with 3 nodes is just an isomorphism of the other)?

Thanks.

Answer 1

I think the answer to your problem according to Cayley-Sylvester theorem is $n$ in the power of $n-2$.

Answer 2

The number of trees on $n$ nodes is given in https://oeis.org/A000055. There’s no closed-form formula for this, though.

While this answer’s sequence looks like the others for the first five to ten values, they quickly begin to differ. This is the one that counts all (unrooted) trees up to graph isomorphism.