\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{mathrsfs}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Counting Colorful Tilings of \\
\vskip .1in
Rectangular Arrays
}
\vskip 1cm
\large
Kathryn Haymaker and Sara Robertson\\ 
Villanova University \\
Department of Mathematics and Statistics\\
St. Augustine Center 305\\
800 E. Lancaster Avenue\\
Villanova, PA 19085 \\
USA\\ 
\href{mailto:kathryn.haymaker@villanova.edu}{\tt kathryn.haymaker@villanova.edu} \\
\href{mailto:srober23@villanova.edu}{\tt srober23@villanova.edu}  

\end{center}


\begin{abstract} 
In this paper we give recursive formulas for the number of colorful
tilings of small rectangular arrays. We enumerate the tilings of a $2
\times n$ board with painted squares, dominoes, and $I$-trominoes. We
also provide a recursion formula for the number of tilings of a
$3\times n$ board with colorful squares and dominoes. Finally, we
describe a general method for calculating the number of colorful
tilings of an $m \times n$ board with squares and dominoes.
\end{abstract}

\section{Introduction}
\label{sec:intro}
How many ways are there to tile a rectangular board with painted
squares and dominoes, when there are $a$ available colors for the
squares and $b$ available colors for the dominoes?  There is no
closed-form expression for the number of tilings of an $m\times n$
board with dominoes and squares, but the problem has been extensively
studied in the area of mathematical physics, where the pieces are
called monomers and dimers \cite{ml70, g74, hm84, hm85,bos01,erw11}.
Jerrum \cite{j87} shows that the general monomer-dimer problem is
computationally intractable.


The number of ways to tile a $2\times n$ board using squares and
dominoes is given by the sequence 1, 2, 7, 22, 71, $\ldots$
(\seqnum{A030186}). This sequence, as well as its corresponding
recursion, have been well-studied \cite{ml70, g74}. In a generalization
of this result,   Katz and Stenson found a recursion for the number of
painted tilings of  a $2\times n$ board \cite{ks09}. Using a different
approach, we obtain a recursion for the number of  tilings of a
$3\times n$ board with painted dominoes and squares.  We begin by
introducing the technique pioneered by Read to count unpainted
square-domino tilings \cite{r82}, and we demonstrate a modification of
that method to obtain a generating function for the number of tilings
of a $2\times n$ board with painted squares, dominoes, and
$I$-trominoes (also called trimers). Following the convention in
earlier work \cite{r82}, in this paper we will refer to $I$-trominoes
as simply trominoes---see Figure~\ref{fig:tiles}.

