[seqfan] Re: looking for bijections

Antti Karttunen antti.karttunen at gmail.com
Wed Jun 9 13:11:04 CEST 2010

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

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.


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

(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
(And thus having "low rate" in some puzzle competition.)



> 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/>)
> >

More information about the SeqFan mailing list