<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
A Weighted Interpretation for the \\
\vskip .11in
Super Catalan Numbers
}
\vskip 1cm
\large
Emily Allen and Irina Gheorghiciuc\\
Department of Mathematical Sciences\\
Carnegie Mellon University \\
Pittsburgh, PA 15213 \\
USA \\
\href{eaallen@andrew.cmu.edu}{\tt eaallen@andrew.cmu.edu} \\
\href{gheorghi@andrew.cmu.edu}{\tt gheorghi@andrew.cmu.edu} \\
\end{center}

\vskip .2 in

\def\S #1{\mathcal{S}_{#1}}

\begin{abstract}
The super Catalan numbers $T(m,n)=(2m)!(2n)!/2m!n!(m+n)!$ are integers that generalize the Catalan numbers. With the exception of a few values of $m$, no combinatorial interpretation is known for $T(m,n)$. We give a weighted interpretation for $T(m,n)$ and develop a technique that converts this weighted interpretation into a conventional combinatorial interpretation in the case $m=2$.
\end{abstract}


\section{Introduction}

As early as 1874 Eug\`ene Catalan observed that the numbers
\[ S(m,n) = \frac{{2m \choose m}{2n \choose n}}{{m + n \choose n}} = \frac{(2m)!(2n)!}{m!n!(m+n)!}\]
are integers. This can be proved algebraically by showing that, for every prime number $p$, the power of $p$ which divides $m!n!(m+n)!$ is at most the power of $p$ which divides $(2m)!(2n)!$. No combinatorial interpretation of $S(m,n)$ is yet known.

Interest in the subject in the modern era was reignited by Gessel \cite{SuperBallot}. He noted that, except for $S(0,0)$, the numbers $S(m,n)$ are even. Gessel refers to
\[T(m,n) = \frac{(2m)!(2n)!}{2(m!n!(m+n)!)}\]
as the super Catalan numbers. The super Catalan numbers defined by Gessel should not be confused with the little Schr\"oder numbers, which are sometimes also called super Catalan numbers.

\begin{table}[ht] 
\centering 
\vspace{10pt}    
\begin{tabular}{  c | c   c   c   c   c   c   c   c  }               
$m \backslash n$ &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 \\ 
\hline  
0 &amp; na &amp; 1 &amp; 3 &amp; 10 &amp; 35 &amp; 126 &amp; 462 &amp; 1716 \\              
1 &amp; 1 &amp; 1 &amp; 2 &amp; 5 &amp; 14 &amp; 42 &amp; 132 &amp; 429 \\   
2 &amp; 3 &amp; 2 &amp; 3 &amp; 6 &amp; 14 &amp; 36 &amp; 99 &amp; 286 \\ 
3 &amp; 10 &amp; 5 &amp; 6 &amp; 10 &amp; 20 &amp; 45 &amp; 110 &amp; 286\\ 
4 &amp; 35 &amp; 14 &amp; 14 &amp; 20 &amp; 35 &amp; 70 &amp; 154 &amp; 364 \\ 
5 &amp; 126 &amp; 42 &amp; 36 &amp; 45 &amp; 70 &amp; 126 &amp; 252 &amp; 546 \\  
6 &amp; 462 &amp; 132 &amp; 99 &amp; 110 &amp; 154 &amp; 252 &amp; 462 &amp; 924 \\        
7 &amp; 1716 &amp; 429 &amp; 286 &amp; 286 &amp; 364 &amp; 546 &amp; 924 &amp; 1716 \\       
\end{tabular} 
\caption{A table for $T(m,n)$.} 
\end{table} 

Clearly $T(0,n)= {2n-1 \choose n}$, whilst $T(1,n) = C_n$ giving the Catalan numbers, a well-known sequence  with over 66 combinatorial interpretations \cite{EC}.

An interpretation of $T(2,n)$ in terms of blossom trees has been found by Schaeffer \cite{Schaeffer}, and another in terms of cubic trees by Pippenger and Schleich \cite{P&amp;S}. An interpretation of $T(2,n)$ in terms of pairs of Dyck paths with restricted heights has been found by Gessel and Xin \cite{GesselXin}. They have also provided a description of $T(3,n)$. An interpretation of $T(m,m+s)$ for $0 \leq s \leq 3$ in terms of restricted lattice paths has been given by Chen and Wang \cite{CW}.

A weighted interpretation of $S(m,n)$ based on von Szily's identity has been given by Georgiadis, Munemasa and Tanaka \cite{GMT}. Their interpretation is in terms of lattice paths of length $2m+2n$ with a condition on the $y$-coordinate of the end-point of the $2m^{th}$ step.

In Section 2 we provide a weighted interpretation of $T(m,n)$ for $m,n \geq 1$ in terms of $2$-Motzkin paths of length $m+n-2$, or Dyck paths of length $2m+2n-2$. Since the lattice paths in \cite{GMT} are not Dyck paths, our interpretation is different from the one by Georgiadis, Munemasa and Tanaka. In Section 3 we are able to use our weighted interpretation to re-derive a result by Gessel and Xin \cite{GesselXin}, which we were then able to generalize for super Catalan polynomials \cite{PolyArt}.

\section{2-Motzkin paths}

A 2-Motzkin path of length $n$ starts at the origin, ends at the point $(n,0)$, never goes below the $x$-axis, and consists of unit steps that are diagonally \textit{up}, diagonally \textit{down}, \textit{straight level} and \textit{wavy level}. A Dyck path of length $2n$ is a 2-Motzkin path of length $2n$ with no \textit{level} steps.

Given a 2-Motzkin path, the level of a point is defined to be its $y$-coordinate. The height of a path is the maximum $y$-coordinate which the path attains. The height of a path $\pi$ will be denoted $h(\pi)$.

For a fixed $m\geq 0$, we call a 2-Motzkin path $\pi$ $m$-positive if the $m^{th}$ step begins on an even level, otherwise $\pi$ is $m$-negative. Let $P(m,n)$ be the number of $m$-positive 2-Motzkin paths of length $m+n-2$, and $N(m,n)$ be the number of $m$-negative 2-Motzkin paths of length $m+n-2$.

There is a well-known bijection between 2-Motzkin paths of length $n-1$ and Dyck paths of length $2n$ \cite{tag}. Given a 2-Motzkin path, read the steps from left to right and do the following replacements:
replace an \textit{up} step with two \textit{up} steps, a \textit{down} step with two \textit{down} steps, a \textit{straight} step with an \textit{up} step followed by a \textit{down} step, and
a \textit{wavy} step with a \textit{down} step followed by an \textit{up} step. The resulting path may touch level $-1$, thus, in addition, add an \textit{up} step to the beginning of the resulting path and a \textit{down} step to the end to obtain a Dyck path.

\begin{theorem}\label{mainTheorem}
 For $m,n \geq 1$, the super Catalan number $T(m,n)$ counts the number of $m$-positive 2-Motzkin paths of length $m+n-2$ minus the number of $m$-negative 2-Motzkin paths of length $m+n-2$. That is,
\[T(m,n) = P(m,n) - N(m,n).\]
\end{theorem}

\begin{proof}

The super Catalan numbers satisfy the following identity, attributed to Dan Rubenstein \cite{SuperBallot},
\begin{equation}
\label{rec}
 4T(m,n) = T(m+1,n) + T(m,n+1).
\end{equation}

Note that (\ref{rec}) can be viewed as a recurrence for $T(m,n)$ on $m$ if written as 
\[ T(m+1,n) = 4T(m,n)-T(m,n+1). \]

Given a 2-Motzkin path $\pi$ of length $m+n-2$, define the weight of $\pi$ to be $1$ if $\pi$ is $m$-positive and $-1$ if $\pi$ is $m$-negative.
	
Let $F(m,n)$ be the sum of the weights of all 2-Motzkin paths of length $m+n-2$, that is, $F(m,n) = P(m,n) - N(m,n)$. To prove $F(m,n) = T(m,n)$, we will check the initial condition 
\[F(1,n) = C_n\]
and the recurrence given by (\ref{rec}),
\[4F(m,n) = F(m+1,n) + F(m,n+1).\]

For $m=1$, the weight of any 2-Motzkin path of length $n$ is $1$ because the first step always starts at the (even) level $y=0$. Hence $F(1,n)=C_n$, giving the number of 2-Motzkin paths of length $n-1$. 

Next we consider the sum of the weights counted by $F(m,n+1) + F(m+1,n)$. If a 2-Motzkin path of length $m+n-1$ has an \textit{up} or \textit{down} step at step $m$, it will be counted once as a $m$-positive path and once as a $m$-negative path, and will not contribute to this sum.

Paths of length $m+n-1$ with a \textit{level} step at step $m$ will be counted twice. Let $\pi$ be such a 2-Motzkin path. By contracting the $m^{th}$ step in $\pi$, we obtain a 2-Motzkin path of length $m+n-2$; furthermore, every 2-Motzkin path of length $m+n-2$ can be obtained by contracting exactly two 2-Motzkin paths of length $m+n-1$, one with a \textit{wavy} step at step $m$ and one with a \textit{straight} step at step $m$. 

Thus the sum of the weights counted by $F(m,n+1) + F(m+1,n)$ is twice the sum of the weights of 2-Motzkin paths of length $m+n-1$ with \textit{level} steps at step $m$; which is four times the sum of the weights of 2-Motzkin paths of length $m+n-2$, that is, $4F(m,n)$.
\end{proof}

\begin{figure}[h]
\centering
 \includegraphics[scale=.4]{MotzkinPaths2.eps}
\caption{When $m=2$, there are ten $m$-positive 2-Motzkin paths and four $m$-negative 2-Motzkin paths of length 3. $T(2,3) = P(2,3) - N(2,3) = 6.$}
\end{figure}

This weighted interpretation can be used to prove combinatorially that $T(m,n)=T(n,m)$. Let $\pi$ be a path of length $m+n-2$ counted by $T(m,n)$. Consider the reverse of a path to be that path read from right to left. Since the $m^{th}$ step of $\pi$ and the $n^{th}$ step of the reverse of $\pi$ start at the same point, mapping a path to its reverse is a weight preserving involution between the 2-Motzkin paths counted by $T(m,n)$ and the 2-Motzkin paths counted by $T(n,m)$.

We can reformulate the result of Theorem \ref{mainTheorem} in terms of Dyck paths. In this case $P(m,n)$ is the number of Dyck paths of length $2m+2n - 2$ whose $2m-1^{st}$ step ends on level $1 \pmod 4$, and $N(m,n)$ is the number of Dyck paths of length $2m+2n-2$ whose $2m-1^{st}$ step ends on level $3 \pmod 4$. 

Similar to a Dyck path, a ballot path starts at the origin, uses a finite number of diagonally \textit{up} and diagonally \textit{down} steps, and does not go below the $x$-axis. A ballot path ends on or above the $x$-axis. Let $B(n,r)$ be the number of ballot paths that end at the point $(2n-1,2r-1)$. It is well known that $B(n,r) = \frac{r}{n}{2n \choose n+r}$. Then

\begin{equation}
T(m,n) = \sum_{r=1}^{\min \{ m,n \}} (-1)^{r-1}B(m,r)B(n,r)
\end{equation}
and
\begin{equation}\label{balloteq}
T(m,n) = \sum_{r=1}^{\min \{ m,n \}} (-1)^{r-1}\frac{r^2}{nm}{2m \choose m+r}{2n \choose n+r}.
\end{equation}

Equation (\ref{balloteq}) is a new identity for the super Catalan number $T(m,n)$. A $q$-analog of this identity is given in \cite{PolyArt}, and its algebraic proof appears in \cite{thesis}.

\section{Combinatorial techniques}

We define the total length of an ordered pair of Dyck paths $(\pi,\rho)$ to be the sum of the lengths of the paths $\pi$ and $\rho$. The height of the empty Dyck path is zero. In \cite{GesselXin} Gessel and Xin use an inclusion-exclusion argument to prove the following result.

\begin{theorem}[Gessel, Xin] For $n \geq 1$, the number $T(2,n)$ counts the ordered pairs of Dyck paths $(\pi,\rho)$ of total length $2n$ with $|h(\pi) - h(\rho)| \leq 1$. Here $\pi$ and $\rho$ are allowed to be the empty path.
\label{Gessel}
\end{theorem}

Our goal in this section is to derive a similar result using Theorem \ref{mainTheorem} and some direct Dyck paths subtraction techniques that will be easier to generalize for larger values of $m$. We already were able to generalize this result to super Catalan Polynomials in \cite{PolyArt}.

Let $\mathcal{D}_{n}$ denote the set of Dyck paths of length $2n$. For a path $\pi \in \mathcal{D}_n$, let $R$ be the rightmost highest point on $\pi$. We define the $X$-point of $\pi$ to be the last, from left to right, level one point on the portion of $\pi$ before and including $R$. In other words, if $h(\pi)&gt;1$, then the $X$-point is the last, from left to right, level one point before $R$. If $h(\pi)=1$, then the $X$-point and $R$ coincide. See Figure~\ref{Xdef}.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.5]{Xdef.eps}
\caption{The $X$-point of two Dyck paths.}
\label{Xdef}
\end{center}
\end{figure}

Let $h_{-}(\pi)$ denote the maximum level that the path $\pi$ reaches from its beginning until and including the $X$-point, and $h_{+}(\pi)$ denote the maximum level that the path $\pi$ reaches after and including the $X$-point. Obviously $h_-(\pi) \leq h_+(\pi) = h(\pi)$.

\begin{theorem} Let $n \geq 1$. The super Catalan number $T(2,n)$ counts Dyck paths $\pi$ of length $2n$ such that $h_{+}(\pi) \leq h_{-}(\pi)+2$, the path of height one counting twice. 
\label{T(2,n)}
\end{theorem}

\begin{proof} Let $\mathcal{A}_{n}$ denote the set of Dyck paths of length $2n$ that start with {\it up, down, up}, $\mathcal{B}_{n}$ denote the set of Dyck paths of length $2n$ that start with {\it up, up, down}, and $\mathcal{N}_{n}$ denote the set of Dyck paths of length $2n$ that start with {\it up, up, up}.

By Theorem \ref{mainTheorem}, $T(2,n)=P(2,n)-N(2,n)$, where $P(2,n)$ is the number of 2-Motzkin paths of length $n$ that start with a {\it level} step, and $N(2,n)$ is the number 2-Motzkin paths of length $n$ that start with an {\it up} step. The canonical bijection between 2-Motzkin paths and Dyck paths leads to the following interpretation: $$T(2,n)=|\mathcal{A}_{n+1}|+|\mathcal{B}_{n+1}|-|\mathcal{N}_{n+1}|.$$

Note that $\mathcal{A}_{n+1}$, $\mathcal{B}_{n+1}$ and $\mathcal{N}_{n+1}$ are subsets of $\mathcal{D}_{n+1}$. By contracting the second and third steps in the paths in $\mathcal{A}_{n+1}$ and $\mathcal{B}_{n+1}$ we get twice $\mathcal{D}_{n}$, so $|\mathcal{A}_{n+1}|=|\mathcal{B}_{n+1}|=C_n$. 

We consider all paths $\pi$ in $\mathcal{N}_{n+1}$ that do not attain level one between the third step of $\pi$ and the rightmost highest point $R$ on $\pi$. The set of all such paths will be denoted by $\mathcal{N}^*_{n+1}$. Let $\mathcal{N}^{**}_{n+1}=\mathcal{N}_{n+1}-\mathcal{N}^*_{n+1}$. Then 
\begin{equation}
\label{fin}
T(2,n)=2|\mathcal{D}_{n}|-|\mathcal{N}^*_{n+1}|-|\mathcal{N}^{**}_{n+1}|.
\end{equation}

First we establish an injection $f$ from $\mathcal{N}^*_{n+1} \subset \mathcal{D}_{n+1}$ to $\mathcal{D}_n$. For $\pi \in \mathcal{N}^*_{n+1}$, let $RQ$ be the {\it down} step that follows the rightmost highest point $R$ of $\pi$. We define $f(\pi)$ to be the path obtained by removing the second and third steps in $\pi$, both of which are {\it up} steps, and then substituting the {\it down} step $RQ$ by an {\it up} step. See Figure~\ref{Mn+1}. Since $\pi$ does not attain level one between its third step and $R$, $f(\pi)$ is a Dyck path of length $2n$. Note that $Q$ is the leftmost highest point on $f(\pi)$. Also, since at least two {\it up} steps precede $Q$ on $f(\pi)$, the height of $f(\pi)$ is at least two. Thus the Dyck path of height one and length $2n$ is not in the image of $f$.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.5]{Mn+1.eps}
\caption{$f$ removes the $2^{nd}$ and $3^{rd}$ steps, substitutes the {\it down} step $RQ$ by an {\it up} step.}
\label{Mn+1}
\end{center}
\end{figure}


We will show that $f$ is an injection and that the only path in $\mathcal{D}_n$ that is not in the image of $f$ is the Dyck path of height one. Let $\rho$ be in $\mathcal{D}_n$ of height $h(\rho)&gt;1$. Let $Q$ be the leftmost highest point on $\rho$ and $RQ$ be the {\it up} step that precedes $Q$. Insert two {\it up} steps after the first step of $\rho$, then substitute the {\it up} step $RQ$ by a {\it down} step, which makes $R$ the rightmost highest point of the resulting path $\pi$. The path $\pi$ is in $\mathcal{N}^*_{n+1}$ and $f(\pi)=\rho$.

It follows that $|\mathcal{D}_{n}|-|\mathcal{N}^*_{n+1}|$ counts only one path, the Dyck path of length $2n$ and height one.  

Next we establish an injection $g$ from $\mathcal{N}^{**}_{n+1} \subset \mathcal{D}_{n+1}$ to $\mathcal{D}_n$. A path $\pi$ in $\mathcal{N}^{**}_{n+1}$ attains level one between its third step and the rightmost highest point $R$ on $\pi$. Let $Y$ be the first point between the third step of $\pi$ and $R$ at which $\pi$ attains level one. The segment $XY$ that consists of two {\it down} steps precedes $Y$. We remove the second and third steps of $\pi$ and substitute the two {\it down} steps $XY$ by two {\it up} steps. See Figure~\ref{M1}. The resulting path is a ballot path of length $2n$ that ends at level two. From left to right, $X$ is the last level one point on this ballot path. The maximum level that this path reaches up to and including point $X$ is less than the maximum level it reaches after and including point $X$ by at least 4. 

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.5]{M1.eps}
\caption{First part of $g$ action is removing the $2^{nd}$ and $3^{rd}$ steps, substituting the two {\it down} steps $XY$ by two {\it up} steps.}
\label{M1}
\end{center}
\end{figure}

Let $L$ be the leftmost highest point of this ballot path and $ML$ be the {\it up} step that precedes $L$. Substitute the {\it up} step $ML$ by a {\it down} step. See Figure~\ref{M2}. The resulting path $g(\pi)$ is in $\mathcal{D}_n$ and $M$ is its rightmost highest point. Note that $X$ is the last level one point on $g(\pi)$ before its rightmost highest point $M$ and $h_{+}(g(\pi)) \geq h_{-}(g(\pi))+3$. 

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.5]{M2.eps}
\caption{Second part of $g$ action is substituting the {\it up} step $ML$ with a {\it down} steps.}
\label{M2}
\end{center}
\end{figure}

We will show that $g$ is an injection and that the only paths in $\mathcal{D}_n$ that are not in the image of $g$ are the Dyck paths $\sigma$ that satisfy $h_{+}(\sigma) \leq h_{-}(\sigma)+2$. Let $\rho$ be in $\mathcal{D}_n$ and $h_{+}(\rho) \geq h_{-}(\rho)+3$. Let $M$ be the rightmost highest point on $\rho$ and $ML$ be the {\it down} step that follows $M$. Let $X$ be the $X$-point of $\rho$, that is the last level one point, from left to right, before and including $M$. Substitute the {\it down} step $ML$ by an {\it up} step. The result is a ballot path of length $2n$ that ends at level two. Note that $L$ is the leftmost highest point on this ballot path. Let $R$ denote the rightmost highest point on this ballot path. From left to right, $X$ is the last level one point on this ballot path. The maximum level that this path reaches up to and including point $X$ is less than the maximum level it reaches after and including point $X$ by at least 4.  Since $X$ is the last level one point, it is followed by the segment $XY$ that consists of two {\it up} steps. Next we insert two {\it up} steps after the first step of this ballot path and then substitute the two {\it up} steps $XY$ by two {\it down} steps. The resulting path is a Dyck path of length $2n+2$, we denote it by $\pi$. Point $Y$ is the first level one point after the third step of $\pi$. Note that the maximum level that this Dyck path reaches after $Y$ is at least the maximum level that this Dyck path reaches up to and including $Y$, which means that the rightmost highest point $R$ is to the right of $Y$. If follows that $p \in \mathcal{N}^{**}_{n+1}$ and $g(\pi)=\rho$.

Thus $|\mathcal{D}_{n}|-|\mathcal{N}^{**}_{n+1}|$ counts Dyck paths $\pi$ of length $2n$ that satisfy $h_{+}(\pi) \leq h_{-}(\pi)+2$. Note that the Dyck path of length $2n$ and height one is among these paths.

Equation (\ref{fin}) can be re-written as \[
T(2,n)=(|\mathcal{D}_{n}|-|\mathcal{N}^*_{n+1}|)+(|\mathcal{D}_{n}|-|\mathcal{N}^{**}_{n+1}|).
\]

Hence $T(2,n)$ counts Dyck paths $\pi$ of length $2n$ such that $h_{+}(\pi) \leq h_{-}(\pi)+2$, the path of height one counting twice.
\end{proof}

We will now show a simple bijection from the objects described in Theorem~\ref{T(2,n)} to those in Theorem ~\ref{Gessel}.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.5]{gessel.eps}
\caption{From Dyck paths described in Theorem~\ref{T(2,n)} to pairs of Dyck path described in Theorem~\ref{Gessel}.}
\label{gessel}
\end{center}
\end{figure}

Let $\pi$ be a Dyck path of length $2n$ and height $h(\pi)&gt;1$, such that $h_{+}(\pi) \leq h_{-}(\pi)+2$. Let $R$ be the rightmost highest point of $\pi$. Note that $X$ is followed by an {\it up} step $XY$ and $R$ is followed by a {\it down} step $RL$. Substitute the {\it up} step $XY$ with a down step, substitute the {\it down} step $RL$ with an {\it up} step. See Figure~\ref{gessel}.
As a result, the portion of $\pi$ between $Y$ and $R$ will be lowered by two levels. Since $\pi$ does not attain level one between $Y$ and $R$, the resulting path is a Dyck path with point $Y$ on level zero. 

Note that $Y$ separates this Dyck path into a pair of Dyck paths $(\rho,\sigma)$. The height of $\rho$ is $h_{-}(\pi)$, the height of $\sigma$ is $h_{+}(\pi)-1$. Thus $|h(\rho) - h(\sigma)| \leq 1$. Since $L$ is the leftmost highest point on $\sigma$, this mapping is reversible. Theorem~\ref{T(2,n)} counts the Dyck path $\tau$ of height one twice. This corresponds to the pairs $(\tau, \epsilon)$ and $(\epsilon, \tau)$ in Theorem~\ref{Gessel}, where $\epsilon$ is the empty path. 


\section{Acknowledgments}

We are very thankful to Ira Gessel for his helpful comments. The
problem about the combinatorial interpretation of the super Catalan
Numbers was first mentioned to us by the late Herb Wilf, to whom we are
immensely grateful.

\begin{thebibliography}{99}

\bibitem{thesis}
E. Allen, {\it Combinatorial interpretations of generalizations of Catalan
numbers and ballot numbers}, Ph.D. thesis, Carnegie Mellon University, 2014.

\bibitem{PolyArt}
E. Allen and I. Gheorghiciuc, On super Catalan polynomials, preprint, 
\url{http://arxiv.org/abs/1403.5296}, August 31 2014.

\bibitem{CW}
X. Chen and J. Wang, The super Catalan numbers $S(m,m+s)$ for $s \leq
3$ and some integer factorial ratios, preprint, \\
\url{http://www.math.umn.edu/~reiner/REU/ChenWang2012.pdf}, 2012.

\bibitem{GMT}
E. Georgiadis, A. Munemasa, and H. Tanaka, A note on super Catalan numbers, {\it Interdiscip. Inform. Sci.} {\bf 18} (2012),  23--24.

\bibitem{SuperBallot}
I. Gessel, Super ballot numbers, {\it J. Symb. Comput.} {\bf 14} (1992), 179--194.  
   
\bibitem{GesselXin}
I. Gessel and  G. Xin, A combinatorial interpretation of the numbers
$6(2n)!/n!(n+2)!$, {\it J. Integer Seq.} {\bf 8} (2005)
\href{https://cs.uwaterloo.ca/journals/JIS/VOL8/Gessel/xin.html}{Article 05.2.3}.

\bibitem{tag}
M. Pierre-Delest and G. Viennot, Algebraic languages and polyominoes
enumeration, {\it Theoret. Comput. Sci.} {\bf 34} (1984), 196--206.

\bibitem{P&amp;S}
N. Pippenger and K. Schleich, Topological characteristics of random
triangulated surfaces, {\it Random Structures Algorithms} {\bf 28}
(2006), 247--288.

\bibitem{Schaeffer}
G. Schaeffer, A combinatorial interpretation of super-Catalan numbers
of order two, unpublished manuscript, 2003.

\bibitem{EC} R. Stanley, {\it Enumerative Combinatorics}, Vol.~2,
Cambridge University Press, 1998.

\end{thebibliography} 


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A19.

\noindent \emph{Keywords: } super Catalan number, Dyck path, 2-Motzkin path,
combinatorial interpretation, combinatorial identity.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A007054}, and
\seqnum{A007272}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 26 2014;
revised version received August 31 2014; September 11 2014.  
Published in {\it Journal of Integer Sequences}, November 5 2014.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>