\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
\newcommand{\Z}{{\bf Z}}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#20 \\
(due 12/11/03)
\end{center}
\medskip
\begin{enumerate}
\item
(from unpublished work of Douglas Zare)
Let $G_{m,n}$ be the directed graph with vertex set
$\{(i,j) \in \Z \times \Z: 0 \leq i \leq m, \ 0 \leq j \leq n\}$,
with an arc from $(i,j)$ to $(i',j')$ iff $(j'-j,i'-i)$ is
$(1,0)$, $(0,1)$, or $(1,1)$.
\begin{itemize}
\item[(a)] For any legal path $P$ in $G_{m,n}$ from $(0,0)$ to $(m,n)$,
define $d(P)$ as the number of diagonal steps in $P$
plus the number of upward steps in $P$ that are followed
{\it immediately\/} by a rightward step.
Show that the number of paths $P$ with $d(P)=k$
is exactly $2^k {m \choose k} {n \choose k}$.
\item[(b)] Let $M$ be the $(n+1)$-by-$(n+1)$ matrix
with rows and columns indexed from 0 through $n$
whose $i,j$th entry is the total number
of paths in $G_{i,j}$ from $(0,0)$ to $(i,j)$.
Use the result of part (a) to find the LDU decomposition of $M$.
That is: find square matrices $L$, $D$, $U$ such that
$LDU=M$, where
$L$ (resp.\ $U$) is a lower (resp.\ upper) triangular matrix
with 1's on the diagonal
and where $D$ is a diagonal matrix
(whose diagonal entries are permitted to be different).
Use this in turn to compute $\det(M)$.
\item[(c)] Interpret $M$ as the Lindstrom matrix
of some directed graph and use this in turn to interpret $\det(M)$
as the number of perfect matchings of some graph $H_n$.
Be explicit about what $H_n$ looks like.
\end{itemize}
\end{enumerate}
\end{document}