A Combinatorial Interpretation for a Super-Catalan Recurrence
Nicholas Pippenger and Kristin Schleich have recently given a combinatorial interpretation for the
second-order super-Catalan numbers (u_{n})_{n>=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} ({n – 2}choose{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''.
