# 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
|   o----o    o----o
|    \  ...  /
|     \  |  /
|      \ | /
|       \|/
|        @
|
| 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 1-1-Correspondence between Rooted Trees and Natural Numbers",
| 'Journal of Combinatorial Theory', B29 (1980), pages 141-143.

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

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

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

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 one-to-one 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
term-by-term 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 "bits-interleaved" 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
"auto-documenting data structures" and "self-tagging molecules",
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:

|    o---o                 o---o
|    |                     |
|    o---o             o---o
|    |                 |
|    @         <?<     @
|
|   (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

```