\documentclass[11pt]{article}
\usepackage{fullpage}
\title{Observations regarding matchings of snake graphs and related phenomena}
\author{Martin Hock\\{\tt mhock@cs.wisc.edu}}
\begin{document}
\maketitle
\section{A combinatorial interpretation of $A$ and $B$}
Let
\[A = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right)\]
and
\[B = \left( \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\right).\]
We see that
\[\left( \begin{array}{cc} a & b \\ c & d \end{array}\right)A =
\left( \begin{array}{cc} a+b & a \\ c+d & c \end{array}\right)\]
and
\[\left( \begin{array}{cc} a & b \\ c & d \end{array}\right)B =
\left( \begin{array}{cc} b & a+b \\ d & c+d \end{array}\right).\]
In other words, $A$ puts into the left column a sum of the left and right
columns, and puts into the right column a copy of the old left column for
future summation.  We can call the left column the ``accumulation column'' 
and the right column the ``summand column''; for $B$ the opposite is true.
On the other hand, the two rows never intermix.
We can make this even more obvious by beginning every chain of multiplications
with the base matrix
\[C = \left( \begin{array}{cc} 1 & 1 \\ 0 & 0 \end{array}\right).\]
Then the bottom row is always empty, so we don't even need to worry about
it.  The sum still works out to what it was before.  Thus, the bottom row
is merely an old copy of the top row, so in some sense, since the individual
entries are unnecessary, they are not individually meaningful.

