The number of non-isomorphic trees
Task number: 4234
Prove that there are at most \( 4^n \) nonisomorphic trees on \( n \) vertices. Improve the estimate to \( \frac{1}{n + 1} \binom{2n}{n} \).
Hint
Use the tree isomorphism algorithm.
Solution
Non-isomorphic trees on \( n \) vertices are encoded by sequences of zeros and ones of length \( 2n \). There are \( 2^{2n} = 4^n \) such sequences.
However, the number of zeros and ones is the same, so the estimate can be improved to \( \binom{2n}{n} \).
In addition, zeros and ones in these sequences can, however, be paired as parentheses in good paired term. Such are \( \frac{1}{n + 1} \binom{2n}{n} \).
