\documentclass[12pt]{article}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#16: Solutions\\
\end{center}
\medskip
\begin{enumerate}
\item
\begin{itemize}
\item[(a)]
{\it How many lattice paths from $(0,0)$ to $(m,n)$
remain the same when you rotate them by 180 degrees
about $(\frac{m}{2},\frac{n}{2})$?
Prove your answer.}
By symmetry, the lattice path must cross the line $x+y=(m+n)/2$
at the point $(m/2,n/2)$,
which is impossible if $m$ and $n$ are both odd
(since for every point on the lattice path,
either the $x$-coordinate or the $y$-coordinate is an integer).
If $m$ and $n$ are both even,
then $(m/2,n/2)$ is a lattice point,
and we can see that every lattice path from $(0,0)$ to $(m/2,n/2)$,
when rotated 180 degrees about the point $(m/2,n/2)$,
yields a lattice path from $(0,0)$ to $(m,n)$ that is
invariant under 180 rotation.
Since it is also clear that every invariant lattice path
is of this form,
the number of such paths is just $\frac{(m/2+n/2)!}{(m/2)!(n/2)!}$.
If $m$ is even and $n$ is odd,
then $(m/2,n/2)$ is the midpoint of the segment
joining $(m/2,(n-1)/2)$ and $(m/2,(n+1)/2$),
and this segment must be part of the lattice path.
In particular, the lattice path must go from $(0,0)$ to $(m/2,(n-1)/2)$.
In this case, the lattice paths from $(0,0)$ to $(m,n)$
that are invariant under rotation
are in bijection with the lattice paths from $(0,0)$ to $(m/2,(n-1)/2)$,
and the number of paths is just $\frac{(m/2+n/2-1/2)!}{(m/2)!(n/2-1/2)!}$.
Likewise, if $m$ is odd and $n$ is even,
the number of invariant paths is $\frac{(m/2+n/2-1/2)!}{(m/2-1/2)!(n/2)!}$.
\end{itemize}
\item
\begin{itemize}
\item[(a)]
{\it How many lattice paths from $(0,0)$ to $(n,n)$
remain the same when you flip them across the diagonal
joining $(n,0)$ and $(0,n)$?
Prove your answer.}
Such a path must cross the line $x+y=n$ at some point $(i,j)$.
If we flip the path from $(0,0)$ to $(i,j)$ across the diagonal,
we get a lattice path from $(0,0)$ to $(n,n)$ of the specified kind,
and every such path arises in this way.
Thus the paths from $(0,0)$ to $(n,n)$
that are invariant under reflection
are in bijection with
lattice paths from $(0,0)$ to the line $x+y=n$,
of which there are
${n \choose 0} + {n \choose 1} + \dots + {n \choose n} = 2^n$.
\item[(b)]
{\it What is the sum of the $q$-weights of these lattice paths?
Conjecture an answer.}
Consider a lattice path from $(0,0)$ to $(i,j)$, with $i+j=n$.
If its $q$-weight is $q^m$,
then the associated path from $(0,0)$ to $(n,n)$
(obtained by reflection)
has $q$-weight $q^{2m+j^2}$.
(To see this, split the area under the path
into three parts:
the part below and to the left of $(i,j)$,
the part above and to the right of $(i,j)$,
and the part below and to the right of $(i,j)$;
these regions have area $m$, $m$, and $j^2$, respectively.)
Therefore, using the function $P_{m,n}(q)$ from the previous problem set,
we can write the sum of the $q$-weights of the symmetrical lattice paths
from $(0,0)$ to $(n,n)$ as
$\sum_{j=0}^n q^{j^2} P_{n-j,j}(q^2)$.
Here we can use Maple.
First, from what we learned in class, we can write a program for $P_{m,n}$:
\begin{verbatim}
P := proc(m,n) local i,j;
expand(simplify(mul(mul(
(1-q^(i+j))/(1-q^(i+j-1)),
i=1..m),j=1..n))); end;
\end{verbatim}
Then we can write a program to $q$-count reflection-invariant lattice paths
\begin{verbatim}
S := proc(n) local j;
expand(simplify(add(q^(j^2)*
subs(q=q^2,P(n-j,j)),j=0..n)));
end;
\end{verbatim}
A little bit of exploration will then yield the observation
that $S(n)$ divided by $S(n-1)$ equals $1+q^{2n-1}$,
so that $$S(n)=(1+q)(1+q^3)\cdots(1+q^{2n-1}).$$
In fact, we can prove this combinatorially by dividing
the area under the lattice path into L-shapes
with their corners at the lower right.
Each L-shape, being symmetrical, contains an odd number of squares.
Also, since the L-shapes fit together to form a (flipped) Young diagram,
their sizes must be distinct,
with the the largest possible L-shape being of size $2n-1$.
Finally, note that if we take any set of odd numbers from $1$ to $2n-1$,
L-shapes of those sizes may be fit together to form
a flipped Young diagram that is reflection-invariant
and whose boundary is a reflection-invariant lattice path.
\item[(c)]
{\it Why is there no part (b) for question 1?}
Because all of the paths have the same $q$-weight, namely $q^{AB/2}$,
so it would have been silly to ask the question.
(Actually, the preceding paragraph {\it would} have been the right answer,
if someone else had asked the question,
or if I had asked it in class.
But since I asked the question {\it on the homework\/},
I obviously didn't think it was too silly a question to ask!
A psychologically accurate answer is that
I originally included a part (b),
then deleted it,
and then decided to re-include it,
but in a slightly off-beat way
that would hopefully be amusing
or at least provocative.)
\end{itemize}
\end{enumerate}
\end{document}