Gödel, Göbel, Matula, Mullin, ...
Jon Awbrey
jawbrey at oakland.edu
Wed Sep 18 16:14:25 CEST 2002
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
AK = Antti Karttunen
JA = Jon Awbrey
catching up on old correspondence,
so this may be a bit out of order.
will try to pare the redundancies.
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.
AK: Look at A075166, giving a bijection between
rooted plane trees and natural numbers > 0.
http://www.research.att.com/cgibin/access.cgi/as/njas/sequences/eisA.cgi?Anum=075166
 The rooted plane trees encoded here are:
 .....................o...............o.........o...o..o.......
 ..............................................\./..........
 .......o....o...o....o....o.o.o..o...o.o.o.o.o...o....o...o...
 ............\./..........\/....\./...\./.........\./....
 @...... at ......@...... at ......@...... at ......@...... at ......@.....
 1......2......3......4......5......6......7......8......9.....
AK: was it that what you had in mind then?
oh, strictly speaking, we should be calling these "planted plane trees",
as otherwise you can rotate the branches around the root and transform,
for example, 6 into 9.
i found the two letters that i wrote to martin gardner in 76 & 78,
and will try to extract the gist of them later, but here is a bit:
 The forest primeval: a correspondence between natural numbers and planted plane trees.

 Consider the primes factorization of a number and represent it as the sequence of its
 exponents separated by parentheses, thus, N = (n_1) (n_2) (n_3) ... (n_m), ignoring
 for now the allzero exponents after some point m.

 e.g.: 1 = 2^0 = (), 2 = 2^2^0 = (()), 3 = 2^0 3^2^0 = ()(())

 Repeat this process with each exponent in the factorization and with each further
 exponent in 'its' factorization and so on, until zero exponents are reached along
 every path of development. A zero exponent, having no representation in primes,
 may simply be omitted on the next pass. For example:

 360 = (3)(2)(1) = ((0)(1)) ((1)) ((0)) = (()((0))) (((0))) (())

 = (()(())) ((())) (())

 = 2^(2^0 3^2^0) 3^2^2^0 5^2^0

 Thus, parentheses suffice to represent this "involved factorization" of a number.
 But they also represent planted plane trees, if we interpret the exterior space
 as the planter, parenthetical containments as further edges, and contained
 spaces as nodes, e.g.:

 o o
  
 o o o o
 \  
 o o o
 \  /
 \/
 o
 
 360 = @

 In this way, every number may be assigned a unique minimal tree, but
 many trees will share the same number when the "insignificant digits" of
 a factorization are taken into account. E.g., trees of the following form,
 where an ellipsis represents an arbitrary number of terminal edges, all have
 the number 360:

 o
o
 / /
 o o
o
o
 \/ / /
 o o o
 \  /
 \  /
 \/
 o
 
 @

 = 2^(2^0 3^(2^0 3^0
) 5^0
) 3^(2^(2^0 3^0
) 3^0
) 5^(2^0
) 7^0
continued later,
jon awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
More information about the SeqFan
mailing list