Necklaces of binary trees.

[karttu at megabaud.fi]

Dear SeqFans,

Using a generalization of Raney's lemma
(for an obscure reference, see
http://dept-info.labri.u-bordeaux.fr/~dutour/CSA/Resumes/delristoro.ps.gz
 From http://www.maths.usyd.edu.au:8000/u/tims/halfies/15081997.html
I also guess that this has something to do with Lagrange's Inversion
Formula.)

it is clear that if we have a necklace of
n black beads and n+k white beads, i.e. as the columns
of A047996 give:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A047996

then it is equal of having a necklace of k plane binary trees,
such that the number of their branching (root + internal) nodes
total n (which means that the number of leaves total n+k).
Note that those binary trees, although they can be rotated
_around_ the necklace, cannot be rotated at their root,
from which they are connected to the string of necklace,
i.e. they preserve their orientation in that sense.
(How about an exposition of combinatorial jewellery and
handicraft to make this clear?)


So, using the combstruct-package developed by the Algorithms
project of Inria, and bundled with Maple, it is easy to check
these empirically (and aren't these then also some of
the C?? transformations given by Christian G. Bower in
http://www.research.att.com/~njas/sequences/transforms2.html
of Catalan numbers?).


> with(combstruct);

     [allstructs, count, draw, finished, iterstructs, nextstruct]

There are many combstruct specifications giving Catalan numbers A000108,
(see The Encyclopedia of Combinatorial Structures at 
http://algo.inria.fr/bin/encyclopedia if it only would respond...)
e.g. we have one corresponding to general plane trees:

> [seq(combstruct[count]([A, {A=Prod(Z,Sequence(A))}],size=n),n=0..12)];

     [0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786]

and the next one corresponding more to what we actually have in mind,
the unlabelled, rooted, plane (= oriented) binary trees, this time counted
by leaves, not by the internal branching nodes:

> [seq(combstruct[count]([BT, {BT=Union(Z,Prod(BT,BT))}],size=n),n=0..12)];

     [0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786]

Now, we construct a cycle (i.e. necklace) of those binary trees,
with any number of binary trees allowed, so that the size =
total number of leaves, and we get A003239:
 
> [seq(combstruct[count]([C, {C=Cycle(BT),BT=Union(Z,Prod(BT,BT))}],size=n),n=0..12)];

    [0, 1, 2, 4, 10, 26, 80, 246, 810, 2704, 9252, 32066, 112720]

which also occurs as the central column in the triangle A047996.

                    -----------------------------

If we have only one binary tree allowed in the necklaces,
then the result is of course the Catalans again:
> [seq(combstruct[count]([C, {C=Cycle(BT,card=1),BT=Union(Z,Prod(BT,BT))}],size=n),n=0..12)];

     [0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786]

which occurs as the next-to-central columns of A047996.

                    -----------------------------

Allowing exactly two binary trees in necklace, we get A007595,
the next^2-to-central columns in A047996:
(something has to be done with the indices, to avoid
shifting to the right as is happening here.)

> [seq(combstruct[count]([C, {C=Cycle(BT,card=2),BT=Union(Z,Prod(BT,BT))}],size=n),n=0..12)];

       [0, 0, 1, 1, 3, 7, 22, 66, 217, 715, 2438, 8398, 29414]

and this time it is easy to construct a bijection to combinatorial
objects we know A007595 already corresponds to, the plane binary trees
upto the reflection: From either of the two possible rotations
of this 2-tree necklace, stick the first binary tree to the left
hand branch of \/, and the _reflection_ of the second binary tree
to the right hand branch of \/, so we know that if we start
this mapping from the other rotation of the necklace, we will
get a mirror image of the other one. Also, both rotations map
to the same binary tree only if the two trees hanging from the
necklace are identical.

                    -----------------------------

And allowing three binary trees in necklace, is equivalent of
having a binary necklace of n black and n+3 white beads, and
we get A003441, as Wouter already observed:

> [seq(combstruct[count]([C, {C=Cycle(BT,card=3),BT=Union(Z,Prod(BT,BT))}],size=n),n=0..12)];

        [0, 0, 0, 1, 1, 3, 10, 30, 99, 335, 1144, 3978, 14000]


ID Number: A003441 (Formerly M2840)
Sequence:  1,1,3,10,30,99,335,1144,3978,14000,49742,178296,643856,
           2340135,8554275,31429068,115997970,429874830,1598952498,
           5967382200,22338765540
Name:      Dissections of a polygon.
References F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for
              arbitrary polygons, Discr. Math. 11 (1975), 371-389.
           R. C. Read, On general dissections of a polygon, Aequat. Math. 18
              (1978), 370-388.
           P. Lisonek, Closed forms for the number of polygon dissections.
              Journal of Symbolic Computation 20 (1995), 595-601.
Keywords:  nonn
Offset:    1
Author(s): njas


of which sequence it would be nice to have some further
information. E.g. what kind of dissections are meant,
upto what automorphism (if any) of the polygons, etc?



Yours,

Antti Karttunen
going for another cottage for another week.