[seqfan] Re: looking for bijections

[wouter meeussen]

1976, september (or october),
with, I believe, monkeys or apes on the cover,
;-))

Wouter.


----- Original Message ----- 
From: "Antti Karttunen" <antti.karttunen at gmail.com>
To: <seqfan at list.seqfan.eu>
Cc: "Emeric Deutsch" <deutsch at poly.edu>
Sent: Wednesday, June 09, 2010 1:17 PM
Subject: [seqfan] Re: looking for bijections


> And of course, for a standard way of converting from
> binary trees to Dyck words, there is that caterpillar
> traversing the binary tree depth-first-wise from left to right,
> as presented by Martin Gardner in his Sci-Am 197? column.
> (I have the photocopies, but I have lost the copy of the
> cover, so I miss the exact year. 1976 or 1977? Wouter,
> do you remember? ;-)
>
>
> Cheers,
>
> Same.
>
> On Wed, Jun 9, 2010 at 2:11 PM, Antti Karttunen
> <antti.karttunen at gmail.com>wrote:
>
> >
> >
> > On Wed, Jun 9, 2010 at 4:56 AM, <seqfan-request at list.seqfan.eu> wrote:
> >
> >>
> >> Message: 7
> >> Date: Fri, 04 Jun 2010 23:07:03 -0400
> >> From: "Emeric Deutsch" <deutsch at poly.edu>
> >> Subject: [seqfan]  looking for bijections
> >> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> >> Message-ID: <4c09bf57.2c1.3cc40.28897 at duke.poly.edu>
> >>
> >> Dear Seqfans,
> >> I'd appreciate references to known bijections between
> >> full binary trees with n internal nodes and Dyck paths of
> >> length 2n.
> >> Thanks,
> >> Emeric
> >>
> >>
> > Do you want direct bijections or is one allowed to go via some other
> > Catalan incarnation (e.g. general trees)?
> >
> > For binary trees <-> general trees, try some old paper by Donaghey.
(I'll
> > try to find the exact reference). However, the same mapping is
implicitly
> > used when converting between the "internal" "dotted pair" and "external"
> > list-notations of Lisp programming language, which roots going back to
the
> > fifties.
> >
> > For general trees <-> Dyck paths, one can use the straightforward
"flooding
> > scheme" presented in
> > D.L. Kreher and D.R. Stinson,
> > Combinatorial Algorithms: Generation, Enumeration and Search,
> > CRC press LTC, Boca Raton, Florida, 1998.
> >
> >
http://www.math.mtu.edu/~kreher/cages.html<http://www.math.mtu.edu/%7Ekreher/cages.html>
> >
> >
> > For a "non-standard" way of mapping between
> > Dyck words and binary trees try
> >
> >
http://www.research.att.com/~njas/sequences/A085184<http://www.research.att.com/%7Enjas/sequences/A085184>
> > (I don't know whether anybody has invented this before me.)
> >
> >
> >> ------------------------------
> >>
> >> Message: 16
> >> Date: Tue, 8 Jun 2010 11:47:47 -0400
> >> From: Max Alekseyev <maxale at gmail.com>
> >> Subject: [seqfan] Re: looking for bijections
> >>
> >> Actually, this bijection is rated quite low in Stanley's "Bijective
> >> proof problems" list:
> >>
http://www-math.mit.edu/~rstan/bij.pdf<http://www-math.mit.edu/%7Erstan/bij.pdf>
> >> See problems 155 and 159 there.
> >> Max
> >>
> >>
> > It's still very useful and important bijection, even if it is obvious to
> > see!
> > (And thus having "low rate" in some puzzle competition.)
> >
> > Cheers,
> >
> > Antti
> >
> >
> >
> >> On Tue, Jun 8, 2010 at 4:47 AM, Joerg Arndt <arndt at jjj.de> wrote:
> >> > I'd suggest to ask Stanley (though no
> >> > historical references are given in his well known
> >> > documents at
http://www-math.mit.edu/~rstan/ec/<http://www-math.mit.edu/%7Erstan/ec/>)
> >> >
> >>
> >>
> >
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
> __________ NOD32 5185 (20100609) Informatie __________
>
> Dit bericht is gecontroleerd door het NOD32 Antivirus Systeem.
> http://www.nod32.nl
>
>