\documentclass[12pt]{article}
\pagestyle{empty}
\begin{document}
\large
\begin{center}
Math 491, Take-home Final \\
(due December 18, 11:00 a.m.)
\end{center}
\medskip
Read the instructions at the end of this exam, and then
do all of the following problems:
\begin{enumerate}
\item %1
A Motzkin path is a finite path that visits the successive points
$(0,m_0)$, $(1,m_1)$, $(2,m_2)$, $\dots$, and $(n,m_n)$,
where $m_0$ and $m_n$ are both 0, all the $m_i$'s are non-negative,
and $m_i-m_{i-1}$ is $-1$, $0$ or $1$ for all $1 \leq i \leq n$.
We call $n$ the length of the path. Define the weight of a Motzkin
path to be $w^k x^n$, where $k$ is the number of $i>0$ with $m_i=0$
and $n$ is length of the path. That is: A Motzkin path consists of
steps that go 1-over-and-1-down, 1-over, or 1-over-and-1-up,
starting and ending at height 0 and never going below height 0,
and the weight of a Motzkin path is $w^k x^n$, where $k$ is the
number of times the path returns to height 0 (counting the right
endpoint as a return but not the left endpoint) and $n$ is the
number of steps in the path.
Let $F(w,x)$ be the sum of the weights of all the Motzkin paths
of every length (including length 0), viewed as a formal power
series, so that
$$F(w,x) = 1 + wx + (w+w^2) x^2 + (w+2w^2+w^3) x^3 + \dots$$
\begin{itemize}
\item[(a)]
(10 points) Express $F(1,x)$ as an algebraic function of $x$.
\item[(b)]
(10 points) Express $F(w,x)$ as an algebraic function of $w$ and $x$.
\item[(c)]
(10 points) How many times on average does a Motzkin path of length 100
return to height 0? Give your answer to the nearest integer.
\end{itemize}
\item %2
(20 points) Use Lindstrom's lemma,
the interpretation of domino tilings as routings,
and a computer,
in order to count the domino tilings of an 8-by-8 square
from which two (non-opposite) corners have been removed.
\item %3
Let $R(q)$ be the formal power series given by the infinite sum
$$1 + \frac{q}{1-q} + \frac{q^4}{(1-q)(1-q^2)}
+ \frac{q^9}{(1-q)(1-q^2)(1-q^3)} + \dots.$$
\begin{itemize}
\item[(a)]
(15 points) Compute the coefficients of $q^0$ through $q^{20}$,
and verify that they are all positive.
\item[(b)]
(15 points) There exists a set $S$ of positive integers
such that the coefficient of $q^n$ in $R(q)$
is equal to the number of partitions of $n$
into numbers from the set $S$.
Give a conjecture for the set $S$
and verify that your data for $1 \leq n \leq 20$
support this conjecture.
\end{itemize}
\item %4
(20 points) How many ordinary lattice paths are there from $(0,0)$ to $(20,20)$
that stay in the region $\{(x,y): 0 \leq x-y \leq 3\}$?
\end{enumerate}
\bigskip
\noindent
{\sc Note:}
\medskip
\noindent
Express all answers in the simplest form you can
(e.g., a closed-form expression is preferable
to a recursively-defined function).
\bigskip
\begin{center}
(more)
\end{center}
\pagebreak
\noindent
Except in the cases of problems that request
a conjecture and nothing more,
full credit will be given
only if you offer a proof
(in the sense of an argument
that would convince an intelligent skeptic);
empirical reasoning
(showing that patterns are amply supported by data)
will get you only partial credit.
Do not omit details.
If you are in doubt about which details to include,
consult Prof.\ Propp or consult the preceding sentence.
\medskip
\noindent
You may use a computer to do any of the steps,
but you should send a copy of your code to
{\tt propp@math.wisc.edu}.
\medskip
\noindent
You may use your notes from the class
(including homework solutions)
and all assigned or recommended texts.
Other sources of information are not permitted.
You should not discuss the test with anyone else,
except that you may (and indeed should!)\ contact Prof.\ Propp
if you are unsure
how a question is to be interpreted
or what sort of answer is being sought.
\end{document}