\documentclass[12pt]{article}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#13: Solutions\\
\end{center}
\medskip
\begin{enumerate}
\item
{\it An ``augmented Aztec diamond of order $n$''
is a subset of the square grid
formed by symmetrically stacking rectangles of height 1
and respective widths $2,4,6,\dots,2n-2,2n,2n,2n,2n-2,\dots,6,4,2$
(note that there are 3 rectangles of width $2n$ being stacked).
Express the generating function $\sum_{n \geq 0} a_n t^n$
as an algebraic function of $t$,
where $a_n$ denotes the number of domino-tilings
of the augmented Aztec diamond of order $n$,
and we put $a_0=1$.
(Note that the augmented Aztec diamond of order 1
is just a rectangle of height 3 and width 2.)}
Divide the region into unit squares,
each of which has two vertical edges of length 1;
put a dot at the midpoint of a vertical edge
if the sum of the $x$ and $y$ coordinates of the edge
has the same parity as the sum of the $x$ and $y$ coordinates
of the two points where the horizontal symmetry axis
crosses the boundary of the region.
As in the examples studied in class,
the dominos that have two dots on their boundaries
(rather than a single dot in their interior)
give rise to paths that join up dots
on the boundary of the region.
Since there are only two dots on the boundary of the region
(one at the left and one at the right),
the domino tilings of the augmented Aztec diamond of order $n$
correspond to paths from $(0,0)$ to $(2n,0)$
in which the legal steps are $(+1,+1)$, $(+1,-1)$, and $(+2,0)$.
Call a path with steps of this kind ``high'' if it never goes below
the line $y=0$, and ``low'' if it never goes above the line $y=1$.
(Note that the trivial path, with no arcs, is both high and low.)
Also call a path ``primitive'' if it is non-trivial
and it intersects the line $y=0$ only at its left and right endpoints.
(Note that a single horizontal arc of length 2
counts as primitive, high, and low.)
Let $a_n^{high}$ be the number of high paths joining $(0,0)$ and $(2n,0)$
(which is also the number of low paths joining these points),
let $a_n^{prim}$ be the number of primitive paths
joining $(0,0)$ and $(2n,0)$,
and let $a_n^{high,prim}$ be the number of paths that are
both high and primitive.
Put $A(x) = \sum_{n \geq 1} a_n x^n$,
and define $A^{high}(x)$,
$A^{prim}(x)$,
and $A^{high,prim}(x)$ analogously.
Since every path is a concatenation of primitive paths in a unique way,
we have $$A(x) = 1/(1-A^{prim}(x)).$$
On the other hand, a primitive path
is either a high primitive path
or a low primitive path,
and these two cases only overlap when the primitive path
is a rightward arc of length 2,
so that $$A^{prim}(x)=2A^{high,prim}(x)-x.$$
A high primitive path either is a single rightward arc
or else consists of
an upward diagonal followed by a high path followed by a downward diagonal,
so that $$A^{high,prim}(x)=x+xA^{high}(x).$$
Finally, a high path is a concatenation of high primitive paths
in a unique way, so $$A^{high}(x)=1/(1-A^{high,prim}).$$
These last two equations refer only to the two unknowns
$A^{high}$ and $A^{high,prim}$,
so we can solve for both,
obtaining in particular
$A^{high,prim}(x)=(1+x-\sqrt{1-6x+x^2})/2$.
Plugging this into the second equation, we get
$A^{prim}(x) = 1-\sqrt{1-6x+x^2}$,
and plugging this in turn into the first equation, we get
$A(x) = 1/\sqrt{1-6x+x^2}$.
\item
{\it Use the exchange principle for 2-routings to find
a compact formula for the number of lozenge-tilings
of the semiregular hexagon with side-lengths $a,b,2,a,b,2$.}
Assume the sides of length 2 are vertical.
As in class, draw a dot at the midpoint of every vertical edge,
so that every horizontal tile has a dot in its middle
and every non-horizontal tile has two dots on its boundary,
which we can join up to form paths.
There are four dots on the boundary of the hexagon:
two on the left (call them $s_1$ and $s_2$, from top to bottom)
and two on the right (call them $t_1$ and $t_2$, from top to bottom).
Is it easy to see that tilings of such a region
are equivalent to 2-routings of a DAG
that join $s_1$ with $t_1$ and $s_2$ with $t_2$.
The number of paths joining $s_1$ with $t_1$ is
$(a+b)!/a!b!$,
as is the number of paths joining $s_2$ with $t_2$.
On the other hand, the number of paths joining $s_1$ with $t_2$ is
$(a+b)!/(a-1)!(b+1)!$
while the number of paths joining $s_2$ with $t_1$ is
$(a+b)!/(a+1)!(b-1)!$.
Since every way of joing $s_1$ with $t_2$ and $s_2$ with $t_1$
leads to an intersection, the exchange principle applies,
and we conclude that the number of 2-routings is
$$\left(\frac{(a+b)!}{a!b!}\right)^2 -
\left(\frac{(a+b)!}{(a-1)!(b+1)!}\right)
\left(\frac{(a+b)!}{(a+1)!(b-1)!}\right),$$
which simplifies to
$$\frac{(a+b)!(a+b+1)!}{a!(a+1)!b!(b+1)!}.$$
\end{enumerate}
\end{document}