What does switching matrices do exactly?  We switch the interpretation of
our columns; now what once was our accumulation column becomes our addition
column, and vice versa.  But with the switching of this interpretations comes
a price.  If we repeatedly multiply the same matrix, the summand column
always holds the previous value of the accumulation matrix, but if we
multiply a different matrix, the summand column's value remains the same,
although the accumulation column dutifully accumulates the sum of both
columns.
\section{Cube snake recurrence}
Paul and Abby have independently verified that the generating function for
the straight cube snake is the following:
\[C(x) = \frac{2+3x-x^2}{1-3x-3x^2+x^3}.\]
This is represented in Sloane's Encyclopedia as A003697.  The entry contains
a note that the values alternate between squares and twice squares.  When
we de-multiplex the two sequences, we find:
\[c_n=\left\{\begin{array}{ll}
2a_{n/2+1}^2 & n\mbox{ is even}\\
b_{(n-1)/2+1}^2 & n \mbox { is odd}
\end{array}\right.\]
where $a_n$ is the number of spanning trees of a 2 by $n$ grid, Sloane's
A001353, and $b_n$ is the number of perfect matchings of a 3 by $2n$ grid,
Sloane's A001835.  We call this the straight cube matching theorem.
\subsection{Proof of the Straight Cube Matching Theorem}
First, we note that both $A=(a_0,a_1,a_2,\ldots)$ and $B$ have the same 
recurrence:
$a_n=4a_{n-1}-a_{n-2}$ and $b_n=4b_{n-1}-b_{n-2}$.  The only difference is that
$a_0=0$ and $a_1=1$ versus $b_0=b_1=1$.  (Intriguingly, even though the $b_n$
sequence begins ``bigger,'' it is actually dominated by the $a_n$ sequence for
all $n>0$.)  Let's use this to find a homogeneous recurrence for $a_n^2$
(and equivalently for $b_n^2$):
\begin{eqnarray*}
a_n &=& 4a_{n-1} - a_{n-2} \\
a_n^2 &=& (4a_{n-1} - a_{n-2})^2 \\
&=& 16a_{n-1}^2 - 8a_{n-1}a_{n-2} + a_{n-2}^2 \\
&=& 16a_{n-1}^2 - 8(4a_{n-2}-a_{n-3})a_{n-2} + a_{n-2}^2 \\
a_{n-1}^2 &=& 16a_{n-2}^2 - 8a_{n-2}a_{n-3} + a_{n-3}^2 \\
a_n^2 + a_{n-1}^2 &=& a_{n-3}^2+a_{n-2}^2+16a_{n-1}^2-16a_{n-2}^2 \\
a_n^2 &=& 15a_{n-1}^2 - 15a_{n-2}^2 + a_{n-3}^2
\end{eqnarray*}
But actually, since we want to interleave these sequences, we really want the
following recurrence: $a_n^2 = 15a_{n-2}^2 - 15a_{n-4}^2 + a_{n-6}^2$
This relation will hold true for both interleaved sequences and thus the
sum of them, since doubling the entire sequence does not affect the recurrence.
We now use Wilf's method to find the generating function for this combined 
interleaved sequence:
\begin{eqnarray*}
-\frac{F(x)-(2+9x+32x^2+121x^3+450x^4+1681x^5)}{x^6} &+& \\
15\frac{F(x)-(2+9x+32x^2+121x^3)}{x^4} &+& \\
-15\frac{F(x)-(2+9x)}{x^2} &+& \\
F(x) &=& 0
\end{eqnarray*}
Solving, we find \[F(x)=-\frac{x^2-3x-2}{x^3-3x^2-3x+1}=C(x),\]
as desired.
\subsection{A-B Bijection}
We would like to find a bijection between members of the interleaved sequence
and members of $C$.  To begin with, it may be helpful to unify $A$ and $B$.
They are related in the following way:
$a_n=\sum_{i=1}^nb_n$ if $n\geq 1$.  To prove this, first we show
\[a_n=3a_{n-1}+2a_{n-2}+2a_{n-3}+\cdots+2a_1+2a_0+1.\]
Examine a spanning tree $T$ of a 2 by $n$ grid graph, which we call $G_n$.
We consider the subgraph of $T$ induced by columns of $G_n$, starting from the
right and working left, i.e., the rightmost $k$ columns at a time, referring
to the graph induced on $k$ columns as $T_k$ ($T_n = T$). If no $T_k$ for 
$k<n$ is a spanning tree, we note that the graph must look like a giant letter
$\mathsf{C}$.
If there were any vertical edges earlier than the far left edge, then if we
consider the smallest $T_k$ that contains a vertical edge, it must be a
$C$-shaped spanning tree.  Otherwise, $T_k$ would not be connected, but this
would imply that $T$ is not connected, violating the assumption that it is a
spanning tree.  If there is such a vertical edge, examine the largest $T_k$
(where $k<n$) is a spanning tree.  If $k=n-1$, then we have three possibilities
for $T_n$: either we add a $\mathsf{\Gamma}$ (the ``Gamma'' case), an 
$\mathsf{L}$ (``Ell''), or a $=$ (``Equals'') to connect the last two
unconnected vertices to the tree; these are the only three ways to connect
them which will not add a loop.  Otherwise, $k<n-1$.  In that case, if we
examine $T_{k+1}$, there will be one disconnected vertex, either the upper 
(``Upper'') or lower (``Lower'').  If both are disconnected, $T$ cannot be 
connected.  In either of these
cases, the remainder of $T$ must look like a giant $C$, but since there are
two possible extensions to $T_k$ to make it a spanning tree, for each spanning
tree on $T_k$ where $k<n-1$ there are two possible spanning trees on $G_n$.

Since we have just identified a way of breaking down any spanning tree on
$G_n$ into a smaller case, we have covered all cases.  This means that if
$G_n$ has $a_n$ spanning trees,
\[a_n=3a_{n-1}+2a_{n-2}+2a_{n-3}+\cdots+2a_1+2a_0+1.\]
From this, we can easily derive that $a_{n+1}=a_n+3a_n-a_{n-1}=4a_n-a_{n-1}$.

Now we go on to show the bijection.  We prove this inductively.  We
assume we have a bijection for all cases through $n-1$.  For the base case,
since the starting values are both 1, this is trivial:
the single spanning tree of the 2 by 1 grid corresponds to the single empty
matching of the 3 by 0 grid.

We now show the bijection for the $n$ case.  We recall
\[a_n = 3a_{n-1}+2a_{n-2}+2a_{n-3}+\cdots+2a_1+1.\]
The first term is different.  This corresponds to taking all of the tilings
we have which correspond to $a_{n-1}$ and tacking onto the left two extra 
columns worth
of irreducible tiling, of which there are three ways: two vertical dominos atop
a horizontal domino, a horizontal domino atop two vertical dominos, or three 
horizontal dominos.  We can see by exhausting all possibilities that these are 
the only tilings of the 2 by 3 rectangle, and that they are all irreducible.
We will correspond these to the Gamma, Ell, and Equals cases, respectively,
as the seams between the tiles resemble these shapes to some degree.

The remaining $a_k$ terms correspond to taking all of the
tilings we have which correspond to $a_k$ and tacking onto the left $2(n-k)$ 
irreducible
tilings.  These tilings have the following form: either the top two rows begin
and end with a vertical domino and the rest is tiled with horizontal dominos,
or the bottom two rows begin and end with a vertical domino and the rest is
tiled with horizontal dominos.  We will correspond these to the Upper and
Lower cases, respectively, to correspond to the positions we placed the
vertical dominos.  To prove that these are the only two
irreducible tilings,
we give a direct argument.  Starting from the leftmost column, we 
note that the tiling cannot begin with three horizontal dominos, so it must
either begin with a vertical domino stacked atop a horizontal domino, or vice
versa.  Examining the two rows taken up by the vertical domino, we can either
put a vertical domino or two horizontal dominos.  However, if we put a vertical
domino, the tiling is not irreducible because there is now a break after the
first two columns.  Furthermore, if we put two horizontal dominos, we must
now put a horizontal domino in the remaining row.  The edge of the tiling is
now the same as before, so we may repeat the argument all the way to the edge
of the rectangle, where in order to finish off the tiling we must place a
vertical domino in the final column, in the same two rows as the original
vertical domino.

We still have one tree remaining.  Since all of our constructions above
involve adding dominos, this corresponds to the single construction which
consists of no dominos: the empty tiling of the empty rectangle.

Since we always tack the irreducible tiling of the $2k$ rectangle onto the 
leftmost $2k$ columns, we can tell by looking at a tiling which case it
corresponds to, by selecting the largest irreducible tiling which includes
the leftmost column and then recursing on the remaining part of the tiling.
(This could also be the empty tiling, which we have also covered.)  Since
every tiling fits this pattern, we have covered all possible tilings, and 
based on the recurrence we are following, we have also covered all possible 
spanning trees.

Since we have corresponded all of the first $n-1$ cases, and from this built
a construction which corresponds the $n$ case, we have completed the proof
by induction.
\subsection{C Bijection?}

\end{document}
