\documentstyle[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#7 \\
(due 10/11/01)
\end{center}
\medskip
\begin{enumerate}
\item
\begin{itemize}
\item[(a)]
How many different polygonal paths of length $n$ are there
that start at the point $(0,0)$
and then take $n$ steps of length 1,
such that each step is either rightward, leftward, or upward,
and such that no point gets visited more than once?
Give an explicit formula.
\item[(b)]
If one chooses at random
one of the paths of length $n$ described in part (a)
(so that each of the length-$n$ paths has an equal chance of being chosen),
what is the expected value of the $y$-coordinate of the last point on the path?
Find a constant $c$ so that
this expected value is asymptotic to $cn$.
\end{itemize}
\item
Look at the (infinite-dimensional) space of
self-reciprocal Laurent polynomials in $t$,
that is, Laurent polynomials in $t$
that are unaffected by the substitution
$t \rightarrow 1/t$.
The space has two natural bases: $x_j = t^j+1/t^j$ (with $j \geq 0$)
and $y_k = (t+1/t)^k$ (with $k \geq 0$).
\begin{itemize}
\item[(a)]
Give an explicit formula for the entries of the (triangular) matrix
that expresses the $y_k$ in terms of the $x_j$.
\item[(b)]
Look at the inverse of this matrix
(which expresses the $x_j$ in terms of the $y_k$).
Try to conjecture a formula for the entries,
or if you can't get that far,
look for patterns and
conjecture some interesting properties.
(E.g., in each row of the infinite matrix
(or each column, if you do it the other way)
there are only finitely many non-zero values.
What is their sum?
What is the sum of their absolute values?)
For full credit, you will need to conjecture
(though not necessarily prove)
a formula for all the entries.
\end{itemize}
\end{enumerate}
\end{document}