Göbel = Matula Numbering. (=?iso-8859-1?Q?Ne=E9?=: Riffs & Rotes & A061396)
Antti Karttunen
karttu at megabaud.fi
Sun Sep 15 19:43:12 CEST 2002
Jon Awbrey wrote:
>
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
> 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.
Look at A075166, giving a bijection between rooted plane trees and
natural numbers > 0.
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=075166
was it that what you had in mind then?
A075171 is a variant based on vectors represented in the
binary run lengths, instead of exponents in prime factorization.
There are also many other ways to "directly" map natural numbers
to the Catalanian denizens. I have collected various
schemes using any NxN <-> N bijection to map between
non-negative integers and plane binary trees, to the index entry
permutations, of the integers, induced by Catalan rerankings, each paired with its inverse: (1) A071651-A071652, A071653-A071654, A072634-A072635, A072636-A072637,
A072656-A072657, A072658-A072659
permutations, of the integers, induced by Catalan rerankings, each paired with its inverse: (2) A072646-A072647, A072787-A072788, A072764-A072765, A072766-A072767
so far I haven't found/constructed any ranking scheme
which would be practical to implement as a computer algorithm,
in a sense that the sequence {max integer mapped to the size n tree}
wouldn't grow too steeply. I reckon this is also the problem
with Matula/Göbel encoding of rooted unoriented trees.
And those two new ones A075166 & A075171 based on general
trees/parenthesizations are even less so (well-behaving and humble).
...
> JA. 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?
I delve into this later in autumn, after I have read more about posets
and lattices, and also when I have grokked your rotes & riffs
(has to find the folder where I put all your mails I printed out then...)
Anyways, I doubt in the following:
> JA. 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?
that you could find with such methods a total order that would
correspond with our usual linear order 1 < 2 < 3 < 4 < 5 < 6 < ...
because it's based on the additive property of integers,
and these N <-> various trees schemes are based on the
multiplicative properties (more or even less).
(And I'm afraid that the connection with primes and such
is just a red herring...)
Terveisin,
Antti Karttunen
>
> jon awbrey
>
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
>
> 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",
> 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:
>
> | 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
More information about the SeqFan
mailing list