Tree terminology. Was: Re: =?iso-8859-1?Q?G=F6del?=, =?iso-8859-1?Q?G=F6bel?=, Matula, Mullin, ...

[Antti Karttunen]

Jon Awbrey wrote:
> 
> o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
> 
> AK = Antti Karttunen
> JA = Jon Awbrey
> 
> AK: 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
> 
> | 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?
> 
> JA: 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'm following Stanley's usage in his
"Exercises on Catalan and Related Numbers"
http://www-math.mit.edu/~rstan/ec/catalan.pdf

that is, the above trees belong to his manifestation 19 (e)
"plane trees with n + 1 vertices"
while the next manifestation (f) is given as
"planted (i.e., root has degree one) trivalent plane trees with 2n + 2 vertices"

so I have thought that the term "planted" means exactly that, that the
tree (whether binary (= trivalent) or general), is "planted" on a
top of the single "stem" |
_not_ that it cannot be reflected as a whole, as you indicate.
(Because being "planar", it is already forbidden).

And also, I assume the terms "plane", "planar" and "oriented" (cf. A000108)
are synonyms, as well as their antonyms "non-planar" and "non-oriented" (cf. A000081).
Am I correct?

I guess we could create a "tree matrix", where we have all the combinations
of labeled/unlabeled, rooted/non-rooted, planar/non-planar, binary/general
trees, with each entry pointing to the corresponding enumerating EIS-sequence.
(will do that, when I have spare time...)


Terveisin,

Antti