%&latex
%will accept 10pt 11pt or 12 pt in following line
%\renewcommand{\baselinestretch}{1.3} sets the interline spacing at
%generous double-spacing
\documentclass[12pt]{article}
\marginparwidth 0pt
\oddsidemargin 0pt
\evensidemargin 0pt
\marginparsep 0pt
\topmargin 0pt
\textwidth 6.3in
\textheight 8.7in
\pagestyle{empty}
\renewcommand{\baselinestretch}{1.3}
%\renewcommand{\parindent}{0mm}
\parindent=0mm
\parskip = 3mm
%\setstretch{1.5}
\usepackage{amsmath}
\def\v{\vert}
\def\a{\ensuremath{\mathcal A}}
\def\b{\ensuremath{\mathcal B}}
\def\s{\ensuremath{\mathcal S}}
\begin{document}
\newtheorem{lemma}{Lemma}
\vspace*{-30mm}
\begin{center}
{\Large
Wong's Catalan Number Identity \\
}
\vspace{10mm}
DAVID CALLAN \\
Department of Statistics \\
University of Wisconsin-Madison \\
1210 W. Dayton St \\
Madison, WI \ 53706-1693 \\
{\bf callan@stat.wisc.edu} \\
\vspace{5mm}
December 2 2003
\end{center}
\vspace{5mm}
The identity \cite{wong}
\[
\sum_{j=0}^{\lfloor n/2 \rfloor}\left[
\frac{n+1-2j}{n+1}\binom{n+1}{j} \right]^{2} =
\frac{1}{n+1}\binom{2n}{n}
\]
has a simple interpretation in terms of lattice paths. The right hand
side is the Catalan number $C_{n}$, which
counts nonnegative lattice paths of $n$ upsteps and $n$ downsteps
(nonnegative means they don't dip
below the $x$-axis). The left hand side counts them
by where they meet the vertical line $x=n$.
The first $n$ steps form a nonnegative path of $n-j$
upsteps and $j$ downsteps for some $j \in \left[0,\lfloor n/2
\rfloor\right]$. The
number of such paths is $\binom{n}{j}$ [all paths] $-\,\binom{n}{j-1}$
[paths that touch $y=-1$] $=\frac{n+1-2j}{n+1}\binom{n+1}{j}$.
Here, the second count uses Andr\'{e}'s reflection principle:
given a path that touches $y=-1$, flip the initial portion of the
path up to the first point of contact with the line $y=-1$ across
this line to
get a bijection to \emph{all} paths from $(0,-2)$ to the same
endpoint, that is, to paths with the same total number $n$ of steps
but one fewer downstep.
Likewise the last $n$
steps, when reversed, form another such path. The identity follows.
Similarly, the identity
$\binom{2n}{n}=\sum_{j=0}^{n}\binom{n}{j}^{2}$ counts all paths of $n$
upsteps and $n$ downsteps by where they meet $x=n$.
\begin{thebibliography}{99}
\bibitem{wong} B. C. Wong, Emma T. Lehmer,
American Math Monthly, Volume 37, Issue 10 (Dec., 1930), 558.
\end{thebibliography}
\end{document}
The number of $j$-sequences of Dyck paths of total semilength $n$ is
\[
\frac{j}{2n+j}\binom{2n+j}{j}.
\]
Hence, the number of paths of $p$ upsteps and $q$ downsteps that never dip below
GL is
\[
\frac{p-q+1}{p+q+1} \binom{p+q+1}{q}.
\]