\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#9 \\
(due 10/18/01)
\end{center}
\medskip
\begin{enumerate}
\item
For various small values of $n$ (1 through 5, at least),
determine the average number of times
that a $2n$-step Dyck path
returns to the horizontal axis
(counting $(2n,0)$ as a return but not $(0,0)$),
and conjecture a general formula.
Compute at least one more value
to confirm (or disprove) your conjecture.
(I strongly encourage you to do this problem
symbolically, if possible,
using a system like Maple or Mathematica
to generate and study a list
whose elements are representations
of the Dyck paths.
Take advantage of the recursive construction of Dyck paths
discussed in class,
in combination with the list-manipulation operations
that are available to you in these computer algebra systems.)
\item
Let $T_n$ be the number of domino tilings
of a 3-by-$2n$ cylinder,
obtained by gluing together the left and right sides (of length 3)
of a 3-by-$2n$ rectangle.
\begin{itemize}
\item[(a)]
Find a generating function
for the sequence $T_1$,$T_2$,$T_3$,... .
\item[(b)]
Since the sequence satisfies a linear recurrence,
there is a natural way to run the recurrence backward,
obtaining values for $T_0$, $T_{-1}$, $T_{-2}$, etc.
Compute $T_n$ for all $n$ between $-10$ and $+10$.
\item[(c)]
Formulate a conjecture based on your data.
\item[(d)]
Prove your conjecture.
\end{itemize}
\end{enumerate}
\end{document}
