next up previous
Next: About this document ...

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''.





Jeffrey Shallit 2005-03-02