[seqfan] Re: looking for bijections

[Antti Karttunen]

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


For a "non-standard" way of mapping between
Dyck words and binary trees try

http://www.research.att.com/~njas/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/>)
> >
>
>