A combinatorial interpretation for a super-Catalan recurrence
J. Integer Seq. 8(1), Art. 05.1.8, 7 p., electronic only (2005)
Summary
Summary: 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".
