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} \).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email