\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