Necklaces of binary trees.

Mon Aug 12 19:06:32 CEST 2002

Example of trees on a necklace:

construct a 2D foam by adding circles (size 1 +/- sigma) to a kernel of 3
circles.
The centers of the 3 circles are connected by lines forming a triangle.

On each side of the triangle, going round anticlockwise, add a circle
tangent to the two circles connected by the line (on the cluster perimeter).

***  either shift the connecting line to the center of the newcomer:

       new                                          new
                               becomes            /     \
---old1---old2---                           --old1       old2---

or, if forced to because of overlap ( 'new' and 'old3' below),

        new      _old3---                  new-------old3---
               _.                         /   \
---old1----old2                     ---old1    old2 

we shift the new circle to become tangent to any potential overlapper.

In this way, building flat foam leads to 'bubble memories' counted by 
necklaces of binary trees.

any other examples 'round?

Wouter Meeussen
email : wouter.meeussen at pandora.be

-----Original Message-----
From: karttu at megabaud.fi [mailto:karttu at megabaud.fi]
Sent: maandag 12 augustus 2002 11:21
To: seqfan at ext.jussieu.fr
Subject: Necklaces of binary trees.

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?An
um=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.

===============================
This email is confidential and intended solely for the use of the individual to whom it is addressed. 
If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited.
You are explicitly requested to notify the sender of this email that the intended recipient was not reached.