Göbel = Matula numbering. (Was Re: Riffs & Rotes & A061396)

[Antti Karttunen]

Jon Awbrey wrote Fri, 22 Jun 2001 14:36:26:
> 
> ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
> 
> F. Göbel,
> On a 1-1-Correspondence between Rooted Trees and Natural Numbers,
> Journal of Combinatorial Theory, B29 (1980), pages 141-143.
> 
> This correspondence is associated in one way or another
> with the following sequences in the EIS online database:
> 
> A005517, A005518, A007097, A057452.
> 
> In 1980, we find the above paper published,
> giving a correspondence between rooted trees
> and natural numbers that is dual, in a sense,
> to the one that I gave between natural numbers
> and planted plane trees.  In summary, we have:
> 
> 1.  Recur on Index : N <-> Rooted Trees
> 2.  Recur on Power : N <-  Planted Plane Trees
> 3.  Recur on Both  : N  -> Riffs <-> Rotes
> 
> As given, the 2nd mapping is many-to-one and onto
> from planted plane trees to natural numbers, but
> there is a way to make the 2nd mapping injective,
> at least, I have an old note that claims this,
> but I will need to read it over again first,
> as I'm not as sure as I used to be about it.
> 
> I also notice that Göbel's paper is
> given as "Received June 26, 1978",
> so I begin to suspect that there
> must have been something in the
> air (or the water) that year.
> 
> Here is a cartoon synopsis of how Göbel's numbering goes:
> 
> ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
> |
> |   1     blank               blank
> |   2     p_1                 ()
> |   3     p_(p_1)             (())
> |   4     p_1^2               ()()
> |   5     p_(p_(p_1))         ((()))
> |   6     p_1 p_(p_1)         ()(())
> |   7     p_(p_1^2)           (()())
> |   8     p_1^3               ()()()
> |   9     p_(p_1)^2           (())(())
> |  10     p_1 p_(p_(p_1))     ()((()))
> |
> | ...
> |
> ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
> |
> |                          o
> |                          |
> |              o           o       o o   o
> |              |           |       |  \ /
> |        o     o   o   o   o   o   o   o   o o o
> |        |     |    \ /    |    \ /    |    \|/
> |  @     @     @     @     @     @     @     @
> |
> |  1     2     3     4     5     6     7     8   ...
> |
> ¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤



Something in the air ten years earlier ?
    
     D. W. Matula, Washington University, St. Louis, Missouri.
    A Natural Rooted Tree Enumeration by Prime Factorization.
    SIAM Rev. 10 (1968), p. 273.
    
      A one-to-one correspondence between the space of rooted
    trees and the positive integers is given by the following
    recursive procedure. Let the positive integer n correspond
    to the root node of a tree, the prime factors of n
    (each occurring as often as its multiplicity) correspond
    to the edges incident to the root node, and for each such
    edge incident to the root which corresponds to the prime p
    let the branch of the tree incident to that edge be the
    rooted tree corresponding to the number pi(p) (the prime
    number function pi). The terminal condition of this
    recursion arises quite naturally as unity (which has no
    prime factors) is thus associated with each pendent vertex.
    On the other hand, the number associated with a given
    rooted tree may be recursively determined as follows:
    If the numbers associated with the branches of a rooted
    tree T are n1, n2, ..., nm, then the unique number
    associated with T is the product p(n1) x p(n2) x ... x p(nm),
    where p(ni) is the ni:th prime. Certain interesting
    relationships between the theories of primes and trees
    will be developed utilizing this "natural" correspondence.


Compare with the beginning of Göbel's paper:

      In the sequel, we suppose that p(1) = 2, p(2), p(3), ...
    is the sequence of primes in ascending order.
      Let T be a rooted tree, r its root. The connected components
    of T - r are denoted by T1, ..., Tv, where v is the degree
    of r. The graphs Tj (j = 1,...,v) obviously are trees, which
    we transform into rooted trees by defining as the the root
    of Tj the vertex of Tj which is adjacent to r in T. We now
    assign a natural number phi(T) to the rooted tree T.

      Definition. If T has only one vertex, then phi(T) = 1.
    If the number of vertices of T is greater than 1, then

              phi(T) = product_{i=1..v} p(phi(Ti)),

    where T1, ..., Tv are the rooted trees defined above.

    .........


There's at least one on-line document about Matula-numbers:

Ivan Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers,
Publications de L'institut Mathématique (Beograd), Vol. 53(67), pp. 17-22 (1993).
URL: http://www.emis.de/journals/PIMB/067/n067p017.pdf
 
It would be nice to compute the functions f1 - f10 (corresponding
to the properties P1 - P10) defined in that paper.
I don't know how much you can find connections from there
to the classical elementary number theory, but as a simple
example, the degree of the rooted tree with Matula/Göbel number n
is bigomega(n) (A001222), and "the primeth recurrence" A007097
gives the trees with just one leaf.
 

Now, I started thinking why we must use specifically
the ordinary primes. Why not use instead the binary
encoding of irreducible Z2[x] polynomials, i.e.
A014580 (2,3,7,11,13,19,25,31,...) instead of
A000040 (2,3,5,7,11,13,17,19,23,...) as the function 'p'
in the above definition given by Göbel?
Of course then we should use the carryless Z2[x] multiplication
instead of the ordinary one, to acquire a one-to-one map.
So, 5 = 101 in binary (corresponding to x^2 + 1 = x+1 * x+1
in Z2[X]) corresponds now to the tree:

  \  /
   \/

which in original Matula/Göbel scheme is associated with the number 9.
(Deducing the properties of the trees using this scheme
might be slightly easier than with the original one?)

Combining the mapping N <-> rooted trees, and
rooted trees <-> Z2[x] polynomials we obtain a map
between the multiplicative semigroup (or specifically:
commutative monoid) of natural numbers
and the multiplicative semigroup found in
the ring of Z2[x] polynomials.
Let's call it khi. Unless I'm completely zombie,
it obeys
  khi(1)  = 1
and
  khi(ab) = khi(a) X khi(b)
where X means multiplication of Z2[x] polynomials,
so it is a homomorphism between these semigroups.


Using the standard binary encoding of Z2[x]
polynomials we can represent it in OEIS as
yet another permutation of natural numbers.
Among other things, it maps A000040 and A014580
term-by-term to each other.
(How does it map the corresponding multiplication
tables A004247 and A048720 to each other?)


Then we can get even wilder, because any domain
with unique factorization can be used, so why not to
use, say Gaussian integers, or some other
"double ring"? I remember that Marc spoke
some months ago about storing these ones to OEIS
with the "bits-interleaved" method.



Terveisin,

Antti Karttunen