[seqfan] Re: Definitions of "circular rooted trees, " "series-reduced mobiles, " "cycle rooted trees, " "asymmetric mobiles"
franktaw at netscape.net
franktaw at netscape.net
Sun Sep 18 08:06:54 CEST 2011
Since no one else has answered, I'll give it a try. I'm fairly
confident of these definitions based on looking at the sequences, but I
didn't originate any of these terms, so I might be mistaken in some of
the details.
I assume a basic understanding of graphs and trees, particularly rooted
trees and ordered trees.
"Circular rooted trees" is synonymous with "mobiles"; I think "cycle
rooted trees" is another synonym. A mobile is an intermediate case
between a rooted tree and an ordered tree: the child nodes from a given
parent can be rotated as a whole, but not permuted in other ways. For
example (you'll want to view these with a fixed font),
...o...
../|\..
./.|.\.
o..o..o
...|..|
...|..|
...o..o
......|
......|
......o
is equivalent to
...o...
../|\..
./.|.\.
o..o..o
|..|...
|..|...
o..o...
...|...
...|...
...o...
since the subtrees are rotated left; but these are not equivalent to:
...o...
../|\..
./.|.\.
o..o..o
|..|...
|..|...
o..o...
|......
|......
o......
which differs from either by a non-rotational permutation.
"Series reduced", for any sort of rooted tree, generally means that no
node has only a single child; there may be none, or two or more. (One
can series reduce a rooted tree by repeatedly replacing any node with
exactly one child by its subtree; the result will be independent of the
order in which the replacements are made. Any of the 3 graphs shown
above lead by series reduction to a tree whose root has three children,
each a single node.) (Series reduced has a related but slightly
different meaning for pure graphs, including free trees.)
Basically, asymmetric for a rooted tree means that there are no nodes
with identical subtrees. This is a bit vague, because there is more
than one possible definition, and I'm not sure what the author intends
here.
Franklin T. Adams-Watters
-----Original Message-----
From: Thomas Copeland <tccopeland at gmail.com>
Dear seq. fans,
Where can I find good (preferably illustrated) definitions of the terms
in
the subject line, which are used extensively in the OEIS?
Sincerely,
Tom Copeland
More information about the SeqFan
mailing list