Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the structure of a rooted tree independent of its underlying set, (i.e. in the sense of trees as combinatorial species). I know a number of ways which we can encode any such tree in natural numbers, but all of them fail to be a bijective, i.e. Some numbers can not be decoded into any sensible tree structure. I would be very pleased to see such concrete correspondence. Thank you.

share|improve this question
    
If you can encode each structure as a natural number, and there are infinitely many different structures you can collapse the range of the encoding to have a bijection with $\mathbb N$. –  Asaf Karagila Nov 11 '12 at 23:49

1 Answer 1

up vote 4 down vote accepted

See Y. Abe, Tree representation of positive integers, Applied Mathematics Letters Volume 7, Issue 1, January 1994, Page 57:

Abstract. We define a natural one-to-one correspondence between the set of positive integers and the set of equivalence classes of isomorphic rooted trees. By this correspondence, one can translate number-theoric concepts or quantities of a positive integer into graph-theoretic ones of a rooted tree. For example, a positive integer is prime if and only if the corresponding rooted tree is planted, that is, the valency of the root is equal to $1$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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