Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.8

A Combinatorial Interpretation for a Super-Catalan Recurrence


David Callan
Department of Statistics
University of Wisconsin-Madison
Medical Science Center
1300 University Ave.
Madison, WI 53706-1532
USA

Abstract: Nicholas Pippenger and Kristin Schleich have recently given a combinatorial interpretation for the second-order super-Catalan numbers $ (u_{n})_{n\ge 0}=(3,2,3,6,14,36,...)$: they count "aligned cubic trees" on $ n$ interior vertices. Here we give a combinatorial interpretation of the recurrence $ u_{n} = \sum_{k=0}^{n/2-1}\binom{n-2}{2k}2^{n-2-2k}u_{k}\,:$ it counts these trees by number of deep interior vertices where "deep interior" means "neither a leaf nor adjacent to a leaf".

(Concerned with sequences A000108 A001700 and A007054 .)

Full version:  pdf,    dvi,    ps,    latex    

Received February 1 2005; revised version received March 2 2005. Published in Journal of Integer Sequences March 2 2005.

Return to Journal of Integer Sequences home page