je-ne-sais-quoi, again...

[Wouter Meeussen]

trees : depth first or width first :
example:

	         1

      1                1

  0      1        1         1
        0 0      0 0      0    1
                              0 0

depth first (carterpillar-wise) is
 ( 1( 1 0 (1 0 0) ) (1 (1 0 0) (1 0 (100) ) ) )
width first  is row-by-row:
  (1)(1 1) (0111)(00 00 01)(00)

of course, the running count of ones is bigger or equal to the running 
count of zero's, in both representations.
So, we can treat this 'rearrangement' of zero's and ones as a symmetry 
operation on the wood of all ordered trees with n leaves.

This leads to the question how the cat[n] trees (depth first) are permuted 
by this symmetry operation (since it's a 1 on 1 correspondance).

It should not come as a surprise that bigger woods are just an extension of 
smaller ones. So, the cycle structure of the above permutation for any wood 
should have the same 'leading terms' and we only need the last one for full 
information:

Length of each cycle: (first row = wood[1])

{1},
{1, 1},
{1, 1, 3},
{1, 1, 3, 4, 3, 2},
{1, 1, 3, 4, 3, 2, 16, 8, 2, 2},
{1, 1, 3, 4, 3, 2, 16, 8, 2, 2, 87, 3},
{1, 1, 3, 4, 3, 2, 16, 8, 2, 2, 87, 3, 202, 25, 5, 4, 61},
{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},
{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}

It is self-evident that the row-sums here must be the catalans, since the 
sum of the cycle-lengths gives the total number of elements (trees) to be 
permuted.

The number of cycles for each wood is increasing in a funny fashion:

{1, 2, 3, 6, 10, 12, 17, 26, 34, ...}

this could be used as an index-list:
the 1st, 2nd, 3rd, 6th .. first terms of {1,1,3,4,3,2,16,8,2,2,..} sum to 
the 1st, 2nd, 3rd, 6th catalan.




Wouter Meeussen
tel +32 (0)51 33 21 24
fax +32 (0)51 33 21 75
w.meeussen at vandemoortele.be