[seqfan] Re: A002955: rooted trimmed trees

[Joerg Arndt]

* Joerg Arndt <arndt at jjj.de> [Mar 05. 2015 14:25]:
> * Neil Sloane <njasloane at gmail.com> [Mar 03. 2015 15:56]:
> > JJ, I see you used the word "unordered" in your edit of A002955.  Did you
> > mean to say "unlabeled"?
> 
> Edited name:
>   Number of (unordered, unlabeled) rooted trimmed trees with n nodes.
> 
> Ordered vs. unordered (the usual confusing thing):

Now I managed to indeed confuse things:

This...
> For (all) trees, "unordered" is A000081, and "ordered" is A000108.
... is correct

While ...
> Cf. compositions ("unordered") and partitions ("ordered").
... FRONK!  (as Alois pointed out, thanks for that)

> So "ordered" things are presented unordered,
> and "unordered" things are presented ordered.

Let me re-word:

If "order matters" (e.g., compositions, aka "ordered partitions")
the objects in the list look "unordered" (i.e., the components of
the individual objects are potentially in any order).

The compositions of 5:
  [ 1 1 1 1 1 ]
  [ 1 1 1 2 ]
  [ 1 1 2 1 ]
  [ 1 1 3 ]
  [ 1 2 1 1 ]
  [ 1 2 2 ]   <--= This ...
  [ 1 3 1 ]
  [ 1 4 ]
  [ 2 1 1 1 ]
  [ 2 1 2 ]   <--= ... and this ...
  [ 2 2 1 ]   <--= ... and this are different.
  [ 2 3 ]
  [ 3 1 1 ]
  [ 3 2 ]
  [ 4 1 ]
  [ 5 ]


If "order does not matter" (e.g., "partitions" proper) we show
the objects in the list in _some_ order, so the appear "ordered"
(i.e., the components in the order are sorted in the way we choose)..

The partitions of 5:
  [ 1 1 1 1 1 ]
  [ 1 1 1 2 ]
  [ 1 1 3 ]
  [ 1 2 2 ]  <--= Just one!
  [ 1 4 ]
  [ 2 3 ]
  [ 5 ]
Here the order chosen is "weakly ascending", just to
annoy those who think it has to be "weakly descending".


> 
> > 
> > And I don't understand the phrase "pre-order walk"! Could you explain?
> 

I could have written:
do a depth-first traversal and print the nodes
as soon as they are encountered.

> [...]

Regards,  jj