[seqfan] A002955: rooted trimmed trees

Joerg Arndt arndt at jjj.de
Mon Mar 2 17:55:42 CET 2015


I observe that this sequence (seems to) count
"Unordered rooted trees without "x x" in the level
 sequence for the pre-order walk."

Here are those (8) trees for n = 6:

   1:  [ 0 1 2 3 4 5 ]
O--o--o--o--o--o

   2:  [ 0 1 2 3 4 3 ]
O--o--o--o--o
      .--o

   3:  [ 0 1 2 3 4 2 ]
O--o--o--o--o
   .--o

   4:  [ 0 1 2 3 4 1 ]
O--o--o--o--o
.--o

   5:  [ 0 1 2 3 2 3 ]
O--o--o--o
   .--o--o

   6:  [ 0 1 2 3 2 1 ]
O--o--o--o
   .--o
.--o

   7:  [ 0 1 2 3 1 2 ]
O--o--o--o
.--o--o

   8:  [ 0 1 2 1 2 1 ]
O--o--o
.--o--o
.--o


Now I realize that I do _not_ understand the comments.
My understanding of "limb" is
"the way (subtree) from a leaf towards the root until
 the first branch point (which can be the root) is reached."
Example: The tree
  [ 0 1 2 3 4 2 1 2 1 ]
O--o--o--o--o
   .--o
.--o--o
.--o
has limbs of lengths 4, 1, 2, and 1.

Now from what I read in A002955 it should count
trees without limbs of length 2 (? or length >= 2 ?).
The trees I show above are(?) different, they avoid subtrees
 *--o
 .--o

Can somebody clarify?


Best regards,   jj

P.S.: should "unordered" be added to the name?
P.P.S.: should "free" be added to the names of
  sequences that are about free trees (like A000055)?


More information about the SeqFan mailing list