Göbel = Matula Numbering. (Neé: Riffs & Rotes & A061396)
Jon Awbrey
jawbrey at oakland.edu
Tue Sep 10 15:16:23 CEST 2002
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
some incidental remarks on riffs & rotes,
from the standpoint of ordered domains.
suppose that we don't know anything at all about the number theory connection,
but are simply given a species of trees defined by the following recursion:
 @ is a rote.

 if f is a finite function from rotes to rotes,
 say, f : index_j ~> exponent_j for j = 1 to k,
 where the "indices" and "exponents" are rotes,
 then the following tree is a rote:

 i_1 e_1 i_k e_k
 oo oo
 \ ... /
 \  /
 \  /
 \/
 @

 where the rotes for the "indices" (source elements) i_j
 and the "exponents" (target elemnts) e_j are attached
 at the places indicated.
so the question is, what is a natural way of partial ordering this species?
then, can we specify enough information to make it a total linear ordering?
jon awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
AK = Antti Karttunen
JA = Jon Awbrey
JA:  F. Göbel,
 "On a 11Correspondence between Rooted Trees and Natural Numbers",
 'Journal of Combinatorial Theory', B29 (1980), pages 141143.
JA: This correspondence is associated in one way or another
with the following sequences in the EIS online database:
A005517, A005518, A007097, A057452.
JA: 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
JA: As given, the 2nd mapping is manytoone 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.
JA: 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.
JA: 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 ...

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
AK: 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 onetoone 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.
AK: 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.

 ...
AK: There's at least one online document about Matulanumbers:
 Ivan Gutman and YeongNan Yeh, Deducing properties of trees from their Matula numbers,
 Publications de L'institut Mathématique (Beograd), Vol. 53(67), pp. 1722 (1993).
 URL: http://www.emis.de/journals/PIMB/067/n067p017.pdf
AK: 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.
AK: 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 onetoone map.
AK: 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?)
AK: 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)
AK: where X means multiplication of Z2[x] polynomials,
so it is a homomorphism between these semigroups.
AK: 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
termbyterm to each other.
AK: (How does it map the corresponding multiplication tables
A004247 and A048720 to each other?)
AK: 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 "bitsinterleaved" method.
JA: i will see if i can find the references later, but i remember
neil or maybe nordhaus telling me about some similar ideas
that a.a. mullin (?) called 'mosaics', some of which got
published in the nat.acad.sci., and i think that there
were related constructions going back to a goodstein
or goldstein in the 20's, also some connections to
mirimanoff. all very fuzzy now.
JA: my initial interest in riffs and rotes came out of a search for
"autodocumenting data structures" and "selftagging molecules",
plus links between additive and multiplicative number theory that
i associated with the question: "how much of the ordering of the
integers is purely combinatorial", whatever that means. so, yes,
some flavor of generalized primes comes into play  if you ask:
JA: is there a "purely combinatorical" reason that (p_2)^1 < (p_1)^2?
JA: viewed as rotes:
 oo oo
  
 oo oo
  
 @ <?< @

 (p_2)^1 <?< (p_1)^2
JA: fun & games ...
JA: links here to dana scott's d_infinity and similar constructions.
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
More information about the SeqFan
mailing list