need advice

[Wouter Meeussen]

concerning my last mail:
"trees : depth first or width first"

I'm looking for proper terminology, and some "trivia-detection".

item 1.
---------
Is it generally accepted to represent these trees (planar planted binary 
trees?) by their binary form,
and to order them in increasing numerical order (101010..  up front)?
Would an entry in EIS make sense to the "combinatorially literates" without 
explicit reference to this (natural?) ordering? (cfr A014486).
Why ask? The cycle lengths may well be independent of the ordering of the 
trees, but the cycles (ergo cycle lengths) themselves could be generated in 
a different order.

item 2.
---------
In Mathematica's Combinatorica Package, a 'Breadth-First' and 'Depth-First' 
traversal of a Graph is documented. I take it (?) that the same terminology 
can be used here, and that these trees are a 'special kind' of directed 
graph of general interest (?).
It would be most surprising if such matters (1 on 1 correspondance between 
breadth-first and depth-first trees) would not have been published yet, so 
a nice literature reference would be proper (R.P. Stanley ??).

item 3.
----------
Would it make sense to give "the" infinite permutation itself (whose cycle 
structure was discussed above). Since not only the cycle structure (cycle 
lengths) but also the permutation of the cat[n] trees is, how should I put 
this, "conserved" over all woods:
n=2: {1, 2}
n=3: {1, 2, 4, 5, 3}
n=4: {1, 2, 4, 5, 3, 9, 10, 13, 14, 12, 6, 7, 8, 11}
n=5: {1, 2, 4, 5, 3, 9, 10, 13, 14, 12, 6, 7, 8, 11, 23, 24, 27, 28, 26, 
36, 37, 41, 42, 40, 32, 33, 35, 39, 15, 16, 18, 19, 17, 22, 25, 20, 21, 34, 
38, 29, 30, 31}
and so on ..

it is a rearrangement of the integers, in which the cat[n] lowest integers 
fill the first cat[n] places.
What is this property of "conservation" called? I've met it before many 
times : for example, the permutations with rank number xx are involutions, 
independend of the size of the permutation.
Generally, a finite sequence of integers is generated by a finite 
"structure", and the same integer sequence is found *at the start* of those 
generated by a "larger" structure. Is this a noteworthy property, or an 
artefact of the counting strategy?

item last.
-------------
Any suggestions\corrections\ as to this lot? can YOU reconstruct what is 
meant?

-----------------------------------
ID Number: A000000
Sequence:  1, 1, 3, 4, 3, 2, 16, 8, 2, 2, 87, 3, 202, 25, 5, 4, 61, 607, 
63, 165, 127, 12, 8, 10, 4, 5, 927, 1441, 283, 625, 91, 52, 8, 5, 4708, 
592, 1890, 86, 3505, 482, 471, 34, 84, 17, 22, 25, 5, 9, 3, 1
Name:       cycle lengths of the permutation that converts the wood of 
depth-first planar planted binary trees into breadth-first representation.
Formula:
Example:   The first 6 terms add up to 14=cat[4], so the cycle lengths of 
the permutation for wood[4] are {1, 1, 3, 4, 3, 2}. The sequence as given 
(50 terms) was generated on wood[10].
See also:  A000002
Keywords:  nonn
Offset:    1
Author(s): Wouter Meeussen (w.meeussen at vandemoortele.be)
---------------------------------
ID Number: A000001
Sequence:  1, 2, 3, 6, 10, 12, 17, 26, 34, 50
Name:       a[n] is the number of cycles of the permutation that converts 
wood[n] of depth-first planar planted binary trees into breadth-first 
representation. The first a[n] terms of A000000 add up to cat[n].
Formula:
Example:   a[5]=10 since there are 10 cycles in this permutation of 
wood[5], with lengths 1, 1, 3, 4, 3, 2, 16, 8, 2, 2  summing up to 
42=cat[5].
See also:  A000002
Keywords:  nonn
Offset:    1
Author(s): Wouter Meeussen (w.meeussen at vandemoortele.be)
---------------------------------
ID Number: A000002
Sequence: 
 1,2,4,5,3,9,10,13,14,12,6,7,8,11,23,24,27,28,26,36,37,41,42,40,32,33,35  
,39,15,16,18,19,17,22,25,20,21,34,38,29,30,31,65,66,69,70,68,78,79,83,84  
,82,74,75,77,81,106,107,111,112,110,125,126,131,132,130,120,121,124,129,  
93,94,97,98,96,105,109,102,103,123,128,116,117,119,43,44,46,47,45,51,52,  
55,56,54,48,49,50,53,64,67,76,80,73,57,58,62,71,60,61,63,72,59,104,108,1  
22,127,118,85,86,99,113,88,89,100,114,87,92,95,101,115,90,91

Name:       the sequence a[1] to a[ cat[n] ] is the permutation that 
converts wood[n] of depth-first planar planted binary trees into 
breadth-first representation.
Formula:   bracket[tree_]:=(Flatten[{tree,0}]/. 
0->{0})//.{1,z___,1,a_List,b_List,y___}:>{1,z,{1,a,b},y};widthfirst[dect  
ree_]:=b2d[Drop[Flatten[{Table[Cases[Level[# 
,{k},z],_Integer],{k,Depth[#]-1}] }/.z->List],-1]]& 
@(bracket at d2b[dectree]);ToCycles[Ordering[widthfirst/@wood[9]]]; cfr 
functions in A014486.
Example:   tree ( 1 (100) (10 ) ) becomes (1) (11)(00 0 ) thus (1 (1(100) 
0)   )  and is permuted from position 3 in wood[3] to position 5 by 
permutation {1,2,4,5,3}={{1},{2},{4,5,3}}
See also:
Keywords:  nonn
Offset:    1
Author(s): Wouter Meeussen (w.meeussen at vandemoortele.be)
---------------------------------