A New Bijection between Natural Numbers and Rooted Trees

Peter Cappello
SIAM Conference on Discrete Mathematics, June 1988.

Abstract

A bijection is defined recursively between the set of natural numbers and the set of finite rooted trees. It is based on the prime decomposition of a natural number and the rank of a prime. This bijection leads naturally to a canonical presentation of rooted trees. For trees in each of two classes, bounds are given for the number of nodes
in terms of the number assigned to the tree.

BibTex

@techreport{cappello:1988:bijection,
    author    = {Peter Cappello},
    title     = {{A New Bijection between Natural Numbers and Rooted Trees}},
    institution = {Computer Science, UC Santa Barbara},
    year      = {1988},
    type      = {},
    number    = {},
    month     = {},
    note      = {Presented at the 4th SIAM Conference on Discrete Mathematics, San Francisco, June 1988},
}

Full version (pdf)