\documentclass[12pt]{article}

\usepackage{amsmath}

\begin{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''.

\end{document}