\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