Göbel = Matula Numbering. (Neé: Riffs & Rotes & A061396)
Jon Awbrey
jawbrey at oakland.edu
Fri Sep 6 06:30:42 CEST 2002
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
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.
my initial interest in riffs and rotes came out of a search for
"auto-documenting data structures" and "self-tagging 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:
is there a "purely combinatorical" reason that (p_2)^1 < (p_1)^2?
viewed as rotes:
o---o o---o
| |
o---o o---o
| |
@ <?< @
(p_2)^1 <?< (p_1)^2
fun & games ...
links here to dana scott's d_infinity and similar constructions.
later,
jon
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Antti Karttunen wrote:
>
> 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
>
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
More information about the SeqFan
mailing list