3
$\begingroup$

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.

  • 0
    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$.2012-11-11

2 Answers 2

4

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$.

1

See also A new bijection between natural numbers and rooted trees (Cappello).