\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[dvips]{epsfig} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \newtheorem{thm}{Theorem} \newtheorem{ID}{Identity} \newtheorem{lem}{Lemma} \newtheorem{prop}{Proposition} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Tiling a ($2 \times n$)-Board with Squares and Dominoes} \vskip 1cm \large Matt Katz\\ Pennsylvania State University\\ Mathematics Department\\ 109 McAllister Building\\ University Park, PA 16802\\ USA\\ \href{mailto:katz@math.psu.edu}{\tt katz@math.psu.edu}\\ \ \\ Catherine Stenson\footnote{All correspondence should be directed to this author.} \\ Juniata College \\ 1700 Moore Street\\ Huntingdon, PA 16652 \\ USA \\ \href{mailto:stenson@juniata.edu}{\tt stenson@juniata.edu}\\ \end{center} \vskip .2 in \begin{abstract} The Fibonacci numbers and the Pell numbers can be interpreted as the number of tilings of a ($1 \times n$)-board by colored squares and dominoes. We explore the tilings of ($2 \times n$)-boards by colored squares and dominoes. We develop a recurrence relation and prove several combinatorial identities in the style of recent work by Benjamin and Quinn. We also give a bijection between these ($2 \times n$)-tilings and a set of weighted ($1 \times n$)-tilings. \end{abstract} \begin{section}{Introduction} The Fibonacci numbers (\seqnum{A000045}) count the tilings of a ($1 \times n$)-board with dominoes and squares. Benjamin and Quinn \cite{PTRC} have used this interpretation to provide tiling proofs of many Fibonacci identities. The Pell numbers (\seqnum{A000129}) count the tilings of a ($1 \times n$)-board with dominoes and two colors of squares, and Benjamin, Plott, and Sellers \cite{Pell} used this interpretation to prove still more combinatorial identities. What if we expand the board--what can we say about tilings of a ($2 \times n$)-board by squares and dominoes? McQuistan and Lichtman \cite{McQ} studied such tilings in the context of placing dimers on a lattice. They found a recurrence relation and a generating function and looked at some statistical questions for large values of $n$. Grimson \cite{Grimson} studied the generating function for $q$ dominoes on a ($2 \times n$)-board. In Section 2, we generalize McQuistan and Lichtman's recurrence to tilings by $a$ colors of squares and $b$ colors of dominoes and give a direct combinatorial proof in the style of Benjamin and Quinn. In Section 3, we prove several combinatorial identities, and in Section 4, we provide a correspondence between these tilings and an equivalent set of weighted ($1 \times n$)-tilings. \end{section} \begin{section}{A Recurrence Relation} Let $k_n$ count the number of tilings of a $(2 \times n)$-board using $(1 \times 1)$ squares and $(1 \times 2)$ dominoes. The sequence (\seqnum{A030186} in the Online Encyclopedia of Integer Sequences \cite{intseq}) begins with $k_0=1$, $ k_1 = 2$, $ k_2 = 7$, and $k_3 = 22$. More generally, let $k_{n}^{a,b}$ be the number of tilings of a $(2 \times n)$-board using $a$ colors of squares and $b$ colors of dominoes. Below is a table of some values of $k^{a,b}_n$. \vspace{.25in} \begin{table}[h] $\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ \hline k_n & 1 & 2 & 7 & 22 & 71 & 228 & 733 & 2356 & 7573\\ \hline k^{2,3}_n & 1 & 7 & 82 & 877 & 9565 & 103960 & 1130701 & 12296275 & 133724242\\ \hline k^{4,2}_n & 1 & 18 & 392 & 8408 & 180560 & 3877120 & 83253056 & 1787684480 & 38386770432\\ \hline \end{array}$ \caption{Some values of $k_n$ and $k_n^{a,b}.$} \end{table} \vspace{.25in} McQuistan and Lichtman \cite{McQ} proved that for $n \geq 3$, \begin{eqnarray} k_n &=& 3k_{n-1} + k_{n-2} - k_{n-3}. \label{McQLrecur} \end{eqnarray} Their proof used repeated applications of other recurrence relations. Here we generalize their relation to $k_{n}^{a,b}$ and offer a more direct proof in the style of Benjamin and Quinn \cite{PTRC}. \begin{thm} \label{abrecur} Let $k^{a,b}_n$ count the number of tilings of a $(2 \times n)$-board with $a$ colors of squares and $b$ colors of dominoes. Then $k^{a,b}_{0}=1$, $k^{a,b}_{1} = a^{2} +b$, $k^{a,b}_{2} = a^{4}+ 4a^{2}b + 2b^{2}$, and, for $n \geq 3$, \begin{equation} k^{a,b}_n = (a^2 + 2b) k^{a,b}_{n-1} + a^2 b k^{a,b}_{n-2} - b^3 k^{a,b}_{n-3}. \end{equation} \end{thm} \begin{proof} First we verify the initial conditions. We define $k^{a,b}_{0}=1$. On a $(2 \times 1)$-board, there are $a^2$ tilings with two squares and $b$ tilings with one vertical domino, giving $k^{a,b}_{1} = a^{2} +b$. On a $(2 \times 2)$-board, there are $a^{4}$ tilings with four squares, $4a^{2}b$ tilings with two squares and one domino, and $2b^{2}$ tilings with two dominoes, giving $k^{a,b}_{2} = a^{4}+ 4a^{2}b + 2b^{2}$. Now we turn to the recurrence relation for $(2 \times n)$-boards, $n \geq 3$. There are $a^{2}k^{a,b}_{n-1}$ tilings of a $(2 \times n)$-board that end with two squares in column $n$ and $bk^{a,b}_{n-1}$ tilings that end with a vertical domino in column $n$. There are $a^{2}bk^{a,b}_{n-2}$ tilings that end with two squares in the top row and a horizontal domino in the bottom row. We need to show that the remaining tilings are counted by $bk^{a,b}_{n-1} -b^{3}k^{a,b}_{n-3}$. The tilings that remain to be counted are those ending in two horizontal dominoes, those ending with a horizontal domino in the top row and a square in the bottom row, and those ending with a horizontal domino in the bottom row, a square in column $n$ of the top row, and a horizontal domino in columns $n-2$ and $n-1$ of the top row. These endings can be seen below in Figure 1. \begin{figure}[H]\ \begin{center} \epsfig{file=proofendings_update.eps,scale=0.4} \caption{The endings counted by $bk^{a,b}_{n-1} -b^{3}k^{a,b}_{n-3}$.} \label{proofend} \end{center} \end{figure} We will show that the $(2 \times n)$-tilings with these endings correspond to certain $(2 \times (n-1))$-tilings. In particular, there are $b^2k_{n-3}^{a,b}$ tilings of a $(2 \times (n-1))$-board that end with two horizontal dominoes in the last two columns. So we need to show that each $(2 \times (n-1))$-tiling that does not end in two horizontal dominoes corresponds to $b$ tilings of a $(2 \times n)$-board that end as in Figure 1. A $(2 \times (n-1))$-tiling that does not end in two horizontal dominoes may end with a vertical domino, with a square in column $n-1$ of the top row, or with a horizontal domino in columns $n-2$ and $n-1$ of the top row and a square in column $n-1$ of the bottom row. If our $(2 \times (n-1))$-tiling ends in a vertical domino, create a $(2 \times n)$-tiling by turning the vertical domino into a horizontal domino in columns $n-1$ and $n$ of the bottom row and filling in columns $n-1$ and $n$ of the top row with any of the $b$ colors of dominoes. If our ($2 \times (n-1)$)-tiling ends with a square in column $n-1$ of the top row, create a $(2 \times n)$-tiling by moving the square to column $n$ of the bottom row and filling in columns $n-1$ and $n$ of the top row with any of the $b$ colors of dominoes. If our ($2 \times (n-1)$)-tiling ends with a horizontal domino in the top row and a square in the bottom row, create a $(2 \times n)$-tiling by moving the square to column $n$ of the top row and filling in columns $n-1$ and $n$ of the bottom row with any of the $b$ colors of dominoes. This mapping can be seen in Figure \ref{end2} below. \begin{figure}[H]\label{end2} \begin{center} \epsfig{file=proofendings2_update.eps,scale=0.5} \caption{Mapping $(2 \times (n-1))$-tilings to $(2 \times n)$-tilings.} \label{proofend2} \end{center} \end{figure} These one-to-$b$ mappings reverse to $b$-to-one mappings, and this correspondence completes the proof of (2). McQuistan and Lichtman's recurrence relation (1) is the special case $a=b=1$. \end{proof} Using standard methods (see, for example, Brualdi's discussion \cite[Chapter 7]{Brualdi}), we can find that the generating function for $k^{a,b}_n$ is \begin{eqnarray} G^{a,b}(x) = \frac{1-x}{1-(a^2 + 2b) x - a^2 b x^2 + b^3 x^3}. \end{eqnarray} \end{section} \begin{section}{Combinatorial Identities} The tilings of a $(1 \times n)$-board by squares and dominoes are counted by the Fibonacci number usually denoted $F_{n+1}$, with $F_{0}=0$ and $F_{1}=1$. Because we would like our subscript to match our board size, we follow the notation of Benjamin and Quinn \cite{PTRC} and define $f_{n} = F_{n+1}$, with $f_{0}=1$, $f_{1}=1$, and $f_{n}=f_{n-1} + f_{n-2}$. We also note that $f_{n} = k_{n}^{0,1}$; that is, $f_n$ counts the tilings of a $(2 \times n)$-board by dominoes. To see this, notice that the top row of a $(2 \times n)$-tiling by dominoes is just a $(1 \times n)$-tiling by dominoes and squares, and that the top row of a $(2 \times n)$-tiling by dominoes completely determines the bottom row. In this case, equation (\ref{McQLrecur}) becomes the Fibonacci identity $f_{n} = 2f_{n-1} + f_{n-3}$. Because of these connections, we expect that many Fibonacci-style identities will apply to $(2 \times n)$-tilings. To prove some of these identities, we need the notion of breakability. We say that a tiling of a $(2 \times n)$-board is {\it breakable} at column $m$ ($1 \leq m \leq n-1$) if it can be separated into a tiling of a $(2 \times m)$-board and a tiling of a $(2 \times (n-m))$-board. A tiling is {\it unbreakable} if it is not breakable at any column. First we consider the case $a=b=1$. Both tilings of a $(2 \times 1)$-board are unbreakable, and three of the tilings of a $(2 \times 2)$-board are unbreakable (the ones with at least one horizontal domino). For $n \geq 3$, there are two unbreakable $(2 \times n)$ tilings, each consisting of $n-1$ staggered horizontal dominoes and one square in the first column and one square in the last column. See Figure \ref{stagger}. If $n$ is even, the two squares will be in the same row, and if $n$ is odd, they will be in different rows. \begin{figure}[H]\label{stagger} \begin{center} \epsfig{file=stagger2.eps,scale=0.3} \caption{The two unbreakable tilings of length 8.} \end{center} \end{figure} In the general case of $a$ colors of squares and $b$ colors of dominoes, there are $a^2 + b$ unbreakable tilings of a $(2 \times 1)$-board, $2a^{2}b + b^2$ unbreakable tilings of a $(2 \times 2)$-board, and $2a^{2}b^{n-1}$ unbreakable tilings of a $(2 \times n)$-board for $n \geq 3$. We now offer several identities with proofs using breakability. The first generalizes the usual Fibonacci recurrence. \begin{ID} \begin{eqnarray*} (i) &&k_n = 2k_{n-1} + 3k_{n-2} + 2 \sum_{i=0}^{n-3} k_{i}.\\ (ii) &&k^{a,b}_n = (a^2 + b) k^{a,b}_{n-1} + (2a^{2}b + b^2) k^{a,b}_{n-2} + 2 a^2 \sum_{i=0}^{n-3} b^{n-i-1} k^{a,b}_{i}. \end{eqnarray*} \end{ID} \begin{proof} We prove statement (\textit{ii}) by conditioning on the location of the rightmost break; statement (\textit{i}) is just the case $a=1$, $b=1$. Say this break occurs at column $i$; we allow $i=0$ if the tiling is unbreakable. The tiling begins with one of the $k_{i}^{a,b}$ tilings of a $(2 \times i)$-board and ends with an unbreakable tiling of a $(2 \times (n-i))$-board. If $n-i=1$, there are $a^2 + b$ such unbreakable tilings. If $n-i=2$, there are $2a^{2}b + b^2$ unbreakable tilings. Finally, if $n-i \geq 3$, there are $2a^{2}b^{n-i-1}$ unbreakable tilings. \end{proof} In the special case $a=0$, $b=1$, identity (\textit{ii}) reduces to the Fibonacci recurrence $f_n = f_{n-1} + f_{n-2}$. Identity 1 (\textit{ii}) can be used to give an alternative proof of Theorem \ref{abrecur}: begin with the identity, add and subtract $bk_{n-1}^{a,b}$ on the right-hand side, use the identity again to expand $-bk_{n-1}^{a,b}$, and simplify. Benjamin and Quinn \cite {PTRC} prove the Fibonacci identity $f_{m+n} = f_m f_n +f_{m-1} f_{n-1}$ by considering whether or not a tiling is breakable at column $m$. We use the same technique to prove the next identity. \begin{ID} For $m,n \geq 0$, \begin{eqnarray*} (i) &&k_{m+n} = k_m k_n + k_{m-1} k_{n-1} + 2 \sum_{i=0}^{m-1} \sum_{j=m+1}^{m+n} k_i k_{m+n-j}\\ (ii) &&k_{m+n}^{a,b} = k_m^{a,b} k_n^{a,b} + b^2 k_{m-1}^{a,b} k_{n-1}^{a,b} + 2 a^2 \sum_{i=0}^{m-1} \sum_{j=m+1}^{m+n} b^{j-i-1} k_i^{a,b} k_{m+n-j}^{a,b}. \end{eqnarray*} \end{ID} \begin{proof} We prove statement (\textit{ii}) here; statement (\textit{i}) is just the case $a=1$, $b=1$. There are $k_m^{a,b} k_n^{a,b}$ tilings of a $(2 \times (m+n))$-board that are breakable at column $m$. If a tiling is not breakable at column $m$, then look for the last break before column $m$ (say it occurs at column $i$) and the first break after column $m$ (say it occurs at column $j$). Then the tiling is breakable at columns $i$ and $j$ ($0 \leq i \leq m-1$, $m+1\leq j \leq m+n$) and unbreakable between these columns. We allow $i=0$ when the tiling has no breaks to the left of column $m$ and $j=m+n$ when the tiling has no breaks to the right of column $m$. When $i=m-1$ and $j=m+1$, there are $2a^{2}b + b^2$ possible unbreakable tilings of the two columns in between, and therefore there are $(2a^{2}b + b^2)k^{a,b}_{m-1}k_{n-1}^{a,b}$ tilings with these values of $i$ and $j$. For all other choices of $i$ and $j$, there are $2a^{2}b^{j-i-1}$ unbreakable tilings between columns $i$ and $j$, and therefore there are $2a^{2}b^{j-i-1}k_{i}^{a,b}k_{m+n-j}^{a,b}$ tilings with the chosen values of $i$ and $j$. We sum over all possible values of $i$ and $j$ to get the identity. If $a = 0$ and $b = 1$, identity (\textit{ii}) reduces to the Fibonacci identity above. \end{proof} The remaining four identities all follow from counting tilings that contain at least one of a certain kind of tile. We begin by considering tilings that contain at least one domino. \begin{ID} For $n\geq0$, $$k_n - 1 = k_{n-1} + 2 \sum_{i=0}^{n-2} (n-i) k_{i}.$$ \end{ID} \begin{proof} The left-hand side counts the number of tilings of a $(2 \times n)$-board with at least one domino, since there is only one tiling using all squares. We will show that the right-hand side counts the same thing. We condition on the location of the rightmost break in the tiling that still has at least one domino to its right. Say this break occurs at column $i$; we allow $i=0$ if there is no such break within the tiling. There are $k_{i}$ ways to fill in the first $i$ columns of such a tiling. The remaining $n-i$ columns begin with an unbreakable tiling of length $j$ ($1\leq j \leq n-i$) containing at least one domino and end with $n-i-j$ columns of squares. If $j=1$, the only appropriate unbreakable tiling is a vertical domino. If $j=2$, there are three unbreakable tilings, and if $j \geq 3$, there are two unbreakable tilings. (See Figure \ref{stagger}.) If we sum these possibilities over all $j$, we get 1 in the case $i=n-1$ and $2(n-i)$ in the case $0 \leq i \leq n-2 $ . This gives us the right-hand side of the identity. \end{proof} The next identity counts tilings that contain at least one square. \begin{ID} \label{knfnID} For $n \geq 1$, \begin{eqnarray} k_n -f_n &=& \sum_{i=0}^{n-1} k_{i}(f_{n-i-1}+ 2\sum_{j=2}^{n-i}f_{n-i-j}) \label{squareid1}\\ &=& \sum_{i=0}^{n-1} k_{i}(f_{n-i+2} -2). \label{squareid2} \end{eqnarray} \end{ID} \begin{proof} The left-hand side of (\ref{squareid1}) counts the number of tilings of a $(2 \times n)$-board with at least one square, since there are $f_n$ tilings using only dominoes. We will show that the right-hand side of (\ref{squareid1}) counts the same thing. We condition on the location of the rightmost break in the tiling that still has at least one square to its right. Say this break occurs at column $i$; we allow $i=0$ if there is no such break within the tiling. There are $k_{i}$ ways to fill in the first $i$ columns of such a tiling. The remaining $n-i$ columns begin with an unbreakable tiling of length $j$ ($1\leq j \leq n-i$) containing at least one square and end with a tiling of length $n-i-j$ using only dominoes. If $j=1$, the only appropriate unbreakable tiling is a pair of squares. If $j=2$, there are two unbreakable tilings with at least one square (a horizontal domino in one row and two squares in the other). If $j \geq 3$, there are two unbreakable tilings. There are $f_{n-i-j}$ tilings of length $n-i-j$ using only dominoes. If we sum over all $j$, we get the right-hand side of (\ref{squareid1}). We get (\ref{squareid2}) by applying the identity $\sum_{j=2}^{n-i}f_{n-i-j}=f_{n-i}-1$ to get \begin{eqnarray*} k_n -f_n &=& \sum_{i=1}^{n-1} k_{i}(f_{n-i-1}+ 2\sum_{j=2}^{n-i}f_{n-i-j})\\ &=& \sum_{i=1}^{n-1} k_{i}(f_{n-i-1} + 2f_{n-i} -2)\\ &=&\sum_{i=1}^{n-1} k_{i}(f_{n-i+2} -2). \end{eqnarray*} \end{proof} The next identity counts tilings which contain at least one vertical domino. After the last vertical domino, such a tiling will fall into two $(1 \times j)$-tilings for some $j$. Benjamin, Plott, and Sellers \cite{Pell} noted that the tilings of a $(1 \times n)$-board by dominoes and two colors of squares are counted by the Pell number $P_{n+1}$. They introduced the notation $p_{n} = P_{n+1}$ with $p_{0}=1$, $p_{1}=2$, and $p_n=2p_{n-1} + p_{n-2}$ (analogous to the Fibonacci notation $f_n$), and we follow that notation here. \begin{ID} For $n\geq0$, \begin{eqnarray} (i) &&k_n - (f_n)^2 = \sum_{m=1}^n k_{m-1} (f_{n-m})^2\\ (ii)&&k_n^{2,1} - (p_n)^2 = \sum_{m=1}^n k_{m-1}^{2,1} (p_{n-m})^2. \end{eqnarray} \end{ID} \begin{proof} Identity (\textit{i}) is due to Cipra and stated without proof in Sloane \cite{intseq}. In both (\textit{i}) and (\textit{ii}), the right- and left-hand sides represent two different ways of counting the number of tilings of a $(2 \times n)$-board with at least one vertical domino. A tiling with no vertical dominoes breaks into two $(1 \times n)$-tilings; there are $(f_{n})^2$ such tilings in the case $a=1$, $b=1$ and $(p_{n})^2$ in the case $a=2$, $b=1$. This gives us the left-hand sides in (\textit{i}) and (\textit{ii}), respectively. To get the right-hand sides, condition on the position of the last vertical domino. Say it is in column $m$. This domino is preceded by a tiling of a $(2 \times (m-1))$-board, of which there are $k_{m-1}$ in case (\textit{i}) and $k_{m-1}^{2,1}$ in case (\textit{ii}). This domino is followed by a tiling of a $(2 \times (n-m))$-board with no vertical dominoes, of which there are $(f_{n-m})^2$ in case (\textit{i}) and $(p_{n-m})^2$ in case (\textit{ii}). \end{proof} This identity can be generalized for any second order linear recurrence $l_n = a l_{n-1} + b l_{n-2}$ which has $l_0 = 1$ and $l_1 = a$. Our last identity counts tilings which contain at least one horizontal domino. \begin{ID} For $n \geq 2$, \begin{eqnarray*} (i) && k_{n} - 2^{n} =\sum_{i=0}^{n-2}k_{i}(2^{n-i-2} + 2^{n-i} - 2)\\ (ii) && k_{n}^{a,b} - (a^2 +b)^{n} = \sum_{i=0}^{n-2}k_{i}(b^{2}(a^2 +b)^{n-i-2} + 2(b(a^2+b)^{n-i-1} - b^{n-i})). \end{eqnarray*} \end{ID} \begin{proof} Once again, statement (\textit{i}) is the case $a=1$, $b=1$ of statement (\textit{ii}). The left-hand side counts the number of tilings with at least one horizontal domino. If a tiling has no horizontal dominoes, then each column contains either a vertical domino or two squares. There are $n$ columns and $a^2 +b$ possibilities for each column, so there are $(a^{2} +b)^{n}$ such tilings. The right-hand side also counts tilings with at least one horizontal domino. To show this, we condition on the rightmost break with at least one horizontal domino to its right. Say this break occurs at column $i$; we allow $i=0$ if there is no such break within the tiling. There are $k_{i}^{a,b}$ ways to fill in the first $i$ columns of such a tiling. If the $n-i$ columns after this break begin with two stacked horizontal dominoes, we have $b^2$ possibilities for these first two dominoes and $(a^2 +b)^{n-i-2}$ possibilities for the remaining columns. Otherwise, the tiling of the last $n-i$ columns begins with an unbreakable tiling of length $j$ ($j \geq 2$) containing two squares and $j-1$ dominoes. Let's consider the case when the first of the two squares appears in the top row; the case when the first square appears in the bottom row is handled in the same way and accounts for the factor of 2 in the right-hand side of (\textit{ii}). To make these tilings easier to count, turn this unbreakable segment into $j-1$ vertical dominoes followed by one column of two squares. The $m^{th}$ horizontal domino in the unbreakable tiling becomes the $m^{th}$ vertical domino in the new tiling, and the first and second squares in the unbreakable tiling become the top and bottom squares, respectively, in column $j$ of the new tiling. Finally, append the remaining $n-i-j$ columns of the original tiling to this new tiling. Now we have a tiling of a ($2 \times (n-i)$)-board that begins with a vertical domino and contains no horizontal dominoes. This process is almost invertible. Start with a tiling of a ($2 \times (n-i)$)-board that begins with a vertical domino and has no horizontal dominoes; there are $b(a^2+b)^{n-i-1}$ such tilings. Say it starts with $l$ consecutive columns of vertical dominoes ($l \geq 1$) followed by a column of two squares. Turn these $l$ dominoes and two squares into an unbreakable tiling of length $l+1$, putting the top square in the first column of the unbreakable tiling and the bottom square in the last column and turning the $m^{th}$ vertical domino into the $m^{th}$ horizontal domino. Append the remaining $n-i-l-1$ columns to create a ($2 \times (n-i)$)-board with an unbreakable tiling of length $l+1$ followed by $n-i-l-i$ columns with no horizontal dominoes. The only tilings that cannot undergo this process are those that do not begin with some number of vertical dominoes followed by a column of two squares. These are the tilings that use only vertical dominoes, and there are $b^{n-i}$ of these. Thus we have the right-hand side. \end{proof} In the case $a=0$, $b=1$, this is the Fibonacci recurrence $f_n -1 = \sum_{i=0}^{n-2}f_i$. \end{section} \begin{section}{Equivalent Tilings on a $(1 \times n)$-board} Benjamin and Quinn \cite[Section 3.5]{PTRC} give an interpretation of any $j$th order linear recurrence in terms of weighted $(1 \times n)$-tilings. In this setting, McQuistan and Lichtman's recurrence in equation (\ref{McQLrecur}) describes the tilings of a ($1 \times n$)-board with squares of three colors, dominoes of one color, and $(3 \times 1)$ trominoes of one color with the following condition: if the tile in column 1 is a square, it can be Color 1 or Color 2 but not Color 3. The weight of an individual tiling is 1 if the tiling has an even number of trominoes and $-1$ if it has an odd number of trominoes. A tiling with a negative weight counts negatively toward the total number of $(1 \times n)$-tilings. For example, when $n=3$ there are 24 unweighted tilings: $2\times 3\times 3$ with three squares, $2\times 1$ with one square followed by one domino, $1\times 3$ with one domino followed by one square, and 1 with one tromino. Since the tiling with a single tromino has weight $-1$, the total number of weighted tilings is 22, which is indeed $k_{3}$. Because these two types of tilings are both counted by $k_{n}$, we looked for a correspondence between them. \begin{thm} There is a one-to-one correspondence between the tilings of a $(2 \times n)$-board with squares and dominoes and the weighted tilings of a $(1 \times n)$-board described above which do not contain either a tromino or a domino followed immediately by a square of Color 3. The weights of the $(1 \times n)$-tilings which do contain a tromino or a domino followed immediately by a Color 3 square sum to 0. \end{thm} \begin{proof} We begin with a $(1 \times n)$-tiling with does not contain either a tromino or a domino followed immediately by a square of Color 3 and use it to construct a tiling of a $(2 \times n)$-board with squares and dominoes. See Figure \ref{1to2} for an example. \begin{enumerate} \item If column $i$ of the ($1 \times n$)-tiling contains a Color 1 square then put two squares in column $i$ of the ($2 \times n$)-board. \item If column $i$ of the ($1 \times n$)-tiling contains a Color 2 square then put a vertical domino in column $i$ of the ($2 \times n$)-board. \item If columns $i$ and $i+1$ of the $(1 \times n)$-tiling contain a domino then put two horizontal dominoes across columns $i$ and $i+1$ of the ($2 \times n$)-board. \item If column $i$ in the ($1 \times n$)-tiling is a Color 3 square then the action depends on what is in column $i-1$ of the ($1 \times n$)-tiling. (Recall that a Color 3 square will never appear in column 1.) \begin{enumerate} \item If column $i-1$ in the ($1 \times n$)-tiling contains a Color 1 square, then remove the lower square in column $i-1$ of the ($2 \times n$)-tiling, place a horizontal domino in the bottom row of columns $i-1$ and $i$, and place a square in the top row of column $i$. \item If column $i-1$ in the ($1 \times n$)-tiling contains a Color 2 square, then remove the vertical domino in column $i-1$ of the $2 \times n$ tiling, place a horizontal domino in the top row of columns $i-1$ and $i$, and place squares in the bottom row of columns $i-1$ and $i$. \item If column $i-1$ in the ($1 \times n$)-tiling contains another Color 3 square and if column $i-2$ contains a Color 1 or Color 2 square, then column $i-1$ of the ($2 \times n$)-tiling contains one square in one row and the second half of a horizontal domino in the other row. (See (a) and (b) above.) Remove the square and use a horizontal domino to fill in this position and the neighboring position in column $i$. Fill the remaining position in column $i$ with a square. Because this operation leaves column $i$ with a square and the second half of a horizontal domino, we can continue to apply this operation for any number of Color 3 squares in a row, creating an unbreakable segment in the ($2 \times n$)-tiling. Since a sequence of Color 3 squares must be preceded by either a Color 1 square or a Color 2 square, we have covered all possibilities. \end{enumerate} \end{enumerate} This procedure is invertible, so we have a one-to-one correspondence. Now we need to show that the weights of the $(1 \times n)$-tilings which do contain a tromino or a domino followed immediately by a Color 3 square sum to 0. Given such a $(1 \times n)$-tiling, find the rightmost occurrence of either a tromino or a domino followed by a Color 3 square. If it is a tromino, replace it with a domino and Color 3 square, and vice versa. The original tiling and the new tiling have weights of opposite sign, since one has one more tromino than the other. Since all the tilings under consideration can be paired this way, their weights sum to 0. \end{proof} \begin{figure}[H]\label{1to2} \begin{center} \epsfig{file=section4.eps,scale=0.4} \caption{A transformation of a $(1 \times 10)$-board to a $(2 \times 10)$-board by the rules above.} \label{section4} \end{center} \end{figure} \end{section} \begin{section}{Future Work} In this paper, we have extended earlier work on $(2 \times n)$-tilings to colored tilings, proved several identities, and connected $(2 \times n)$-tilings to weighted $(1 \times n)$-tilings. There is still more to be learned about the sequences $k_n$ and $k_n^{a,b}$. We have begun exploring the roots of the characteristic equation $x^3 - (a^2+2b)x^2 - a^2b x + b^3=0$, which lead to an expression for $k_n^{a,b}$ that is analogous to the Binet formula for the Fibonacci numbers. Since $\lim_{n\to\infty}k^{a,b}_{n+1}/k^{a,b}_{n}$ is one of these roots, we would like to be able to say more about them for various values of $a$ and $b$. We would also like to know more about the arithmetic properties of $k_n$ and $k_n^{a,b}$. Identity 3 shows that the parity of $k_n$ alternates. It is straightforward to use the recurrence relation in Theorem 1 to check the behavior of the parity of $k_n^{a,b}$ for different combinations of odd and even $a$ and $b$, but we expect there is a good deal more to be said in this area. Finally, this general approach should extend to boards of other shapes and sizes. \end{section} \begin{section}{Acknowledgments} Thanks to Art Benjamin for the discussion that led to this proof of Theorem \ref{abrecur}. Thanks to an anonymous referee for several helpful comments, including the observation about parity and Identity 3. Thanks to Henry Escuadro for suggesting that we look at squares and dominoes, and especially to James Sellers for his talk on Pell numbers and for his comments on earlier versions of this work. \end{section} \begin{thebibliography}{5} \bibitem{Pell} Arthur T. Benjamin, Sean S. Plott, and James Sellers, Tiling proofs of recent sum identities involving Pell numbers, \textit{Ann. Comb.}, \textbf{12} (2008) 271--278. \bibitem{PTRC} Arthur T. Benjamin and Jennifer J. Quinn, \textit{Proofs that Really Count: The Art of Combinatorial Proof}, Mathematical Association of America, 2003. \bibitem{Brualdi} Richard A. Brualdi, \textit{Introductory Combinatorics}, 4th edition, Pearson Prentice Hall, 2004. \bibitem{Grimson} R. C. Grimson, Exact formulas for $2 \times n$ arrays of dumbbells, \textit{J. Math Phys.}, \textbf{15} (1974) 214--216. \bibitem{McQ} R. B. McQuistan and S. J. Lichtman, Exact recursion relation for $2 \times N$ arrays of dumbbells, \textit{J. Math Phys.}, \textbf{11} (1970) 3095--3099. \bibitem{intseq} N. J. A. Sloane, (2008), The On-Line Encyclopedia of Integer Sequences, available at \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/\char'176njas/sequences/} \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 \textit{Mathematics Subject Classification}: Primary 05A19; Secondary 05A15, 05B45. \noindent {\textit{Keywords}:} dominoes, tiling, Fibonacci numbers, Pell numbers. \bigskip \hrule \bigskip \noindent Concerned with sequences \seqnum{A000045}, \seqnum{A000129}, and \seqnum{A030186}. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 20 2008; revised version received January 14 2009. Published in {\it Journal of Integer Sequences}, January 16 2009. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}