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

Wouter Meeussen w.meeussen.vdmcc at vandemoortele.be
Tue May 2 20:02:32 CEST 2000

```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

```