\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{psfrag}
\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,amsthm}
\usepackage{latexsym}
\usepackage{epsf}
\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 of the Numbers $6\,(2n)!\,/n!\,(n+2)!$
}
\vskip 1cm
\large
Ira M. Gessel\footnote{Partially supported by NSF grant DMS-0200596.}
and Guoce Xin \\
Department of Mathematics\\
Brandeis University\\
Waltham, MA 02454-9110 \\
USA \\
\href{mailto:gessel@brandeis.edu}{\tt gessel@brandeis.edu} \\
\href{mailto:guoce.xin@gmail.com}{\tt guoce.xin@gmail.com} \\
\end{center}
\vskip .2 in
\begin{abstract}
It is well known that the numbers
$(2m)!\,(2n)!/m!\,n!\,(m+n)!$ are integers,
but in general there is no known combinatorial interpretation for them.
When $m=0$ these numbers are the middle binomial coefficients
$\binom{2n}{n}$, and when $m=1$ they are twice the Catalan numbers. In this paper, we give combinatorial
interpretations for these numbers when $m=2$ or $3$.
\end{abstract}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{thm}{Theorem}[section]
%\newtheorem{pro}[thm]{Proposition}
%\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\renewcommand{\thethm}{\thesection.\arabic{thm}}
\makeatletter\@addtoreset{equation}{section}\makeatother
%\def\qed{$\quad$\rule{0mm}{3mm}\hfill \rule{2mm}{3mm}}
\newcommand{\E}{{\mathbf E}}
\newcommand{\D}{{\mathbf D}}
\newcommand{\C}[1]{1-C^{#1}}
\newcommand{\CC}[1]{(1-C^{#1})}
\newcommand{\B}{{\mathbf B}}
\newcommand{\G}[2]{G_{#1}^{(#2)}}
\renewcommand{\H}[2]{H_{#1}^{(#2)}}
\newcommand\sumz[1]{\sum_{#1=0}^\infty}
\newcommand\superscript{$^1$}
\def\comment#1{\textbf{Comment: }\emph{#1}}
\section{Introduction}
The Catalan numbers
$$C_n=\frac{1}{n+1}\binom{2n}{n} =\frac{(2n)!}{n!\,(n+1)!}$$
are well-known integers that arise in many combinatorial problems.
Stanley \cite[pp. 219--229]{EC2} gives
$66$ combinatorial interpretations of these numbers.
In 1874 Catalan \cite{catalan} observed that the numbers
\begin{equation}
\frac{(2m)!\,(2n)!}{m!\,n!\,(m+n)!}\label{e-1}
\end{equation}
are integers, and their
number-theoretic
properties were studied by several authors (see Dickson \cite[pp.
265--266]{dickson}). For $m=0$,
(\ref{e-1}) is the middle binomial coefficient
$\binom{2n}n$, and for $m=1$ it is $2C_n$.
Except for $m=n=0$, these integers are even, and it is convenient for our
purposes to
divide them by 2, so we consider the numbers
\begin{equation*}
T(m,n)=\frac{1}{2} \; \frac{(2m)!\,(2n)!}{m!\,n!\,(m+n)!}.
\end{equation*}
Some properties of these numbers are given in \cite{gessel}, where they are called ``super Catalan
numbers". An intriguing problem is to find a combinatorial interpretation to the super Catalan
numbers. The following identity
\cite[Equation (32)]{gessel}, together with the symmetry property $T(m,n)=T(n,m)$ and the initial value $T(0,0)=1$,
shows that
$T(m,n)$ is a positive integer for all $m$ and $n$.
\begin{align}
\sum_{n} 2^{p-2n} {p\choose 2n} T(m,n) =T(m,m+p), \quad p\geq 0. \label{e-8}
\end{align}
Formula (\ref{e-8}) allows us to construct recursively a set of cardinality
$T(m,n)$ but it is difficult to give a natural description of this set.
Shapiro \cite{shapiro} gave a combinatorial interpretation to
(\ref{e-8}) in the case $m=1$,
which is the Catalan number identity
\[\sum_{n} 2^{p-2n}\binom p{2n} C_n=C_{p+1}.\]
A similar interpretation works for the case $m=0$ of (\ref{e-8})
(when multiplied by 2), which is the
identity
\[\sum_{n} 2^{p-2n}\binom p{2n}\binom{2n}{n}=\binom{2p}{p}.\]
Another intriguing formula for $T(m,n)$, which does not appear in
\cite{gessel}, is
\begin{equation}
\label{e-mo}
1+\sum_{m,n=1}^\infty C_m C_n x^m y^n=\biggl(1-\sum_{m,n=1}^\infty T(m,n)x^my^n\biggr)^{-1},
\end{equation}
which can easily be proved using the the generating function for $2T(m,n)$ given in formulas (35) and (37) of \cite{gessel}.
Although (\ref{e-mo}) suggests a combinatorial interpretation
for $T(m,n)$ based on a decomposition of pairs of
objects counted by Catalan numbers, we have not found such an interpretation.
In this paper, we give a combinatorial interpretation for
$T(2,n)=6\,(2n)!\,/n!\,(n+2)!$ for $n\ge1$ and for $T(3,n)= 60\,(2n)!\,/n!\,(n+3)!$ for $n\ge2$.
The first few values of $T(m,n)$ for $m=2$ and $m=3$ are as follows:
\[
\offinterlineskip\vbox
{\halign{\ \hfil\strut$#$\hfil\ \vrule&&\hfil\ $#$\ \cr
m\backslash n&0&1&2&3&4&5&6&7&8&9&10\cr
\noalign{\hrule}
2&3&2&3&6&14&36&99&286&858&2652&8398\cr
3&10&5&6&10&20&45&110&286&780&2210&6460\cr
}}
\]
We show that $T(2,n)$ counts pairs of Dyck paths of total length $2n$ with heights differing by at most 1.
We give two proofs of this result, one combinatorial and one using generating functions.
The combinatorial proof is based on
the easily checked formula
\begin{equation}\label{e-2}
T(2,n)=4C_n-C_{n+1}
\end{equation}
which we interpret by inclusion-exclusion.
Our interpretation for $T(3,n)$ is more complicated, and involves
triples of Dyck paths with height restrictions. Although we have
the formula $T(3,n) = 16C_n -8C_{n+1}+C_{n+2}$ analogous to
(\ref{e-2}), we have not found a combinatorial interpretation to
this formula, and our proof uses generating functions.
Interpretations of the number $T(2,n)$ in terms of trees, related to each other, but not, apparently, to our
interpretation, have been found by Schaeffer \cite{gilles}, and by Pippenger and Schleich \cite[pp.~34]{nicholas}. A combinatorial interpretation of
(\ref{e-8}) for $m=2$,
using Pippenger and Schleich's interpretation of $T(2,n)$,
has been given by Callan \cite{callan}.
\section{The main theorem}
\label{s-main}
All paths in this paper have steps $(1,1)$ and $(1,-1)$, which we call \emph{up steps} and \emph{down steps}.
A step from a point
$u$ to a point $v$ is denoted by $u\to v$.
The \emph{level}
of a point in a path is defined to be its
$y$-coordinate.
A \emph{Dyck path} of \emph{semilength} $n$
(or of length $2n$)
is a path that starts at $(0,0)$, ends at $(2n,0)$,
and never goes below level $0$.
It is well-known that the number of Dyck paths of semilength $n$ equals the Catalan
number $C_n$.
The
\emph{height} of a path $P$,
denoted by $h(P)$, is the highest level it reaches.
Every nonempty Dyck path $R$ can be factored uniquely as $UPDQ$,
where $U$ is an up step, $D$ is a down step, and $P$ and $Q$ are
Dyck paths. Thus the map $R\mapsto (P,Q)$ is a bijection from
nonempty Dyck paths to pairs of Dyck paths. Let $\B_n$ be the set
of pairs of Dyck paths $(P,Q)$ of total semilength $n$. This
bijection gives $ | \B_n | = C_{n+1}$, so by (\ref{e-2}), we have
$T(2,n)= 4C_n - | \B_n | $.
%
%Let $c(x)$ be the generating function for the Catalan numbers, so that
%\[c(x)=\sum_{n=0}^{\infty} \frac{1}{n+1}{2n\choose n} x^n
%=\frac{1-\sqrt{1-4x}}{2x}.\]
%Then $c(x)$ satisfies the functional equation $c(x)=1+xc(x)^2$. {}From
%equation \eqref{e-2}, the generating function for
%$T(2,n)$ is
%\begin{equation}
%\label{e-T2}
%\sum_{n=0}^\infty T(2,n) x^n
% =\sum_{n=0}^\infty (4C_n-C_{n+1})x^n
% = 4c(x)-\frac{c(x)-1}{x} = 4c(x)-c(x)^2.
%\end{equation}
%Now if we let $\B_n$ be the set of pairs of Dyck paths $(P,Q)$ of total semilength
%$n$, then $ | \B_n | $ has generating function $c(x)^2$, and we have $T(2,n)= 4C_n
%- | \B_n | $.
Our interpretation for $T(2,n)$ is a consequence of the following
Lemma \ref{l-main}. We give two proofs of this lemma, one
combinatorial and the other algebraic. The algebraic proof will be
given in the next section.
\begin{lem}\label{l-main}
For $n\ge 1$, $C_n$ equals the number of pairs of Dyck paths
$(P,Q)$ of total
semilength $n$, with $P$ nonempty and $h(P)\leq h(Q)+1$.
\end{lem}
\begin{proof}
Let $\D_n$ be the set of Dyck paths of semilength $n$, and let
$\E_n$ be the set of pairs of Dyck paths $(P,Q)$ of total
semilength $n$, with $P$ nonempty and $h(P)\leq h(Q)+1$. We first
establish a bijection from $\E_n$ to $\D_n$.
For a given pair $(P,Q)$ in $\E_n$, since $P$ is nonempty, the last step of
$P$ must be a down step, say, $u\to v$. By replacing $u\to v$ in $P$ with an
up step $u\to v'$, we get a path $F_1$. Now raising $Q$ by two levels, we get
a path $F_2$. Thus $F:=F_1F_2$ is a path that ends at level $2$
and never goes below level $0$. The point $v'$ belongs to both
$F_1$ and $F_2$, but we treat it as a point only in $F_2$, even if $F_2$
is the empty path.
The condition that
$h(P)\le h(Q)+1$ yields
$h(F_1)0$ with $h(P)\leq h(Q)+1$ is $2C_m$.
\begin{thm}
\label{t-firstsum}
\[\sum_{n=0}^\infty(G_n-G_{n-1})G_{n+1}=1+2C.\]
\end{thm}
\begin{proof}
Let \[\Psi_k=\sum_{n=k}^\infty \frac{C^n}{1-C^{n}}.\]
Thus if $j2$ have combinatorial interpretations similar to
that of Theorem \ref{t-main}. Using the partial fraction procedure described in the proof of Lemma \ref{l-general}, it is straightforward (with the help of a computer algebra system) to evaluate as rational functions of $C$ the sums
that count $k$-tuples of paths with height restrictions when
Theorem \ref{t-general} applies. By rationalizing the denominator, we can express any rational function of $C$ in the form
\begin{equation}
\label{e-sqrt}
A(x) + B(x)\sqrt{1-4x},
\end{equation}
where $A(x)$ and $B(x)$ are rational functions. Such a formula can be related to the super Catalan numbers with the help of the following formula.
\begin{lem}
\label{l-gf}
\begin{align}
(1-4x)^{m-1/2}&=
\sum_{k=0}^{m-1} (-4)^k \binom{m-1/2}k x^k
+ 2(-1)^m\sum_{n=0}^\infty T(m,n) x^{m+n}.
\end{align}
\end{lem}
\begin{proof}
It is easily verified that $T(m,n) = \frac12 (-1)^n 4^{m+n}\binom{m-1/2}{m+n}$. Thus
\begin{align*}
(1-4x)^{m-1/2}&=\sum_{k=0}^{m-1}(-4)^k\binom{m-1/2}k x^k
+\sum_{k=m}^{\infty}(-4)^k\binom{m-1/2}k x^k\\
&= \sum_{k=0}^{m-1}(-4)^k\binom{m-1/2}k x^k
+ \sum_{n=0}^\infty (-4)^{m+n}\binom{m-1/2}{m+n} x^{m+n}\\
&= \sum_{k=0}^{m-1}(-4)^k\binom{m-1/2}k x^k
+2(-1)^m\sum_{n=0}^\infty T(m,n) x^{m+n}.
\end{align*}
\end{proof}
Thus if in (\ref{e-sqrt}) we expand the numerator of $B_1(x)$ in powers
of $1-4x$, we will get an expression involving rational functions and
generating functions for super Catalan numbers.
For example, the sum
\begin{equation}
\label{e-3paths}
\sum_{n=0}^\infty (G_n - G_{n-1})(G_{n+2}-G_{n+1})(G_{n+4}-G_{n+3})
\end{equation}
counts triples of paths whose heights are $n$, $n+2$, and $n+4$ for some $n$. It can easily be expressed in terms of sums to which Theorem
\ref{t-general} applies, and we find that
(\ref{e-3paths}) is equal to
\begin{multline}
\label{e-ugly3}
\quad
\frac{C^6(1+C^2)(1+2C^2+C^4-C^5+C^6-2C^7+C^8)}
{(1+C^2)^2(1+C+C^2)(1+C+C^2+C^3+C^4)^2}\\
= \frac{(1-3x)
(1-13x+63{x}^{2}-140{x}^{3}+142{x}^{4}-56{x}^{5}+6{x}^{6})}
{2(1-x)^2(1-2x)^2(1-3x+x^2)^2}\\
-\frac{(1-4x)^{5/2}}{(1-x)(1-2x)(1-3x+x^2)}.\quad\qquad\qquad
\end{multline}
The rational functions that appear in (\ref{e-ugly3}) can be simplified
by partial fraction expansion, and we can write down an explicit
formula involving $T(3,n)$ for the coefficients of (\ref{e-ugly3}).
What we obtain is far from a combinatorial interpretation of $T(3,n)$,
but the computation suggests that perhaps some modification of this set
of paths might lead to the desired interpretation. We note also that
sums with $m$ paths instead of three empirically give similar
expressions with $(1-4x)^{m-1/2}$ instead of $(1-4x)^{5/2}$.
Our strategy for finding a combinatorial interpretation for $T(3,n)$ is
to consider more general paths that give us counting formulas that
generalize (\ref{e-G}), in the hope that this additional generality may
lead us to a combinatorial interpretation for $T(3,n)$. In this we are
partially successful: we do find in Theorem \ref{t-T3} a set of triples
of paths, not too different from the set counted by (\ref{e-3paths})
whose generating function is $\sum_{n=0}^\infty T(3,n+1) x^n$ plus a
rational function, and moreover we can interpret the coefficients of
the rational function in terms of paths. Although the set of paths is
not very natural, the result does suggest that there is some hope for
this approach to give a nice combinatorial interpretation of $T(3,n)$
and perhaps even for $T(m,n)$.
For our interpretation of $T(3,n)$, we need to consider paths that end at levels greater than 0.
Let us define a \emph{ballot path} to be a path that starts at level 0
and never goes below level 0.
In the previous section all our
paths had an even number of steps, so it was natural to assign a path with $n$ steps the weight $x^{n/2}$. We shall
continue to weight paths in this way, even though some of our paths now have odd lengths.
Let $G_k^{(j)}$ be the generating function for ballot paths of height at most $k$ that end at level $j$.
\begin{lem}
\label{t-Gij}
For $0\le j\le k+1$ we have
\begin{equation}
\label{e-Gj}
G_k^{(j)}=C^{j/2}(1+C)\frac{\C{k-j+1}}{1-C^{k+2}}
\end{equation}
\end{lem}
\begin{proof}
The case $j=0$ is Lemma \ref{l-G}. Now let $W$ be a ballot
path counted by $G_k^{(j)}$, where $j>0$, so that $W$ is of height at most $k$ and $W$
ends at level $j$. Then
$W$ can be factored uniquely as $W_1UW_2$, where $W_1$ is a path of height at most $k$ that
ends at level 0 and $W_2$ is a path from level 1 to level $j$ that never goes above level
$k$ nor below level 1.
Using $\sqrt x=\sqrt{C/(1+C)^2}=\sqrt C/(1+C)$, we obtain
\[G_k^{(j)}=G_k\sqrt x G_{k-1}^{(j-1)}=(1+C)\frac{\C {k+1}}{\C{k+2}}
\cdot \frac{\sqrt C}{1+C}\cdot G_{k-1}^{(j-1)}=\sqrt C\frac{\C
{k+1}}{\C{k+2}}G_{k-1}^{(j-1)},\] and (\ref{e-Gj}) follows by
induction on $j$.
\end{proof}
We note an alternative formula that avoids half-integer powers of $C$,
\[G_k^{(j)}=x^{j/2}(1+C)^{j+1}\frac{\C{k-j+1}}{1-C^{k+2}},\]
which follow easily from (\ref{e-Gj})
% \eqref{e-Gij},
and the formula $\sqrt x=\sqrt C/(1+C)$.
There is a similar formula for the generating function $G_k^{(i,j)}$
for paths of height at most $k$ that start at level $i$, end at level $j$, and never go below level 0:
for $0\le i\le j\le k+1$ we have
\begin{equation}
\label{e-Gij}
G_k^{(i,j)}=
C^{(j-i)/2}(1+C)\frac{\CC{i+1}(1-C^{k-j+1})}{\CC{}\CC{k+2}},
\end{equation}
with $G_k^{(i,j)}=G_k^{(j,i)}$ for $i>j$.
Although we will not use (\ref{e-Gij}) in this paper, it may be helpful
in further applications of this method. We have not found (\ref{e-Gj})
or (\ref{e-Gij}) in the literature, although they may be derived from
the known rational generating function for $G_k^{(i,j)}$ described
below.
We note two variants of (\ref{e-Gij}), also valid for $0\le i\le j\le k+1$:
\begin{align*}
G_k^{(i,j)}&=x^{(j-i)/2}(1+C)^{j-i+1}\frac{\CC{i+1}(1-C^{k-j+1})}{\CC{}\CC{k+2}},\\
&=x^{-1/2}C^{(j-i+1)/2}\frac{\CC{i+1}\CC{k-j+1}}{\CC{}\CC{k+2}}.
\end{align*}
It is well known that $G_k^{(i,j)}$ is $x^{(j-i)/2}$ times a
rational function of $x$, and it is useful to have an explicit formula
for it as a quotient of polynomials. (See Sato and Cong
\cite{sato-cong} and Krattenthaler \cite{kratt}.) Let us define
polynomials $p_n=p_n(x)$
by
\[p_n(x)=\sum_{0\le k\le n/2}(-1)^k{n-k\choose k}x^k.\]
%It follows easily that
%\[\sum_{n=0}^\infty p_n z^n={1\over 1-z+xz^2},\]
%and a partial fraction expansion gives
%\begin{equation}
%\label{e-p}
%p_{n}
% ={1\over\sqrt{1-4x}}\left[\left(1+\sqrt{1-4x}\over 2\right)^{n+1}
% -\left(1-\sqrt{1-4x}\over 2\right)^{n+1}\right].
%\end{equation}
The first few values are
\begin{align*}
p_0&=1\\
p_1&=1\\
p_2&=1-x\\
p_3&=1-2x\\
p_4&=1-3x+x^2\\
p_5&=1-4x+3x^2\\
p_6&=1-5x+6x^2-x^3\\
\end{align*}
These polynomials can be expressed in terms of the
Chebyshev polynomials of the second kind $U_n(x)$ by
%\[\sum_{n=0}^\infty U_n(x) z^n={1\over 1-2xt+t^2},\]
%so
\[p_n(x)=x^{n/2}U_n\left(1\over 2\sqrt x\right).\]
%It follows from (\ref{e-p}) that
It is not difficult to show that
\[p_n=\frac{\C{n+1}}{(1-C)(1+C)^n},\]
and thus we obtain
\[G_k^{(i,j)}=x^{(j-i)/2}\frac{p_i p_{k-j} }{p_{k+1}},\]
for $0\le i\le j\le k$, and in particular,
$G_k^{(j)}=x^{j/2} p_{k-j}/p_{k+1}$ and $G_k=p_k/p_{k+1}.$
We can now describe our combinatorial interpretation of $T(3,n)$: $T(3,n)$ counts triples of ballot paths whose
heights are $k$, $k-2$, and $k-4$ for some $k$, ending at levels 4, 3, and 2, together with some additional paths
of height at most 5. (Note that if a path of height $k-4$ ends at level 2, then $k$ must be at least 6.) More
precisely, let
$\H kj$ be the generating function for ballot paths of height
$k$ that end at level
$j$, so that $\H kj = \G kj - \G{k-1}j$.
Then we have:
\begin{thm}
\label{t-T3}
\begin{equation}
\label{e-T3}
1+\sum_{n=0}^\infty T(3,n+1) x^n = \sqrt x\sum_{k=6}^\infty \H k4 \H{k-2}3 \H{k-4}2
+2G_1+2G_2+G_3+G_5.
\end{equation}
\end{thm}
\begin{proof} With the help of Lemma \ref{l-gf} we find that
\begin{equation}
\label{e-5/2}
-\frac{(1-4x)^{5/2}}{2x^4} - \frac{10}x +\frac{15}{x^2}-\frac{5}{x^3}+\frac1{2x^4}
=\sum_{n=0}^\infty T(3,n+1)x^n.
\end{equation}
Using the method described in Lemma \ref{l-general} and Theorem \ref{t-general}, we find, with the
help of Maple, that the sum
\[ \sqrt x\sum_{k=6}^\infty \H k4 \H{k-2}3 \H{k-4}2\]
is equal to
\[-\frac{(1-4x)^{5/2}}{2x^4} - \frac{10}x +\frac{15}{x^2}-\frac{5}{x^3}+\frac1{2x^4} +1 -\frac2{1-x}
-2\frac{1-x}{1-2x} -\frac{1-2x}{1-3x+x^2}-\frac{1-4x+3x^2}{1-5x+6x^2-x^3}.
\]
Then (\ref{e-T3}) follows from (\ref{e-5/2}), the formula $G_k=p_k/p_{k+1}$, and the formulas for $p_k$, $k=1,\dots,
6.$
\end{proof}
\begin{thebibliography}{9}
\bibitem{de-Bruijn}
N. G. de Bruijn, D. E. Knuth, and S. O. Rice, ``The average height
of planted plane trees", in \emph{Graph Theory and Computing},
R. C. Read, ed.,
Academic Press, New York-London, 1972, pp.\ 15--22.
\bibitem{callan}
D. Callan, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Callan/callan301.html}
{A combinatorial interpretation for a super-Catalan recurrence},
{\it J. Integer Seq.} {\bf 8} (2005),
no. 1, Article 05.1.8, 7 pp. (electronic).
\bibitem{catalan}
E. Catalan, Question 1135,
\emph{Nouvelles Annales de Math\'{e}matiques}
(2) {\bf 13} (1874), 207.
\bibitem{dickson}
L. E. Dickson,
\emph{History of the Theory of Numbers}, New York: Chelsea. Vol. 1,
1966. Originally published in 1919 by the Carnegie Institute of Washington.
%This is irrelevant
%\bibitem{Flajolet}
%P. Flajolet, Z. Gao, A. Odlyzko, and B. Richmond, ``The
%distribution of heights of binary trees and other simple trees",
%\emph{Combin. Probab. Comput.} 2 (1993), 145--156.
\bibitem{gessel}
I. Gessel, Super ballot numbers,
\emph{J. Symb. Comput.} {\bf 14} (1992), 179--194.
\bibitem{kratt}
C. Krattenthaler, Permutations with restricted patterns and Dyck paths,
\emph{Adv. Appl. Math.} {\bf 27} (2001), 510--530.
\bibitem{nicholas}
N. Pippenger and K. Schleich,
\href{http://www.arxiv.org/abs/gr-qc/0306049}{Topological characteristics of
random surfaces
generated by cubic interactions}, {\tt arXiv:physics.gr-qc/0306049}.
\bibitem{sato-cong}
M. Sato and T. T. Cong,
The number of minimal lattice paths restricted by two parallel lines,
\emph{Disc. Math.} {\bf 43} (1983), 249--261.
\bibitem{gilles}
G. Schaeffer, \href{http://www.loria.fr/~schaeffe/Pub/Conjugacy/superCat.ps}{A
combinatorial interpretation of super-Catalan numbers of order two},\\
{\tt
http://www.loria.fr/\hspace{-1pt}\lower3pt\hbox{\char`\~}schaeffe/Pub/Conjugacy/superCat.ps}
\hspace{-2pt}, (2001).
\bibitem{shapiro}
L. W. Shapiro, A short proof of an identity of Touchard's concerning
Catalan numbers, \emph{J. Combin. Theory Ser. A} {\bf 20} (1976),
375--376.
\bibitem{EC2}
R. P. Stanley, \emph{Enumerative Combinatorics},
Vol.\ 2, Cambridge University Press, 1999.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A10; Secondary 05A15.
\noindent \emph{Keywords: Dyck paths, super Catalan numbers}
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A007054} and \seqnum{A007272}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received March 5 2005;
revised version received March 16 2005.
Published in {\it Journal of Integer Sequences}, April 27 2005.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in
\end{document}