\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 192r, Problem Set \#7 (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}
\item
{\it 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)]
{\it Give an explicit formula for the entries of the (triangular) matrix
that expresses the $y_k$ in terms of the $x_j$.}

I'll give the matrices in upper-triangular form
(though I see that in the statement of the problem
I used lower-triangular form,
since I asserted in part (b) that
each \emph{row} has only finitely many non-zero entries).
For $j=0$, the $j,k$th entry in the matrix
(the coefficient of $x_j$ in the expansion of $y_k$)
is $\frac12 {k \choose k/2}$
(which we interpret as 0 if $k/2$ is non-integer).
For $j>0$, the $j,k$th entry is simply ${k \choose (j+k)/2}$ 
(which we interpret as 0 if $k<j$ or if $(j+k)/2$ is not an integer).
Here's the excerpt of the matrix with $j,k$ running between 0 and 9:
$$\left( \begin{array}{rrrrrrrrrr}
1 & 0 & 1 & 0 & 3 &  0 & 10 &  0 & 35 &   0 \\
0 & 1 & 0 & 3 & 0 & 10 &  0 & 35 &  0 & 126 \\
0 & 0 & 1 & 0 & 4 &  0 & 15 &  0 & 56 &   0 \\
0 & 0 & 0 & 1 & 0 &  5 &  0 & 21 &  0 &  84 \\
0 & 0 & 0 & 0 & 1 &  0 &  6 &  0 & 28 &   0 \\
0 & 0 & 0 & 0 & 0 &  1 &  0 &  7 &  0 &  36 \\
0 & 0 & 0 & 0 & 0 &  0 &  1 &  0 &  8 &   0 \\
0 & 0 & 0 & 0 & 0 &  0 &  0 &  1 &  0 &   9 \\
0 & 0 & 0 & 0 & 0 &  0 &  0 &  0 &  1 &   0 \\
0 & 0 & 0 & 0 & 0 &  0 &  0 &  0 &  0 &   1
\end{array} \right)$$
One way to make this array is as follows:
\begin{verbatim}
entry := proc(j,k)
        if (j=0 and k mod 2 = 0) then 
                simplify((1/2)*binomial(k,k/2));
        elif (k>=j and j+k mod 2 = 0) then 
                binomial(k,(j+k)/2);
        else 0; fi; end;
m := matrix(10,10,[seq(seq(entry(j,k),k=0..9),j=0..9)]);
\end{verbatim}
\item[(b)]
{\it 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,
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.}

In Maple (with the {\tt{linalg}} library loaded), 
{\tt{inverse(m)}} gives
$$\left( \begin{array}{rrrrrrrrrr}
2 & 0 &-2 & 0 & 2 &  0 & -2 &  0 &  2 &   0 \\
0 & 1 & 0 &-3 & 0 &  5 &  0 & -7 &  0 &   9 \\
0 & 0 & 1 & 0 &-4 &  0 &  9 &  0 &-16 &   0 \\
0 & 0 & 0 & 1 & 0 & -5 &  0 & 14 &  0 & -30 \\
0 & 0 & 0 & 0 & 1 &  0 & -6 &  0 & 20 &   0 \\
0 & 0 & 0 & 0 & 0 &  1 &  0 & -7 &  0 &  27 \\
0 & 0 & 0 & 0 & 0 &  0 &  1 &  0 & -8 &   0 \\
0 & 0 & 0 & 0 & 0 &  0 &  0 &  1 &  0 &  -9 \\
0 & 0 & 0 & 0 & 0 &  0 &  0 &  0 &  1 &   0 \\
0 & 0 & 0 & 0 & 0 &  0 &  0 &  0 &  0 &   1
\end{array} \right)$$
Column-sums are $2,1,-1,-2,-1,1,2,1,-1,-2,\dots$,
which seems to be a periodic sequence.
If we take absolute values before summing, we get
$2,1,3,4,7,11,18,29,47,76,\dots$,
which looks like the Lucas sequence.
We can certainly conjecture that the $k,j$ entry
has sign $(-1)^{(k-j)/2}$.
(We index rows by $k$ and columns by $j$ now,
since this is the inverse matrix.)
One might also note that the successive non-zero diagonals
(leaving aside the principal diagonal, which has a glitch
in its first entry)
appear to be given by polynomials of degree 1, 2, 3, etc.

The key to finding a formula for the entries
lies in the observation that
most of the entries in the $j$ column
are divisible by $j$, or nearly so.
In fact, if you throw out the 0 row and 0 column,
get rid of all the signs,
and divide each entry by its column-index
and then multiply each entry by its row-index,
you get the integer matrix
$$\left( \begin{array}{rrrrrrrrr}
1 & 0 & 1 & 0 &  1 &  0 &  1 &  0 &   1 \\
0 & 1 & 0 & 2 &  0 &  3 &  0 &  4 &   0 \\
0 & 0 & 1 & 0 &  3 &  0 &  5 &  0 &  10 \\
0 & 0 & 0 & 1 &  0 &  4 &  0 & 10 &   0 \\
0 & 0 & 0 & 0 &  1 &  0 &  5 &  0 &  15 \\
0 & 0 & 0 & 0 &  0 &  1 &  0 &  6 &   0 \\
0 & 0 & 0 & 0 &  0 &  0 &  1 &  0 &   7 \\
0 & 0 & 0 & 0 &  0 &  0 &  0 &  1 &   0 \\
0 & 0 & 0 & 0 &  0 &  0 &  0 &  0 &   1
\end{array} \right)$$
which is just Pascal's triangle!
So the coefficient of $y_k$ in the expansion of $x_j$
(relative to the basis $y_0,y_1,\dots$)
is $$(-1)^{(k-j)/2} \: \frac{j}{k} \: {(j+k-2)/2 \choose (j-k)/2}$$
as long as $j \geq k \geq 1$ and $j,k$ have the same parity;
in the case $k = 0$, the coefficient is $$(-1)^{(j-k)/2} \: 2$$
as long as $j \geq 0$ and $j,k$ have the same parity;
otherwise, the coefficient vanishes.

\end{itemize}
\end{enumerate}

\end{document}
