\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 491, Problem Set \#9 (Solutions)\\
\end{center}
\medskip
\begin{enumerate}
\item
\begin{itemize}
\item[(a)]
{\it 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.}
This is the same as the number of strings of length $n$
consisting of the symbols $R$, $L$, and $U$
(short for Right, Left, and Up, respectively)
such that no $R$ is followed by an $L$
and no $L$ is followed by an $R$.
The associated 1-step transfer matrix
$$\left( \begin{array}{ccc}
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 1 \end{array} \right)$$
has characteristic polynomial $(t-1)(t^2-2t-1)$,
so the answer is of the form $A+Br^n+Cs^n$
where $r=1+\sqrt{2}$, $s=1-\sqrt{2}$,
and $A,B,C$ are undetermined coefficients.
Using the fact that the number of polygonal paths of the desired kind
equals 1, 3, and 7 when $n$ is 0, 1, and 2, respectively,
we get $A=0$, $B=1+\sqrt{2}$, and $C=1-\sqrt{2}$, so that
the final answer is $\frac12((1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n+1})$.
To do this in Maple, one might proceed as follows:
\begin{verbatim}
with(linalg):
m := matrix(3,3,[1,0,1,0,1,1,1,1,1]);
p := charpoly(m,t);
sols := solve(p=0,t);
r := sols[2];
s := sols[3];
ans:=solve({A+B*r+C*s=3,A+B*r^2+C*s^2=7,
A+B*r^3+C*s^3=17},{A,B,C});
\end{verbatim}
The result is a set whose three elements are equations
giving the values of $A$, $C$, and $B$ respectively.
(Note that the Maple command I used doesn't return the values of the
variables in the same order as I specified them!
Does anyone know of a variant of my command that doesn't suffer
from this defect?)
By the way, the command {\tt with(linalg)} only needs to be done
once per session.
\item[(b)]
{\it 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$.}
An appropriate generating function is
$\sum_{n \geq 1} (uM^nv)x^n$,
where $u=(1,1,y)$, $v=(1,1,1)^T$ (the transpose),
and $M$ is a modified version of the preceding transition matrix
in which the 1's that correspond to Up-steps are replaced by $y$'s,
so that when we multiply the matrix by itself,
obtaining a matrix of polynomials in $y$,
a term equal to $y^k$
corresponds to a path that takes $k$ Up-steps.
(After we've expressed this generating function
in closed form, we'll be able to differentiate it
to get at the information we seek.)
The entry $y$ in the vector $u$ occurs
because it corresponds to taking a step in the Up direction.
The generating function can be written as
the sum of the nine entries of
$u(\sum (Mx)^n)v = u(I-Mx)^{-1}v$,
where the matrix $Mx$ is
$$\left( \begin{array}{ccc}
x & 0 & xy \\
0 & x & xy \\
x & x & xy \end{array} \right).$$
We can use Maple for this:
\begin{verbatim}
with(linalg):
Mx := [[x,0,x*y],[0,x,x*y],[x,x,x*y]];
Id := [[1,0,0],[0,1,0],[0,0,1]];
u := [[x,x,x*y]];
v := [[1],[1],[1]];
inv := inverse(Id-Mx);
ans := simplify(multiply(u,inv,v)[1,1]);
\end{verbatim}
(Note that for Maple, $xy$ must be written as {\tt{x*y}};
also note that {\tt{Mx}} is just an indivisible symbol.
Observe that the symbol {\tt{I}} is reserved for
the square root of minus 1.
Finally, note that the output of {\tt{multiply(u,inv,v)}}
is a 1-by-1 matrix, not a number;
hence the need to extract its 1,1 element
with the matrix-entry-extraction operator {\tt{[1,1]}}.)
The answer {\tt{ans}} turns out to be
the simple expression $$\frac{2+y+xy}{1-x-xy-x^2y}.$$
If we differentiate this with respect to $y$
and then set $y=1$,
we will obtain the generating function in which
the coefficient of $x^n$
is the sum of the heights of all the polygonal paths.
\begin{verbatim}
heights := simplify(subs(y=1,diff(ans,y)));
\end{verbatim}
gives
$$\frac{x(1+x)^2}{(1-2x-x^2)^2}.$$
To find the asymptotic behavior of the coefficients
of this generating function, use partial fractions
over the field generated over the rationals
by the square root of 2:
\begin{verbatim}
convert(heights, parfrac, x, sqrt(2));
\end{verbatim}
Unfortunately, Maple gives us an answer in which
the denominators of the four terms
are of the form $x+a$ instead of $1+bx$,
but this is only a minor annoyance.
The term that controls the growth rate
is the term whose denominator is quadratic
and vanishes closest to $x=0$.
This is the term
$$\frac14 \frac{-1+\sqrt{2}}{(x+1-\sqrt{2})^2}
= \frac{1+\sqrt{2}}{4} (1-x(1+\sqrt{2}))^{-2}.$$
Now we may apply the binomial theorem with exponent $-2$:
the coefficient of $x^n$ in the preceding generating function equals
$$\frac{1+\sqrt{2}}{4} {-2 \choose n} (-(1+\sqrt{2}))^n
= \frac{1+\sqrt{2}}{4} {n+1 \choose n} (1+\sqrt{2})^n,$$
which grows like $\frac{n}{4} (1+\sqrt{2})^{n+1}$.
The answer to part (a) grows like
$\frac{1}{2} (1+\sqrt{2})^{n+1}$,
so, taking the ratio, we find that
the expected height tends to the limit $n/2$.
(There must be a nice way to see this!)
\end{itemize}
\end{enumerate}
\end{document}