[seqfan] Re: looking for bijections

[Antti Karttunen]

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