Riffs & Rotes & A061396

[Jon Awbrey]

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

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