1
$\begingroup$

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.

Improve this question
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Also, this is wrong, because the $n^{n-2}$ formula distinguishes isomorphic trees with differently labeled vertices. $\endgroup$ – Misha Lavrov May 22 '17 at 16:46
0
$\begingroup$

I think isomorphism needs to be better defined here. If we label the nodes A, B, and C, A-B-C is clearly the same as C-B-A, but A-C-B is a relabeling, which may or may not be considered an isomorphism. If we don't label nodes at all, and the tree is non-directed, then yes, every 3-node tree is equivalent.

In this latter case, I'm unsure, but perhaps you can look at the problem as counting the number of distinct Steiner trees with 1-N vertices: https://oeis.org/A104653?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.