\documentclass[12pt,reqno]{article} %\usepackage[usenames]{color} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} %\definecolor{webgreen}{rgb}{0,.5,0} %\definecolor{webbrown}{rgb}{.6,0,0} %\usepackage{color} %\usepackage{fullpage} %\usepackage{float} %\usepackage{psfig} %\usepackage{graphics,amsmath,amssymb} %\usepackage{amsfonts} %\usepackage{latexsym} \usepackage{epsf} \usepackage{amsmath,amsthm} \usepackage{latexsym} \usepackage{pstricks,pstcol,pst-node} \usepackage{color} \usepackage{xspace} % load hyperref last %\usepackage[colorlinks=true, %linkcolor=green, %filecolor=brown, %citecolor=green]{hyperref} \def\red{\textcolor{red} } \def\v{\vert} \def\incs{inclined twinsteps} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf A Combinatorial Interpretation for a Super-Catalan Recurrence } \vskip 1cm \large David Callan \\ Department of Statistics\\ University of Wisconsin-Madison\\ Medical Science Center\\ 1300 University Ave.\\ Madison, WI 53706-1532\\ USA\\ \href{mailto:callan@stat.wisc.edu}{\tt callan@stat.wisc.edu} \\ \end{center} \vskip .2 in \begin{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''. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] \section{Introduction} For fixed integer $m\ge 1$, the numbers \[ u_{n}=\frac{\binom{2m}{m} \binom{2n}{n} }{2\binom{m+n}{m}} \] satisfy the recurrence relation \begin{equation} u_{n}=\sum_{k\ge 0}2^{n-m-2k} \binom{n-m}{2k}u_{k} \label{eq1} \end{equation} and hence are integers except when $m=n=0$ \cite{superballot}. We will call them {\it super-Catalan numbers of order} $m$ (although other numbers go by this name too). For $m=0$ and $n\ge 1$, they are the odd central binomial coefficients $(1,3,10,35,\ldots)$ (Sloane's \seqnum{A001700}, and count lattice paths of $n$ upsteps and $n-1$ downsteps. For $m=1$ and $n\ge 0$, they are the familiar Catalan numbers $(1,1,2,5,14,42,\ldots)$ (Sloane's \seqnum{A000108}) with numerous combinatorial interpretations \cite[Ex 6.19]{ec2}. Three recent papers give combinatorial interpretations for $m=2$, in terms of (i) pairs of Dyck paths \cite{gesselxin04}, (ii) ``blossom trees'' \cite{schaeffer03}, and (iii) ``aligned cubic trees'' \cite{pippenger}. In this case the sequence is $(3,2,3,6,14,36, \ldots)$ and is Sloane's \seqnum{A007054}. The object of this note is to establish a combinatorial interpretation of the recurrence (\ref{eq1}) for $m=2$: it counts the just mentioned aligned cubic trees by number of vertices that are neither a leaf nor adjacent to a leaf. For $m=1$, (\ref{eq1}) is known as Touchard's identity, and in Section 2 we recall combinatorial interpretations of the recurrence for the cases $m=0,1$. In Section 3 we define aligned cubic trees and establish notation. In Section 4 we introduce configurations counted by the right side of (\ref{eq1}) for $m=2$, and in Section 5 we exhibit a bijection from them to size-$n$ aligned cubic trees. \vspace*{3mm} \section{Recurrence for \emph{m}\,=\:0,\,1 } For $m=0$, (\ref{eq1}) counts lattice paths of $n$ upsteps ($U$) and $n-1$ downsteps ($D$) by number $k$ of $DUU$s where, for example, $DDUUUDDUU$ has 2 $DUU$s. It also counts paths of $n$ $U$s and $n$ $D$s that start up by number $2k$ (necessarily even) of \incs\ ($UU$ or $DD$) at \emph{odd} locations. For example, $U_{\textrm{{\,\tiny 1\,}}}U_{\textrm{{\,\tiny 2\,}}}U_{\textrm{{\,\tiny 3\,}}} D_{\textrm{{\,\tiny 4\,}}}D_{\textrm{{\,\tiny 5\,}}}D$ has four \incs, at locations $1,2,4$ and 5, but only the first and last are at odd locations. For $m=1$, (\ref{eq1}) counts Dyck $n$-paths (paths of $n\ U$s and $n\ D$s that never dip below ground level) by number $k$ of $DUU$s. It also counts them by number $2k$ of \incs\ at \emph{even} locations. See \cite{twobij04}, for example, for relevant bijections. Recall the standard ``walk-around'' bijection from full binary trees on $2n$ edges to Dyck $n$-paths: a worm crawls counterclockwise around the tree starting just west of the root and when an edge is traversed for the first time, records an upstep if the edge is west-leaning and a downstep if it is east-leaning. This bijection carries deep interior vertices to $DUU$s where deep interior means ``neither a leaf nor adjacent to a leaf''. Hence the recurrence also counts full binary trees on $2n$ edges by number of deep interior vertices. The interpretation for $m=2$ below is analogous to this one. \section{Aligned cubic trees} It is well known that there are $C_{n}$ (Catalan number) full binary trees on $2n$ edges. Considered as a graph, the root is the only vertex of degree 2 when $n \ge 1$. To remedy this, add a vertical planting edge to the root and transfer the root to the new vertex. Now every vertex has degree 1 or 3 and, throughout this paper, we will refer to a vertex of degree 3 as a \emph{node} and of degree 1 as a \emph{leaf}. Thus our planted tree of $2n+1$ edges has $n$ nodes. Leave the root edge pointing South and align the other edges so that all three angles at each node are $120^{\circ}$, lengthening edges as needed to avoid self intersections. Rotate these objects through multiples of $60^{\circ}$ to get all ``rooted aligned cubic'' trees on $n$ nodes ($6C_{n}$ of them, since the edge from the root is no longer restricted to point South but may point in any of 6 directions). Now erase the root on each to get all (unrooted) aligned cubic trees on $n$ nodes ($\frac{6}{n+2}C_{n}$ of them since for each, a root could be placed on any of its $n+2$ leaves). Thus two drawings of an aligned cubic tree are equivalent if they differ only by translation and length of edges. This is interpretation (iii) of the second order super-Catalan numbers mentioned in the Introduction. For short, we will refer to an aligned cubic tree on $n$ nodes simply as an $n$-ctree (c for cubic). More concretely, a rooted $n$-ctree can be coded as a pair $(r,u)$ with $r$ an integer mod 6 and $u$ a nonnegative integer sequence of length $n+2$. The integer $r$ gives the angle (in multiples of $60^{\circ}$) from the direction South counterclockwise to the direction of the edge from the root. The sequence $u=(u_{i})_{i=1}^{n+2}$ measures distance between successive leaves: traverse the tree in preorder (a worm crawls counterclockwise around the tree starting at a point just right of the root when looking from the root along the root edge). Then $u_{i}=v_{i}-2$ where $v_{i}\ (\ge 2)$ is the number of edges traversed between the $i$th leaf and the next one. For example, the sketched 3-ctree when rooted at $A$ is coded by $\left(2,(3,0,1,1,1,0)\right)$ and when rooted at $B$ is coded by $\left(1,(0,1,1,1,0,3)\right)$. \begin{center} \psset{xunit=.6cm,yunit=.6cm} \pspicture*(-3,-1)(4,9) \rput{*0}(-2.2,3){$B$} \rput{*0}(-2.2,5){$A$} \dotnode(0,8){a1} \dotnode(0,6){b1} \dotnode(3.46,6){b2} \dotnode(-1.73,5){c1} \dotnode(1.73,5){c2} \dotnode(-1.73,3){d1} \dotnode(1.73,3){d2} \dotnode(0,2){e1} \dotnode(3.46,2){e2} \dotnode(0,0){f1} \ncline{b1}{a1} \ncline{b1}{c1} \ncline{b1}{c2} \ncline{b2}{c2} \ncline{d2}{c2} \ncline{d2}{e1} \ncline{d2}{e2} \ncline{e1}{d1} \ncline{e1}{f1} \endpspicture \end{center} In general, if a ctree rooted at a given leaf is coded by $\left(r,(u_{1},u_{2},\ldots,u_{n+1},u_{n+2})\right)$ then, when rooted at the next leaf in preorder, it is coded by $( (2+r-u_{1})$\,mod\,6$,(u_{2},u_{3},\ldots,u_{n+2},u_{1}))$. Repeating this $n+2$ times all told rotates $u$ back to itself and gives ``$r$''\,$=2n+4+r-\sum_{i=1}^{n+2}u_{i}$ mod 6. Since $\sum_{i=1}^{n+2}u_{i}$ is necessarily $=2n-2$, we are, as expected, back to the original coding sequence. An ordinary (planted) full binary tree is coded by $(0,u)$ and so there are $C_{n}$ coding sequences of length $n+2$. They can be generated as follows. A ctree can be built up by successively adding two edges to a leaf to turn it into a node. The effect this has on the coding sequence is to take two consecutive entries $u_{i},u_{i+1}$ (subscripts modulo $n+2$) and replace them by the three entries $u_{i}+1,\,0,\,u_{i+1}+1$. The 1-ctree has coding sequence (0,0,0). The 2-ctree coding sequences are (1,0,1,0) and (0,1,0,1), and so on. Reversing this procedure gives a fast computational method to check if a given $u$ is a coding sequence or not. For example, successively pruning the first 0, $11210230 \rightarrow 1120130 \rightarrow 111030 \rightarrow 11020 \rightarrow 1010 \rightarrow 000$ is indeed a coding sequence. However, we will work with the graphical depiction of a ctree. The $n$-ctrees for $n=0,1,2$ are shown below. Note that since edges have a fixed non-horizontal direction, we can distinguish a top and bottom vertex for each edge. \begin{center} \psset{xunit=.5cm,yunit=.5cm} \pspicture*(-8,4)(8,9) \rput{*0}(-5,6){$n=0:$} \dotnode(.27,6){A} \dotnode(2,7){B} \dotnode(3.73,6){C} \dotnode(-2,5){D} \dotnode(2,5){E} \dotnode(5.46,5){F} \ncline{A}{D} \ncline{B}{E} \ncline{C}{F} \endpspicture \pspicture*(-6,4)(8,9) \rput{*0}(-4,6){$n=1:$} \dotnode(-2,8){G} \dotnode(1.46,8){H} \dotnode(4.46,8){I} \dotnode(-.27,7){J} \dotnode(4.46,6){K} \dotnode(-.27,5){L} \dotnode(2.73,5){M} \dotnode(6.19,5){N} \ncline{J}{G} \ncline{J}{H} \ncline{J}{L} \ncline{K}{I} \ncline{K}{M} \ncline{K}{N} \endpspicture \end{center} \begin{center} \psset{xunit=.6cm,yunit=.6cm} \pspicture*(-12,-1)(12,5.5) \rput{*0}(-10,3){$n=2:$} \dotnode(-7.46,5){a1} \dotnode(-4,5){a2} \dotnode(0,5){a3} \dotnode(9.16,5){a4} \dotnode(-5.73,4){b1} \dotnode(0,3){b2} \dotnode(3.46,3){b3} \dotnode(5.73,3){b4} \dotnode(9.16,3){b5} \dotnode(-5.73,2){c1} \dotnode(-1.73,2){c2} \dotnode(1.73,2){c3} \dotnode(7.43,2){c4} \dotnode(10.89,2){c5} \dotnode(-7.46,1){d1} \dotnode(-4,1){d2} \dotnode(1.73,0){d3} \dotnode(7.43,0){d4} \ncline{a1}{b1} \ncline{a2}{b1} \ncline{c1}{b1} \ncline{c1}{d1} \ncline{c1}{d2} \ncline{a3}{b2} \ncline{c2}{b2} \ncline{c3}{b2} \ncline{c3}{d3} \ncline{c3}{b3} \ncline{a4}{b5} \ncline{c4}{b5} \ncline{c5}{b5} \ncline{c4}{d4} \ncline{c4}{b4} \endpspicture \end{center} It is convenient to introduce some further terminology. Recall a node is a vertex of degree 3. A node is \emph{hidden, exposed, naked} or \emph{stark naked} according as its 3 neighbors include $0,1,2$ or 3 leaves. Thus a deep interior vertex is just a hidden node. A 0-ctree has no nodes. Only a 1-ctree has a stark naked node, and hidden nodes don't occur until $n\ge 4$. For $n\ge 2$, an $n$-ctree containing $k$ hidden nodes has $k+2$ naked nodes and hence $n-2k-2$ exposed nodes. The terms right and left can be ambiguous: we always use right and left relative to travel \emph{from} a specified vertex or edge. Thus vertex $B$ below is left (not right!) travelling from vertex $A$. \vspace*{-30mm} \hspace*{40mm}\pspicture*(-2,0)(2,6.5) \psset{xunit=.5cm,yunit=.5cm} \dotnode(0,5){a3} \dotnode(0,3){b2} \dotnode(-1.73,2){c2} \dotnode(1.73,2){c3} \ncline{a3}{b2} \ncline{c2}{b2} \ncline{c3}{b2} \rput(0,5.6){$A$} \rput(2.2,2){$B$} \endpspicture \\ Each $n$-ctree has a unique center, either an edge or a node, defined as follows. For $n=0$, it is the (unique) edge in the ctree. For $n=1$, it is the (unique) node in the ctree. For $n\ge 2$, delete the leaves (and incident edges) adjacent to each naked node, thereby reducing the number of nodes by at least 2. Repeat until the $n=0$ or 1 definition applies. Equivalently, define the depth of a node in a ctree to be the length (number of edges) in the shortest path from the node to a naked node. Then there are either one or two nodes of maximal depth; if one, it is the center and if two, they are adjacent and the edge joining them is the center. \section{(\emph{n\,,\,k})-Configurations} There are $\binom{n-2}{2k}2^{n-2-2k}u_{k}$ configurations formed in the following way. Start with a $k$-ctree---$u_{k}$ choices. Break a strip of $n-2-2k$ squares---$\underbrace{\Box\!\Box\!\Box\!\Box \ldots \Box\!\Box}_{n-2-2k}$---into $2k+1$ (possibly empty) substrips, one for each of the $2k+1$ edges in the $k$-ctree---$\binom{(n-2-2k)+(2k+1)-1}{n-2-2k}=\binom{n-2}{2k}$ choices. Mark each square $L\,(=$ left) or $R\,(=$ right)---$2^{n-2-2k}$ choices. Actually, this is not quite what we want. Perform one little tweaking: if there is a center edge and it has an \emph{odd-length} strip of squares, mark the first square $T\,(=$ top) or $B\,(=$ bottom) instead of $L$ or $R$. So a configuration might look as follows ($n=12,\,k=2$, empty strips not shown). \begin{center} \psset{xunit=.6cm,yunit=.6cm} \pspicture*(-2,-1)(3,5) \dotnode(-1.73,4){a} \dotnode(1.73,4){b} \dotnode(0,3){c} \dotnode(0,1){d} \dotnode(-1.73,0){e} \dotnode(1.73,0){f} \ncline{a}{c} \ncline{c}{b} \rput{*0}(2.1,3.3){{\tiny \fbox{$R$}\fbox{$L$} } } \ncline{d}{e} \ncline{c}{d} \rput{*0}(1.4,2){{\tiny \fbox{$B$}\fbox{$L$}\fbox{$L$} } } \ncline{d}{f} \rput{*0}(2.0,0.6){{\tiny \fbox{$R$} } } \endpspicture \end{center} {\Large \textbf{5 \quad Bijection} } Here is a bijection from $(n,k)$-configurations to $n$-ctrees with $k$ hidden nodes. The bijection produces the correspondences in the following table. \begin{center} \begin{tabular}{cc} \textbf{(\emph{n,k})-configuration} & \textbf{\emph{n}-ctree} \\ leaf & naked node \\ node & hidden node \\ square & exposed node \\ \end{tabular} \end{center} Roughly speaking, work outward from the center, turning a strip of $j$ labeled squares on an edge $AB$ into $j$ exposed nodes lying between $A$ and $B$. First, for the center edge (if there is one), the procedure depends on whether it has an even or odd number of squares. \textbf{Case Even}\quad Here, the center edge becomes an edge joining two exposed nodes as shown: the labels again indicate the $L/R$ status (travelling from the center edge) of the leaves associated with the exposed nodes. The labels are applied from the bottom vertex subtree $(H_{2})$ to the top one $(H_{1})$. \begin{center} \pspicture*(-4,-1)(4,4.5) \psset{xunit=.6cm,yunit=.6cm} \dotnode(-1,2){a} \dotnode(.73,3){b} \ncline[linewidth=.06]{a}{b} \rput{*0}(-0.6,3.2){{\scriptsize center }} \rput{*0}(-0.7,2.7){{\scriptsize edge}} \rput{*0}(-1.1,1.4){$H_{2}$} \rput{*0}(1.1,3.4){$H_{1}$} \rput{*0}(4.5,3){$\longrightarrow$} \rput{*0}(1.9,2.3){{\tiny \fbox{$L$}\fbox{$L$}\fbox{$L$}\fbox{$R$} } } \endpspicture \pspicture*(-3,-1)(6,4.5) \psset{xunit=.6cm,yunit=.6cm} \rput{*0}(-2.56,5.5){$H_{2}$} \rput{*0}(5.1,3.1){$H_{1}$} \rput{*0}(-3.3,2.2){{\scriptsize $L$}} \rput{*0}(-.53,1){{\scriptsize $L$}} \rput{*0}(1.2,4){{\scriptsize $L$}} \rput{*0}(2.93,1){{\scriptsize $R$}} \dotnode(-2.46,5){a1} \dotnode(1,5){a2} \dotnode(-2.46,3){b1} \dotnode(1,3){b2} \dotnode(4.46,3){b3} \dotnode(-4.19,2){c1} \dotnode(-.73,2){c2} \dotnode(2.73,2){c3} \dotnode(-.73,0){d1} \dotnode(2.73,0){d2} \ncline{a1}{b1} \ncline{c2}{b1} \ncline{c1}{b1} \ncline{a2}{b2} \ncline{c2}{d1} \red{ \ncline[linewidth=.06]{c2}{b2}} \ncline{c3}{b2} \ncline{c3}{d2} \ncline{c3}{b3} \endpspicture \end{center} \textbf{Case Odd}\quad Here, the center edge becomes a leaf edge. The first square indicates whether the top or bottom vertex becomes a leaf. Construct equal numbers of exposed nodes on each side of the non-leaf (here, top) vertex, using the $L/R$ designations to determine the leaves ($L/R$ relative to travel from the leaf and running, say, from the left branch to the right). \begin{center} \pspicture*(-5,0)(4,4) \psset{xunit=.6cm,yunit=.6cm} \dotnode(0,5.3){c} \dotnode(0,2.3){d} \rput{*0}(0.0,5.7){$H_{1}$} \rput{*0}(0.0,1.7){$H_{2}$} \rput{*0}(5,4){$\longrightarrow$} \rput{*0}(-0.8,4.2){{\scriptsize center }} \rput{*0}(-0.8,3.7){{\scriptsize edge}} \ncline[linewidth=.06]{c}{d} \rput{*0}(1.55,4){{\tiny \fbox{$B$}\fbox{$L$}\fbox{$L$} } } \endpspicture \pspicture*(-3,-1)(4,3.5) \psset{xunit=.6cm,yunit=.6cm} \dotnode(-1.73,5){a} \dotnode(1.73,5){b} \dotnode(-1.73,3){c} \dotnode(1.73,3){d} \dotnode(-3.46,2){e} \dotnode(0,2){f} \dotnode(3.46,2){g} \dotnode(0,0){h} \ncline{c}{a} \ncline{c}{e} \ncline{c}{f} \ncline{b}{d} \ncline{f}{d} \ncline{g}{d} \ncline[linewidth=.06]{f}{h} \rput{*0}(0,-.35){{\scriptsize leaf}} % \rput{*0}(1.5,1){old center edge} \rput{*0}(-2.4,2.3){{\scriptsize $L$}} \rput{*0}(1.5,4){{\scriptsize $L$}} \rput{*0}(-1.73,5.5){$H_{2}$} \rput{*0}(3.8,1.5){$H_{1}$} \endpspicture \end{center} Decide the placement of the two subtrees $H_{1},H_{2}$, say the $H$ originally sitting at the vertex which is now a leaf goes at the end of the left branch from the leaf. Next, for a non-center edge with $i\ge 0$ squares, identify its endpoint closest to the center, let $H_{0},H_{1},H_{2}$ be the subtrees as illustrated ($H_{0}$ containing the center), and insert $i$ exposed nodes as shown. The labels $L,L,R$ apply in order from $H_{1}$-$H_{2}$ to $H_{0}$ and indicate the $L/R$ status (travelling from the center) of the leaves associated with the exposed nodes. \begin{center} \psset{xunit=.6cm,yunit=.6cm} \pspicture*(-14,-1)(7,7) \dotnode(-1.73,6){a1} \dotnode(1.73,6){a2} \dotnode(-10.73,5){b1} \dotnode(0,5){b2} \dotnode(3.46,5){b3} \dotnode(-10.73,3){c1} \dotnode(0,3){c2} \dotnode(3.46,3){c3} \dotnode(-12.46,2){d1} \dotnode(-9,2){d2} \dotnode(-1.73,2){d3} \dotnode(1.73,2){d4} \dotnode(5.19,2){d5} \dotnode(1.73,0){e1} \ncline{c1}{b1} \ncline{c1}{d1} \ncline[linewidth=.06]{c1}{d2} \ncline{a1}{b2} \ncline{a2}{b2} \ncline{c2}{b2} \ncline{c2}{d3} \ncline{c2}{d4} \ncline{c3}{d4} \ncline{e1}{d4} \ncline{c3}{b3} \ncline[linewidth=.06]{c3}{d5} \rput{*0}(-10.73,5.5){$H_{2}$} \rput{*0}(-12.56,1.4){$H_{1}$} \rput{*0}(-8.9,1.4){$H_{0}$} \rput{*0}(-8.6,0.8){{\scriptsize(center) }} \rput{*0}(-5,4){$\longrightarrow$} \rput{*0}(-1.73,6.5){$H_{1}$} \rput{*0}(1.73,6.5){$H_{2}$} \rput{*0}(5.8,2){$H_{0}$} \rput{*0}(2.1,1){{\scriptsize $L$}} \rput{*0}(3.85,4){{\scriptsize $R$}} \rput{*0}(-1.4,2.7){{\scriptsize $L$}} \rput{*0}(-7.9,2.7){{\tiny \fbox{$L$}\fbox{$L$}\fbox{$R$} } } \endpspicture \end{center} Finally, turn the original leaves into naked nodes by adding two edges apiece. We leave to the reader to verify that the resulting ctree has $n$ nodes of which $k$ are hidden, and that the original configuration can be uniquely recovered from this $n$-ctree by reversing the above procedure, working in from the leaves. \begin{thebibliography}{99} \bibitem{superballot} Ira Gessel, \htmladdnormallink{Super ballot numbers}{http://www.cs.brandeis.edu/~ira/}, \emph{J. Symbolic Computation} \textbf{14} (1992), 179--194. \bibitem{ec2} Richard P.~Stanley, \emph{Enumerative Combinatorics Vol.\,2}, Cambridge University Press, 1999. Exercise 6.19 and related material on Catalan numbers are available online at \htmladdnormallink{http://www-math.mit.edu/$\sim$rstan/ec/ }{http://www-math.mit.edu/~rstan/ec/}. \bibitem{gesselxin04} Ira M. Gessel and Guoce Xin, A combinatorial interpretation of the numbers $6(2n)!/(n!(n+2)!)$, \htmladdnormallink{math.CO/0401300}{http://front.math.ucdavis.edu/math.CO/0401300}, 2004, 11pp. \bibitem{schaeffer03} Gilles Schaeffer, A combinatorial interpretation of super-Catalan numbers of order two, \htmladdnormallink{Manuscript}{http://www.lix.polytechnique.fr/Labo/Gilles.Schaeffer/Biblio/}, 2003, 4pp. \bibitem{pippenger} Nicholas Pippenger and Kristin Schleich, Topological Characteristics of Random Triangulated Surfaces, \emph{Random Structures \& Algorithms}, to appear, \htmladdnormallink{arXiv:gr-qc/0306049}{http://arxiv.org/pdf/gr-qc/0306049}, 2003, 58 pp. \bibitem{twobij04} David Callan, Two bijections for Dyck path parameters, \htmladdnormallink{math.CO/0406381}{http://front.math.ucdavis.edu/math.CO/0406381}, 2004, 4pp. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A19; Secondary 05A15. \noindent \emph{Keywords: } super-Catalan, aligned cubic tree. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000108}, \seqnum{A001700}, and \seqnum{A007054}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received February 1 2005; revised version received March 2 2005. Published in {\it Journal of Integer Sequences}, March 2 2005. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \vskip .1in \end{document}