first child - next sibling

[deutsch]

subject line.
Return-Path: <deutsch at duke.poly.edu>
X-Ids: 165
Sender: deutsch at duke.poly.edu
From: "deutsch" <deutsch at duke.poly.edu>
To: seqfan at ext.jussieu.fr
X-Mailer: Quality Web Email v3.1b, http://netwinsite.com/refw.htm
Date: Mon, 13 Aug 2007 12:23:44 -0400
Message-id: <46c08590.37d.180.24591 at duke.poly.edu>
X-Spam-Status: No, score=-4.1 required=6.0 tests=ALL_TRUSTED,AWL,BAYES_00,
	MISSING_SUBJECT autolearn=ham version=3.1.7
X-Spam-Level: 
X-Spam-Checker-Version: SpamAssassin 3.1.7 (2006-10-05) on duke.poly.edu
X-Virus-Scanned: ClamAV 0.88.7/3947/Mon Aug 13 17:25:28 2007 on shiva.jussieu.fr
X-Virus-Scanned: ClamAV version 0.87, clamav-milter version 0.87 on duke.poly.edu
X-Virus-Status: Clean
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.165]); Mon, 13 Aug 2007 19:10:33 +0200 (CEST)
X-j-chkmail-Score: MSGID : 46C09088.001 on shiva.jussieu.fr : j-chkmail score : XX : 0/50 1 0.760 -> 2
X-Miltered: at shiva.jussieu.fr with ID 46C09088.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
Return-Path: <maharri at gmail.com>
X-Ids: 165
DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed;
        d=gmail.com; s=beta;
        h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=AuIUN1eflR8PECXcoZiYuOfCVRn+6CsQ0dL8wicZeB0kAw4FFwEe2DYJbpqzV6BP593N3fgeSLg3Geeth97FzPFoijlGvTpIAr4xz2HQYeD1Tw6tnmWIdyvuKztB647F/p4IXqqdYs7TQ3Jb+HelxhFvnbniyESMG7AxWLh7YXo=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=rsGsoFcBhXy0jzi+mIsA46icUAG6IvQzDQPcxgQ5bictY9Yk4kg+PPBC6gUI5apHLHIyBkpqRANGsF7nVROIeDF4mj1tjNlKGahQm5aBm6U7Tusr0SjGkkWeCgBY845EZxtad6SgvYwAqwyGW/wjPH9oc/gSDvkM4DALXuI2HMo=
Message-ID: <553db06d0708131235g767bda43u12c6cc50800868ee at mail.gmail.com>
Date: Mon, 13 Aug 2007 15:35:48 -0400
From: "Mitch Harris" <maharri at gmail.com>
To: deutsch <deutsch at duke.poly.edu>
Subject: Re: first child - next sibling
Cc: seqfan at ext.jussieu.fr
In-Reply-To: <46c0875e.1f1.6bc.26096 at duke.poly.edu>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <46c0875e.1f1.6bc.26096 at duke.poly.edu>
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.165]); Mon, 13 Aug 2007 21:35:51 +0200 (CEST)
X-Virus-Scanned: ClamAV 0.88.7/3947/Mon Aug 13 17:25:28 2007 on shiva.jussieu.fr
X-Virus-Status: Clean
X-j-chkmail-Score: MSGID : 46C0B296.001 on shiva.jussieu.fr : j-chkmail score : X : 0/50 1 0.555 -> 1
X-Miltered: at shiva.jussieu.fr with ID 46C0B296.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!

On 8/13/07, deutsch <deutsch at duke.poly.edu> wrote:
>
> Do you know some reference about the so-called "first child
> - next sibling" bijection from ordered trees to binary
> trees?

The classic reference is

 Stanley, Enumerative Combinatorics, vol 2. (1999)

See especially ch 6 thm 6.2.1 and following thms -and- exercise
6.19c,d,e (and really the many others). The latter (ex. 6.19) with
solutions and references is at:

  http://www-math.mit.edu/~rstan/ec/catalan.pdf
  http://www-math.mit.edu/~rstan/ec/catsol.pdf
  http://www-math.mit.edu/~rstan/ec/catadd.pdf

-- 
Mitch Harris