\begin{figure}[h!]
\includegraphics[scale=0.6]{tiles.eps}
\centering
\caption{A square, domino, and $I$-tromino (which we refer to as a `tromino', excluding the $L$-tromino shape in this work).}
\label{fig:tiles}
\end{figure}

We then obtain the recursion for the number of tilings of a $3\times n$
board with painted squares and dominoes. The final section of the
paper  generalizes the approach of Ahrens \cite{a81} for counting the
number of painted square-domino tilings of general rectangular arrays.




\section{Coverings of $2 \times n$ boards with squares, dominoes, and trominoes}
\label{sec:coverings}
 

Read  \cite{r82} introduces a  method for counting the number of tilings of small rectangular boards using squares and dominoes.  Read also applies it to counting tilings using diagonal dominoes, as well as tilings in which the domino is exchanged for a $1 \times 3$ rectangular tile called a tromino. Read's method is readily adapted to many variations of the original dimer problem. In the following proof, we extend Read's method to count the number of tilings which use painted squares, dominoes, and trominoes on $2 \times n$ boards. The new ideas in this application of Read's techniques include allowing different color choices for the tiling components and tiling using three different types of tiles: squares, dominoes, and trominoes.


Let $s_n^{a,b,c}$ be the number of ways to tile a $2\times n$ board with painted squares, dominoes and trominoes, where there are $a$ available colors for each square, $b$ available colors for each domino, and $c$ available colors for each tromino. 


\begin{theorem} \label{thm:tromino} 
The following recurrence relation holds for $n \geq 4$:
\begin{align*}s_n^{a,b,c} &= (a^2+2b)s_{n-1}^{a,b,c}+(a^2b+ac)s_{n-2}^{a,b,c}+(a^3c+3abc-b^3+2c^2)s_{n-3}^{a,b,c}\\ &+(a^2c^2-ab^2c-2bc^2)s_{n-4}^{a,b,c}+(b^2c^2-ac^3)s_{n-5}^{a,b,c}-c^4s_{n-6}^{a,b,c}
\end{align*}
with the following initial conditions: 
\begin{align*}
s_{-2}^{a,b,c} &:=0 \\
s_{-1}^{a,b,c} &:=0 \\
s_{0}^{a,b,c} & =1 \\
s_{1}^{a,b,c} & = a^2+b \\
s_{2}^{a,b,c} & = a^4+4a^2b+2b^2 \\
s_3^{a,b,c} & = a^6+7a^4b+11a^2b^2+3b^3+2a^3c+4abc+c^2 .
\end{align*} 
\end{theorem}
\begin{proof}
We begin by determining the finite number of possible \textit{profiles} which may occur on a $2\times n$ board at any stage in the tiling process. Tiling begins on the left-hand-side of the board; the profiles describe the boundary preceding the portion of the board that remains untiled. Each profile defines a \textit{target square}, the topmost uncovered square in the leftmost column which has yet to be completely tiled, indicated using an \textbf{*}. Placing either a square, domino, or a tromino on the target square results in a new profile. 
\begin{figure}[h!]
\includegraphics[scale=0.6]{Profiles.eps}
\centering
\caption{Profiles for $2\times n$ case with squares, dominoes, and trominoes.}
\label{fig:profiles}
\end{figure}

In this case, there are six unique profiles, as shown in Figure~\ref{fig:profiles}. The name of each profile is indicated by the letter $A$, $B$, $C$, $D$, $E$, or $F$. The arrows and their accompanying $x$, $y$, or $z$ describe the tile placement that generates the resulting profile from the starting profile, where an $x$ indicates the addition of a domino, a $y$ indicates the addition of a square, and $z$ indicates the addition of a tromino. 

Each profile can be expressed as a generating function in terms of the addition of the necessary tile to those profiles from which it is derived. For example, as profile $D$ can only be created by adding a tromino to profile $A$, it follows that $D(x,y,z) = zA(x,y,z)$. By dropping the arguments, we obtain the following simplified equations:
\begin{align*}
\begin{split}
A &= 1 + xA + xB +yC +zD +yE +xF\\
B &= xA + yD + zE\\
C & = yA +yB + xD + xE + zF\\
D &= zA\\
E &= zB + xC +yF\\
F &= zC .
\end{split}
\end{align*}

It is worth noting that the first equation, which represents tilings stemming from the profile that is simply a vertical line, includes the addition of a 1. This results from the fact that there is is one way to tile a completely empty board, which would be categorized by profile $A$, with no tiles.  

As $D$, $E$, and $F$ can be written in terms of $A$, $B$, and $C$, substitutions can be made to produce the simplified equations: 
\begin{align*}
\begin{split}
A(1-x-z^2) &= 1 + B(x +xz) + C(y+xy+y^2z+xz)\\
B(1-z^2) &= A(x+yz)+ C(xz+yz^2)\\
C(1-x^2-xyz-z^2) & = A(y+xz)+B(y+xz).
\end{split}
\end{align*}

Ultimately, it is only necessary to solve for $A(x,y,z)$, as this represents all tilings that begin with the vertical profile. Thus, \[A(x, y, z) = \frac{U}{V}\] where $U = 1-x-yz-z^2$, and \begin{align*}
V = & 1+ x^2yz-x^2z^2-y^3z-y^2z^2+yz^3+z^4+x^3-xy^2-3xyz+2xz^2\\&-y^2-yz-2z^2-2x\end{align*}
As our ultimate goal is to create a generating function for a recursion which counts the number of painted tilings for a $2\times n$ board, we need our function to account for the length of our board, $n$. To do this, we first replace $x$ by $bu^2$, $y$ by $au$, and $z$ by $cu^3$. Now, the power of $u$ will account for the number of `spaces' on the board the tile occupies. The total number of spaces in a $2\times n$ board is $2n$, so the coefficient of $u^{2n}$ will count the number of tilings of this board. Thus, every power of $u$ will be even, so we can replace $u^2$ by $t$, where the power of $t$ will now correspond to the length of the board, $n$. 

This produces the generating function 
\[A(a,b,c,t) = \frac{U}{V}\] where $U = 1-bt-act^2-c^2t^3$, and \begin{align}\label{eq:ts}
\begin{split}
V = & 1 -(a^2 +2b)t - (a^2b+ac)t^2 - (a^3c-b^3+3abc+2c^2)t^3 \\
&- (a^2c^2-ab^2c-2bc^2)t^4-(b^2c^2-ac^3)t^5+c^4t^6.
\end{split}
\end{align} 
We will use the notation $V= 1- V'$, where $V'$ is the polynomial in $a, b,c$ and $t$ as above. 

The resulting coefficient of $t^{n}$ from this generating function, which will be a polynomial in terms of $a,b$ and $c$, is the number of \textit{painted} tilings of a $2 \times n$ board  with $a$ available colors of squares, $b$ available colors of dominoes, and $c$ available colors of trominoes. Further, the coefficient of $a^k b^l c^j t^{n}$ reflects the number of (unpainted) tilings of a $2 \times n$ board  using precisely $k$ squares, $l$ dominoes, and $j$ trominoes where $2n = 3j+2l+k$. 

Using a similar procedure to Read \cite[pp.~55--56]{r82}, we can obtain a recurrence relation from Equation~\eqref{eq:ts}. Let $s_n(a, b, c)$ denote the polynomial corresponding to the number of possible placements of $a$ squares, $b$ dominoes, and $c$ trominoes on a $2 \times n$ board. Then
\[ A(a, b, c,t)=\sum s_n(a, b, c)t^n\]
and from Equation~\eqref{eq:ts} we obtain
\[\sum s_n(a, b, c)t^n = \frac{1-bt-act^2-c^2t^3}{V}.\]
By multiplying both sides by $V$, we obtain 
\[ (1-V')\sum s_n(a, b, c)t^n = 1-bt-act^2-c^2t^3,\] which we can use to solve for the coefficients $s_n(a,b,c)$: 
\[ \sum s_n(a, b, c)t^n = (1-bt-act^2-c^2t^3)+V'\sum s_n(a, b, c)t^n.\]

For $n\geq 4$, the right-hand side of this equation will give a recursive definition for the coefficient of $t^n$. We can distribute $V'$ over the sum $\sum s_n(a, b, c)t^n$ (denoted below as $\sum s_n t^n$) and re-index as follows:
\begin{align*} \sum_{n\geq 4} s_n t^n &= (a^2+2b)t\sum_{N\geq 3} s_N t^N + (a^2b+ac)t^2\sum_{N\geq 2} s_N t^N + \cdots +c^4t^6\sum_{N\geq -2} s_N t^N \\
& = (a^2+2b)\sum_{n\geq 4} s_{n-1}t^{n} +\cdots +c^4\sum_{n\geq 4} s_{n-6} t^n
, \end{align*}
where $s_n(a,b,c):= 0 $ for all  $n\leq 0$. 
By gathering the coefficients of $t^n$, we obtain the following expression for $s_n(a,b,c)$:  
\begin{align*}s_n(a,b,c) &= (a^2+2b)s_{n-1}(a,b,c)+(a^2b+ac)s_{n-2}(a,b,c)+(a^3c+3abc-b^3+2c^2)s_{n-3}(a,b,c)\\ &+(a^2c^2-ab^2c-2bc^2)s_{n-4}(a,b,c)+(b^2c^2-ac^3)s_{n-5}(a,b,c)-c^4s_{n-6}(a,b,c).
\end{align*}

A case-by-case analysis gives the initial conditions in the theorem. 
\end{proof} 

A classic question on the topic of tilings of rectangular boards is to
ask how many ways there are to tile a $2\times n$ board using
trominoes, dominoes, and squares of a single color. To obtain this
result, we can simply evaluate the recurrence relation from
Theorem~\ref{thm:tromino} at $a, b, c = 1$.

\begin{corollary} \label{tromino cor} The recurrence relation for tilings of a $2\times n$ board with squares, dominoes, and trominoes is \[ S_n=3S_{n-1}+2S_{n-2}+5S_{n-3}-2S_{n-4}-S_{n-6},\]
with initial conditions
\[ S_0=1, S_1 = 2, S_2 = 7, S_3 = 29, S_4=109.\]
\end{corollary}

\begin{remark} 
The sequence in Corollary~\ref{tromino cor} is sequence \seqnum{A278815} in the OEIS. 
\end{remark} 

\section{A recurrence relation for $3\times n$ boards}
\label{sec:3byn}
Now that we have seen an example of Read's method applied to the case
of painted squares, dominoes, and trominoes, we return to the original
question of counting the number of tilings of a $3\times n$ board with
only painted squares and dominoes. For the sake of space, we refer to
``The dimer problem for narrow rectangular arrays''  for the profiles
in the $3\times n$ case, and for the profile equations 
\cite[Fig.~5 and Eq.~(3.1)]{r82}.

Using the same notation as in Section~\ref{sec:coverings}, $A(x,t)$
denotes the generating function for the number of tilings of a $3\times
n$ board with squares and dominoes, where the power of $x$ corresponds
to the number of dominoes and the power of $t$ corresponds to the width
of the rectangle, $n$. The following result is by Read \cite{r82}.

\begin{theorem}[Read, 1982] \label{Read}
The generating function for tilings of a $3\times n$ board with squares and dominoes is 
\[ A(x,t)=\frac{(1-2xt-x^3t^2)(1+xt-x^3t^2)}{V}, \] where 
\[ V=1-(1+3x)t-(2x+7x^2+5x^3)t^2 - (x^2+x^3-2x^4)t^3+(2x^4+3x^5+5x^6)t^4-(x^6-x^7)t^5-x^9t^6. \]
The recurrence for $P_n$ is
\[ P_n=4P_{n-1}+14P_{n-2}-10P_{n-4}+P_{n-6},\]
with initial conditions
\[ P_0=1, P_1=3, P_2=22, P_3=823, P_4=5096.\]
\end{theorem} 



We include Theorem~\ref{Read} \cite[pp.~55--56]{r82} to provide comparison with the result for painted tilings which we give below. The recurrence given by Read \cite{r82} has a parameter $x$ whose exponent denotes the number of dominoes in the tiling. To obtain the simple recurrence in Theorem~\ref{Read} we substitute $x=1$. The sequence defined by this recurrence is \seqnum{A033506}. 

Let $\tau_n^{a,b}$ be the number of ways to tile a $3\times n$ board with painted squares and dominoes, where there are $a$ available colors for each square, and $b$ available colors for each domino. 

\begin{theorem}\label{recursion3}

The following recurrence relation holds for $n\geq 5$: 
\begin{align*} \tau_{n}^{a,b}=& (a^3+3ab)\tau_{n-1}^{a,b}+(2a^4b+7a^2b^2+5b^3)\tau_{n-2}^{a,b} + \\ &(a^5b^2+a^3b^3-2ab^4)\tau_{n-3}^{a,b} - (2a^4b^4+3a^2b^5+5b^6)\tau_{n-4}^{a,b} + \\ & (a^3b^6 - ab^7)\tau_{n-5}^{a,b} + b^9\tau_{n-6}^{a,b},\end{align*}
with the following initial conditions: 
\begin{align*}
\tau_{-1}^{a,b} &:=0 \\
\tau_{0}^{a,b} & =1 \\
\tau_{1}^{a,b} & = a^3+2ab \\
\tau_{2}^{a,b} & = a^6 + 7a^4b + 11a^2b^2 + 3b^3 \\
\tau_3^{a,b} & = a^9+12a^7b+44a^5b^2+56a^3b^3+18ab^4 \\
\tau_4^{a,b} & = a^{12}+17a^{10}b + 102a^8b^2+267a^6b^3 + 302a^4b^4+123a^2b^5+11b^6.
\end{align*} 

\end{theorem}

\begin{proof}
Using Read's equation \cite[Eq.~(3.5)]{r82}, we modify the change of variable procedure to account for $a$ available square colors and $b$ available domino colors with similar reasoning to that used in Theorem~\ref{thm:tromino}.  Replacing $x$ by $bu^2$ and $y$ by $au$, and then $u^3$ by $t$, we obtain 
\begin{equation} A(a,b,t) = \frac{U}{V}, 
\label{eq:threen} \end{equation} where $U=(1-b^3t^2 - 2abt)(1-b^3t^2+abt)$, and 
\begin{align*} 
V = & 1-t(a^3+3ab)-t^2(2a^4b+7a^2b^2+5b^3) - t^3(a^5b^2+a^3b^3 - 2ab^4) + \\
&  t^4(2a^4b^4+3a^2b^5+5b^6) - t^5(a^3b^6 - ab^7)-t^6b^9. 
\end{align*}

Denote $V$ by $1-V'$.

Equation~\eqref{eq:threen} is a generating function where the coefficient of $t^n$ is the number of tilings of a $3\times n$ board with squares and dominoes, with $a$ available colors of squares and $b$ available colors of dominoes.  

Solving for the coefficient of $t^n$ in Equation~\eqref{eq:threen} will result in the desired recursion for $\tau_n^{a,b}$.

Using a method analogous to the proof of Theorem~\ref{thm:tromino}, we  write $A(a,b, t)=\sum_{n\geq 0} \tau_n(a,b)t^n$ so that Equation~\eqref{eq:threen} becomes 
\[ \sum_{n\geq 0} \tau_n(a,b)t^n= \frac{U}{V}.\]  Therefore, multiplying both sides by $V$ and solving for $ \sum_{n\geq 0} \tau_n(a,b)t^n$, we obtain
\[ \sum_{n\geq 0} \tau_n(a,b)t^n= U + V'\left( \sum_{n\geq 0} \tau_n(a,b)t^n\right). \]

Since we seek a recursive expression for $\tau_n(a,b)$,  we will focus on $n\geq 5$, where the terms $V'\sum \tau_n(a,b)t^n$ appear. 
 
As in the proof of Theorem~\ref{thm:tromino}, by distributing $V'$ and gathering coefficients of $t^n$ on the right-hand side, we obtain the following recursion: 
 
 \begin{align*} \tau_{n}(a,b)=& (a^3+3ab)\tau_{n-1}(a,b)+(2a^4b+7a^2b^2+5b^3)\tau_{n-2}(a,b) + \\ &(a^5b^2+a^3b^3-2ab^4)\tau_{n-3}(a,b) - (2a^4b^4+3a^2b^5+5b^6)\tau_{n-4}(a,b) + \\ & (a^3b^6 - ab^7)\tau_{n-5}(a,b) + b^9\tau_{n-6}(a,b).
 \end{align*}

The initial conditions for the recurrence relation are calculated using case-by-case analysis.  
\end{proof} 

While the method in this section is useful to obtain an explicit
recursion for $\tau_n^{a,b}$, a different approach introduced by Ahrens
\cite{a81} gives a way to calculate the number of tilings for
\textit{any} rectangular array of dimensions $m\times n$. (Although it
does not give a single closed-form expression for all $m, n$.)  In the
next section we generalize the work of Ahrens to include the parameters
$a$ and $b$. However, the subsequent technique cannot be used to obtain
the  results in Section~\ref{sec:coverings} on tilings with squares,
dominoes, and trominoes. A more detailed contrast of the two
enumeration methods  will be discussed in Section~\ref{sec:transfer}.

\section{Tilings of $m\times n$ boards using transfer matrices} 
\label{sec:transfer}
While the approach in the previous section considered building tilings horizontally using `profiles', the techniques in this section will build tilings vertically. Of course, the number of tilings of a $3\times n$ board will be the same as the number for an $m\times 3$ board when $m=n$, so we will interchange the  fixed dimension for the rectangular boards in this section. 

Consider a square-domino tiling of an $m\times n$ board. If a position is covered by a domino, place a 1 in that position, otherwise place a 0. Notice that the bottom row of the board can be any of the $2^n$ length-$n$ binary vectors. For a given board, call the binary vector in the bottom row the \textit{(binary) signature} of the tiling. We will see that multiple different tilings may correspond to a particular binary signature. For a natural number $i$, let $i_{b}$ denote the binary representation of $i$. 


As an example, Figure~\ref{fig:signatures} gives all tilings of a $2\times 3$ board with squares and dominoes that have signature $i=7$, i.e., $i_b = 111$. 
\begin{figure}[h!]
\includegraphics[scale=0.6]{signature.eps}
\centering
\caption{The five $2\times 3$ tilings with signature $i=7$.}
\label{fig:signatures}
\end{figure}



Ahrens defines a \textit{transfer matrix} to be a $2^n \times 2^n$ matrix containing entries $a_{i,j}$, where $a_{i,j}$ counts the number of ways that an $m\times n$ tiling with binary signature $i_b$ can become an $(m+1)\times n$ tiling with binary signature $j_b$ by the addition of squares or  dominoes in the final row \cite{a81}. In this process, we consider  a square to be an `empty' space, so a square in row $m$ can be covered by a domino that spans from row $m$ to row $m+1$ in the extended tiling.  The transfer matrix that Ahrens produces  \cite{a81} has entries in $\mathbb{Z}^{+}$. 

We extend this method to count the number of \textit{painted} tilings of $m\times n$ boards where there are $a$ colors for squares and $b$ colors available for dominoes. Therefore the new transfer matrix will have entries that are expressions in $a$ and $b$. We use a similar approach to Ahrens, but we take into account the number of squares and dominoes that need to be placed in each case, so that $a_{i,j}$ becomes the number of ways that a painted  tiling with signature  $i_b$ can become a tiling with signature $j_b$ by a placement of \textit{painted} squares and dominoes, where there are $a$ possible colors of squares and $b$ possible colors of dominoes. 

For example, consider the entry $a_{7,0}$ in the $8\times 8$ transfer matrix for $m\times 3$ tilings. For each of the tilings in Figure~\ref{fig:signatures}, there is one way to extend to a $3\times 3$ tiling with signature $j=0$ ($j_b=000$) using unpainted squares and dominoes. These extensions are shown in Figure~\ref{fig:extend}. Since each square placed in the third row has $a$ possible colors, there are $a^3$ ways to extend a  $2\times 3$ painted tiling with signature 7 to a  $3\times 3$ painted tiling with signature 0. Therefore $a_{7,0}=a^3$. 

\begin{figure}[h!]
\includegraphics[scale=0.6]{extend.eps}
\centering
\caption{Extending $2\times 3$ tilings with a signature of 7  to  $3\times 3$ tilings with a signature of 0. }
\label{fig:extend}
\end{figure}

The preceding example demonstrates how to find a single entry of the
transfer matrix in the $m\times 3$ case, but the entire $8$-by-$8$
transfer matrix can be obtained by applying a recursive procedure to
the $m\times 1$ and $m\times 2$ matrices. Thus, we show how to
construct these smaller matrices first and then use them to recursively
build the $m\times 3$ transfer matrix.

Let $A_n$ denote the transfer matrix for $m\times n$ boards. The $m\times 1$ transfer matrix is 
\[ A_1 = \begin{bmatrix}
a & \frac{b}{a} \\
a & 0 
\end{bmatrix}. \]

Since the $(i,j)^{th}$ entry of the matrix is the number of ways to extend an $(m-1)\times 1$ tiling with signature $i$ to an $m\times 1$ tiling with signature $j$, we see that $a_{0,0}=a$, since there are $a$ colors available for the additional square. Similarly, a tiling that has signature $1$ can be extended to one with signature 0 by adding a square, so $a_{0,1}=a$ as well. On the other hand, we would need to place a domino vertically to turn a 0 signature into a 1, and the vertical domino would cover what was previously a square, so $a_{0,1}=\frac{b}{a}$. Finally, there is no way to place a domino in a single space on an $(m-1)\times 1$ tiling that has signature 1 to extend it to an $m\times 1$ tiling with signature 1.  Therefore $a_{1,1}=0$. 


 Figure~\ref{fig:transfermatrix} 
 demonstrates how to find each entry of the $m\times 2$ transfer matrix, using an arbitrary tiling with signature $i$ for each $i=0, 1, 2, 3$. The transfer matrix entry $a_{0,3}$ is $b+\frac{b^2}{a^2}$ because there are two ways to obtain a signature of $3$ by extending a tiling with signature $0$: the way pictured in Figure~\ref{fig:transfermatrix}, which contributes the term $b$,  or by covering both squares by vertically-placed dominoes. Since each domino has $b$ possible colors, and they are covering two squares that have $a$ possible colors each, the resulting count is $\frac{b^2}{a^2}$. 

\begin{figure}[h!]
\includegraphics[scale=0.25]{transfer-2by2.eps}
\centering
\caption{Images illustrating the entries $a_{i,j}$ for the $m\times 2$-board transfer matrix. }
\label{fig:transfermatrix}
\end{figure}

The transfer matrix for $m\times 2$ painted tilings is given below: 
\[A_2=\begin{bmatrix}
a^2 & b & b& b+\frac{b^2}{a^2} \\
a^2 & 0 & b & b \\
a^2 & b & 0 & b \\
a^2 & 0 & 0 & b 
\end{bmatrix}. \]


\subsection{Recursive construction of the transfer matrix}

The $2^n\times 2^n$ transfer matrix that describes the transitions from
an $(m-1)\times n$ board to an $m\times n$ board can be constructed
recursively from the $2^i\times 2^i$ transfer matrices for $i<n$. In
Table~\ref{table:transfer} we provide a key to this recursive
construction. This is a generalization of the process detailed 
in Ahrens \cite[p.~279]{a81}. Throughout this subsection we use $i$ for
the binary representation of the integer $i$, instead of  $i_b$.

Let $i'$ denote the binary representation of $i$, truncated on the last bit. For example, if $i=1001$, then $i'=100$. Similarly, let $i''$ denote the binary representation of $i$ truncated on the last two bits. 



\begin{table}[h!]
\centering
\label{table:transfer}
\begin{tabular}{|l|l|l|l|l|}
\hline
$i$/$j$             & $j\equiv 0$ (mod 4)      & $j\equiv1$ (mod 4)                 & $j\equiv 2 $ (mod 4)     & $j\equiv 3$ (mod 4)                            \\ \hline
$i\equiv 0$ (mod 2) & $a_{ij}=a\cdot a_{i'j'}$ & $a_{ij}=\frac{b}{a}\cdot a_{i'j'}$ & $a_{ij}=a\cdot a_{i'j'}$  & $a_{ij}=\frac{b}{a}a_{i'j'}+b\cdot a_{i''j''}$ \\ \hline
$i\equiv 1$ (mod 2) & $a_{ij}=a\cdot a_{i'j'}$ & 0                                  & $a_{ij}=a\cdot a_{i'j'}$ & $a_{ij}=b\cdot a_{i''j''}$                     \\ \hline
\end{tabular}
\caption{Transfer matrix construction}
\end{table}



Recall that $a$ is the number of available colors for squares, and $b$
is the number of available colors for dominoes, while $a_{ij}$ is the
number of ways to extend a tiling with signature $i$ to one with
signature $j$ by adding a new row.  Table~\ref{table:transfer} states
that when $i\equiv 0\pmod{2}$ and $j\equiv 0\pmod{4}$, that
$a_{ij}=a\cdot a_{i'j'}$.  Given that $i\equiv 0\pmod{2}$, we have that
$i=i'0$ and similarly $j=j'0$. Therefore any  extension of $i'$ to $j'$
can be turned into an extension of $i$ to $j$ by placing a square (of
which there are $a$ color options) in the lower right corner of the
$i$-to-$j$ extension. Therefore the number of ways to extend $i$ to $j$
is $a$ times the number of ways to extend $i'$ to $j'$.

The remaining entries can be calculated in a similar way. We will explain the case of $i\equiv 0\pmod{2}$, $j\equiv 3\pmod{4}$ since it also requires the term $a_{i''j''}$. 

Since $j\equiv 3\pmod{4}$, the binary representation of $j$ ends in $11$. There are two ways to obtain an ending of $11$ in $j$, given that $i$ ends in $0$---either have (i) a vertical domino that ends in the  last position of $j$, or (ii) a horizontal domino that ends in the last position of $j$. 
 
Case (i) can occur in $\frac{b}{a}a_{i'j'} $ ways, since we can cover the final 0 (square) in $i$ with a vertical domino to obtain the final 1 in $j$. There are $\frac{b}{a}$ ways to complete this extension of the last position of $i$ to the last position of $j$. The remaining positions are accounted for by the term $a_{i'j'}$, which counts the ways to extend a tiling with signature $i'$ to one with signature $j'$. Therefore there are a total of $\frac{b}{a}a_{i'j'} $ ways. 

Case (ii) can occur in $b\cdot a_{i''j''}$ ways. Placing a horizontal domino in the final two positions to form binary signature $j$ can be done in $b$ ways. This horizontal domino can be added to any method of extending $i''$ to $j''$, so we obtain $b\cdot a_{i''j''}$. 







\subsection{Enumeration using the transfer matrix}
Using the recursive construction described in the previous section, we obtain $A_3$, the transfer matrix for $m\times 3$ rectangular boards: 

$$A_3=\left[ \begin{array}{ccccccccc}     
    a^3 & ab & ab & \frac{b^2}{a} + ab & ab & \frac{b^2}{a} & \frac{b^2}{a} + ab  & \frac{b^3}{a^3} + 2\frac{b^2}{a}\\
    a^3 & 0 & ab & ab & ab & 0 & \frac{b^2}{a} + ab  & \frac{b^2}{a}\\
    a^3 & ab & 0 & ab & ab & \frac{b^2}{a} & ab  & 2\frac{b^2}{a}\\
    a^3 & 0 & 0 & ab & ab & 0 & ab  & \frac{b^2}{a}\\
    a^3 & ab & ab & \frac{b^2}{a} + ab & 0 & 0 &  ab  & \frac{b^2}{a}\\
    a^3 & 0 & ab & ab & 0 & 0 & ab  & 0\\
    a^3 & ab & 0 & ab & 0 & 0 & ab  & \frac{b^2}{a}\\
    a^3 & 0 & 0 & ab & 0 & 0 & ab  & 0\\
\end{array} \right].$$


To calculate the number of painted tilings of a $3\times 3$ board, for example, take the sum of the entries in the vector  $v^{(0)}(A_3)^3$, where $v^{(0)}=(0,0, 0,0 ,0,0 ,0,1)$. The vector $v^{(0)}$ describes the number of tilings of a $0\times 3$ board, which we define to be 1. In general, the $i^{th}$ entry of the vector $v^{(m)}$,  $v^{(m)}_i$, denotes the number of tilings of an $m\times 3$ board with signature $i$. We define $v^{(0)}_7 = 1$, since any $1\times 3$ tiling can be viewed as an extension of the unique $0\times 3$ board, where no vertical dominoes are allowed. The rest of the entries of $v^{(0)}$ are 0 since if we declared any other entry to be $1$, we would be allowing  vertical dominoes in a $1\times 3$ board.





For an $m\times 3$ board, the number of ways to tile it with painted squares and dominoes is the sum of entries in the vector $v^{(m)}$, which can be calculated by  

\begin{equation}\label{eq:A3} v^{(m)}=v^{(0)}(A_3)^m.\end{equation} 

More generally, let $A_n$ be the transfer matrix for an $m\times n$ board, obtained recursively. The number of ways to tile an $m\times n$ board with painted squares and dominoes is the sum of the entries of $v^{(m)}$, where 
\[ v^{(m)}=v^{(0)}(A_n)^m.\]

(As above, the vector $v^{(0)}$ is an $(1\times 2^n)$-vector composed of all zeroes, except for a 1 in the last position.) The construction of the transfer matrix $A_n$ guarantees that the product $v^{(0)}A_n$ gives the number of ways to tile an $1\times n$ board with painted squares and dominoes. Again, the $i$th component of the vector $v^{(0)}A_n$ is the number of such tilings with binary signature $i$. Multiplying by the transfer matrix a second time gives the number of tilings of a $2\times n$ board. Thus,  repeated application of this process shows that $ v^{(m)}=v^{(0)}(A_n)^m$. 

Ahrens \cite{a81} provides an algorithm  to speed up the computation time for the expression above, and we note that the algorithm could be adjusted in a straightforward way for the colorful tiling case. 

Using \ref{eq:A3}, determining the number of painted tilings of an $m\times 3$, or equivalently a $3\times n$ board, is computationally straightforward. For instance, using $A_3$ as defined previously, we can easily calculate the number of tilings of a $3 \times 2$ board:  
\begin{align*}
v^{(2)}&=v^{(0)}(A_3)^2\\
&=\left[\begin{array}{cccccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{array} \right]\left[ \begin{array}{ccccccccc}     
    a^3 & ab & ab & \frac{b^2}{a} + ab & ab & \frac{b^2}{a} & \frac{b^2}{a} + ab  & \frac{b^3}{a^3} + 2\frac{b^2}{a}\\
    a^3 & 0 & ab & ab & ab & 0 & \frac{b^2}{a} + ab  & \frac{b^2}{a}\\
    a^3 & ab & 0 & ab & ab & \frac{b^2}{a} & ab  & 2\frac{b^2}{a}\\
    a^3 & 0 & 0 & ab & ab & 0 & ab  & \frac{b^2}{a}\\
    a^3 & ab & ab & \frac{b^2}{a} + ab & 0 & 0 &  ab  & \frac{b^2}{a}\\
    a^3 & 0 & ab & ab & 0 & 0 & ab  & 0\\
    a^3 & ab & 0 & ab & 0 & 0 & ab  & \frac{b^2}{a}\\
    a^3 & 0 & 0 & ab & 0 & 0 & ab  & 0\\
\end{array} \right]^2\\
&=\left[\begin{array}{cccccccccc}
a^3 & 0 & 0 & ab & 0 & 0 & ab  & 0
\end{array} \right]\left[ \begin{array}{ccccccccc}     
    a^3 & ab & ab & \frac{b^2}{a} + ab & ab & \frac{b^2}{a} & \frac{b^2}{a} + ab  & \frac{b^3}{a^3} + 2\frac{b^2}{a}\\
    a^3 & 0 & ab & ab & ab & 0 & \frac{b^2}{a} + ab  & \frac{b^2}{a}\\
    a^3 & ab & 0 & ab & ab & \frac{b^2}{a} & ab  & 2\frac{b^2}{a}\\
    a^3 & 0 & 0 & ab & ab & 0 & ab  & \frac{b^2}{a}\\
    a^3 & ab & ab & \frac{b^2}{a} + ab & 0 & 0 &  ab  & \frac{b^2}{a}\\
    a^3 & 0 & ab & ab & 0 & 0 & ab  & 0\\
    a^3 & ab & 0 & ab & 0 & 0 & ab  & \frac{b^2}{a}\\
    a^3 & 0 & 0 & ab & 0 & 0 & ab  & 0\\
\end{array} \right]\\
&=\left[\begin{array}{cccccccccc}
a^6+2a^4b \\ a^4b+a^2b^2 \\ a^4b \\ a^3(\frac{b^2}{a}+ab)+2a^2b^2 \\ a^4b+a^2b^2 \\ a^2b^2 \\ a^3(\frac{b^2}{a}+ab)+2a^2b^2 \\ a^3(\frac{b^3}{a^3}+\frac{2b^2}{a})+2b^3
\end{array} \right]^\mathsf{T} .
\end{align*}

By taking the sum of the entries of $v^{(2)}$ and combining like terms, we find that the number of painted tilings of a $3 \times 2$ board with $a$ available colors of squares and $b$ available colors of dominoes is $a^6+7a^4b+11a^2b^2+3b^3$, which agrees from the result derived in Theorem~\ref{recursion3}. 

We can similarly use this procedure to determine that there are $a^9+12a^7b+44a^5b^2+56a^3b^3+18ab^4$ painted tilings of a $3\times 3$ board and $a^{12}+17a^{10}b+102a^8b^2+267a^6b^3+302a^4b^4+123a^2b^5+11b^6$ painted tilings of a $3\times 4$ board with $a$ available colors of squares and $b$ available colors of dominoes.

\section{Conclusion} 

Although the transfer matrix approach gives a powerful tool for counting the number of colorful tilings of $m\times n$ arrays, the method is does not immediately generalize to other types of tilings. For example, in Section~\ref{sec:coverings} we counted the number of painted tilings for squares, dominoes, and trominoes, and there is no current tromino generalization of the signature definition or of the transfer matrix construction. Read also mentions this drawback while contrasting the profile approach with the transfer matrix method \cite{r82}. However, the advantage of the transfer matrix approach is that it offers a procedure for recursively constructing new transfer matrices, meaning we can find the number of painted tilings of each consecutively larger $m$.  

Alternatively, the generalization of Read's method presented in this paper has the advantage of producing a recurrence relation, thereby describing the entire sequence of possible painted tilings for a particular $m$. Moreover, this approach is extremely flexible in that it can be easily modified to consider tilings of different sizes, not just squares, dominoes, and trominoes. However, for each new value of $n$ examined, Read's method requires reworking the entire process from the beginning and little work from prior cases can be reused. Further, as $n$ increases, the number of possible profiles increases rapidly, making the system prohibitively complex to solve. Consequently, given specific values of $m$ and $n$, assuming these values are not overly large, the transfer matrix method will calculate the number of tilings with painted squares and dominoes more efficiently.

Possible topics of future research could include determining asymptotic behavior \cite{a81}, or finding recursions for tilings that include $L$-trominoes as well as $I$-trominoes. 
In addition, we believe it could be possible to  modify the transfer matrix method to account for tilings using ($I$-) trominoes. Such a modification might require signatures from the bottom two rows, and would potentially produce a $2^{2^n} \times 2^{2^n}$ transfer matrix. There are also related questions about colorful tilings of boards of different shapes (such as the Aztec Diamond shape), where the methods developed in this paper may be applied. Finally, we note that a natural generalization of colorful tilings is to have constraints on the number of tiles available for certain colors. The enumeration would then depend on these additional parameters.

\begin{thebibliography}{99}
\bibitem{a81} J. H. Ahrens, Paving the chessboard, \textit{J.
Combin. Theory Ser. A} \textbf{31} (1981), 277--288.

\bibitem{bos01} I. Beichl, D. P. O'Leary, and F. Sullivan,
Approximating the number of monomer-dimer coverings in periodic
lattices, \textit{Phys. Review E} \textbf{64} (2001), 1--6.

\bibitem{erw11} A. Erickson, F. Ruskey, and J. Woodcock, Monomer-dimer
tatami tilings of rectangular regions, \textit{Electronic J.
Combin.} \textbf{18} (2011), \#P109.

\bibitem{g74} R. Grimson, Exact formulas for 2-by-$n$ arrays of
dumbbells, \textit{J. Math. Phys.} \textbf{15} (1974),
214--216.

\bibitem{hm84} J. Hock and R. McQuistan, A note on the occupational
degeneracy for dimers on a saturated two-dimensional lattice space,
\textit{Disc. Appl. Math.} \textbf{8} (1984), 101--104.

\bibitem{hm85} H. Hosoya and A. Motoyama, An effective algorithm for
obtaining polynomials for dimer statistics, \textit{J.
Math. Phys.} \textbf{26} (1985), 157--167.

\bibitem{j87} M. Jerrum, Two-dimensional monomer-dimer systems are
computationally intractable, \textit{J. Stat. Phys.}
\textbf{48} (1987), 121--134.

\bibitem{ks09} M. Katz and C. Stenson, Tiling a $(2\times n)$-board
with squares and dominoes, \textit{J. Integer Sequences}
\textbf{12} (2009), \href{https://cs.uwaterloo.ca/journals/JIS/VOL12/Stenson/stenson8.html}{Article 09.2.2}.

\bibitem{ml70} R. B. McQuistan and S. J. Lichtman, Exact recursion
relation for 2-by-$N$ arrays of dumbbells, \textit{J.
Math. Phys.} \textbf{11} (1970), 3095--3099.

\bibitem{r82} R. Read, The dimer problem for narrow rectangular arrays:
A unified method of solution, and some extensions, \textit{Aequationes
Math.} \textbf{24} (1982), 47--65.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 05B45; Secondary 05A15, 52C20.

\noindent \emph{Keywords: } domino, tiling, $I$-tromino, transfer matrix.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A030186},
\seqnum{A033506}, and
\seqnum{A278815}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 6 2016;
revised version received April 11 2017. 
Published in {\it Journal of Integer Sequences}, June 24 2017.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                



.
