\documentclass[12pt]{6042}

\usepackage{eepic}

%\documentstyle[12pt,twoside,amsfonts,amstex,psfig]{article}

%\raggedbottom

% \input{macros-course}

\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{teamprobs#1}{Problem for Recitation #1 (#2/98)}{#3}
}

\newcommand{\numb}[1]{\#\text{#1}}

\begin{document}

\recn{9}{11/6}{November 6, 1998}

\begin{problems}

\problem

We consider an ingenious approach to counting well-matched
parenthesis strings.

For example, \texttt{(()((())()))} is well-matched.  On the other hand, no
string that begins with a right parenthesis or ends with a left
parenthesis can be well-matched; neither can any proper prefix of a
well-matched string be well-matched.

We want to compute the number, $S_n$, of such well-matched parenthesis
strings of length $2n$.  It's easy to check that $S_1=1$, $S_2=1$,
$S_3=2$.  With a little case analysis, the only well-matched strings of 8
parentheses are
\[\texttt{(()(())),\ (()()()),\ ((())()),\ (((()))),\ ((()()))},\]
so $S_4=5$.

The team problem develops an ingenious combinatorial approach to arrive at
a simple formula for $S_n$.
Our approach will involve considering \emph{paths}
in the plane from a point $(x_1,y_1)$ to $(x_2,y_2)$ for $x_i,y_i \in
\ints$, where each step in the path is at a $\pm 45$ degree angle,
increasing the x-coordinate by 1 and the y-coordinate by $\pm 1$.  For
example, a path might start at $(1,1)$ and make seven steps to the
successive points $(2,0)$, $(3,-1)$, $(4,0)$, $(5,1)$, $(6,2)$,
$(7,1)$, $(8,0)$ as  in Figure~\ref{fig:path}.

\bparts

\ppart
Explain why the number of well-matched parenthesized strings of
length $2n$ is the same as the number of paths from $(0,0)$ to $(2n,0)$
which only touch the x-axis at their endpoints.  (That is, if $0<i<2n$ and
$(i,j)$ is a point on the path, then $j>0$.)

\ppart
How many paths are there from $(x_1,y_1)$ to $(x_2,y_2)$?  (Express the
answer as a binomial coefficient.)

\ppart For $y_1,y_2 > 0$, show that the number of paths from $(x_1,y_1)$
to $(x_2,y_2)$ which touch or cross the x-axis is equal to the number
of paths from $(x_1,-y_1)$ to $(x_2,y_2)$.
See Figure~\ref{fig:reflect}.

\ppart Conclude that the number of well-matched strings of $2n$ parentheses
equals the $n-1$st Catalan number
\[\frac{1}{n} \binom{2n-2}{n-1}.\]

\eparts
\end{problems}
\begin{figure}
\begin{center}
\begin{picture}(345,195)(-45,-45)

\put(0,-45){\line(0,1){195}}
\put(-45,0){\line(1,0){345}}

\put(-30,-2.5){\line(0,1){5}}
\put(30,-2.5){\line(0,1){5}}
\put(60,-2.5){\line(0,1){5}}
\put(90,-2.5){\line(0,1){5}}
\put(120,-2.5){\line(0,1){5}}
\put(150,-2.5){\line(0,1){5}}
\put(180,-2.5){\line(0,1){5}}
\put(210,-2.5){\line(0,1){5}}
\put(240,-2.5){\line(0,1){5}}
\put(270,-2.5){\line(0,1){5}}

\put(-2.5,-30){\line(1,0){5}}
\put(-2.5,30){\line(1,0){5}}
\put(-2.5,60){\line(1,0){5}}
\put(-2.5,90){\line(1,0){5}}
\put(-2.5,120){\line(1,0){5}}

\put(30,30){\circle*{3}}
\put(32,32){\makebox(0,0)[bl]{$(x_1, y_1)$}}

\path(30,30)(60,0)(90,-30)(120,0)(150,30)(180,60)(210,30)(240,0)

\put(60,0){\circle*{3}}
\put(90,-30){\circle*{3}}
\put(120,0){\circle*{3}}
\put(150,30){\circle*{3}}
\put(180,60){\circle*{3}}
\put(210,30){\circle*{3}}

\put(240,0){\circle*{3}}
\put(242,2){\makebox(0,0)[bl]{$(x_2, y_2)$}}

\end{picture}
\end{center}

\caption{\em A path from $(1,1)$ to $(8,0)$.}

\label{fig:path}

\end{figure}

\begin{figure}

\begin{center}
\begin{picture}(345,205)(-45,-55)

\put(0,-45){\line(0,1){195}}
\put(-45,0){\line(1,0){345}}

\put(-30,-2.5){\line(0,1){5}}
\put(30,-2.5){\line(0,1){5}}
\put(60,-2.5){\line(0,1){5}}
\put(90,-2.5){\line(0,1){5}}
\put(120,-2.5){\line(0,1){5}}
\put(150,-2.5){\line(0,1){5}}
\put(180,-2.5){\line(0,1){5}}
\put(210,-2.5){\line(0,1){5}}
\put(240,-2.5){\line(0,1){5}}
\put(270,-2.5){\line(0,1){5}}

\put(-2.5,-30){\line(1,0){5}}
\put(-2.5,30){\line(1,0){5}}
\put(-2.5,60){\line(1,0){5}}
\put(-2.5,90){\line(1,0){5}}
\put(-2.5,120){\line(1,0){5}}

\put(30,30){\circle*{3}}
\put(32,32){\makebox(0,0)[bl]{$(x_1, y_1)$}}

\put(30,-30){\circle*{3}}
\put(32,-32){\makebox(0,0)[tl]{$(x_1, -y_1)$}}

\dottedline{2}(30,-30)(60,0)

\path(30,30)(60,0)(90,-30)(120,0)(150,30)(180,60)(210,30)(240,0)

\put(60,0){\circle*{3}}
\put(90,-30){\circle*{3}}
\put(120,0){\circle*{3}}
\put(150,30){\circle*{3}}
\put(180,60){\circle*{3}}
\put(210,30){\circle*{3}}

\put(240,0){\circle*{3}}
\put(242,2){\makebox(0,0)[bl]{$(x_2, y_2)$}}

\end{picture}
\end{center}

\caption{\em Reflection of the initial part of a path.}

\label{fig:reflect}

\end{figure}


\end{document}
