\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \input{epsf} \usepackage{amssymb,latexsym,graphicx} \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} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \def\sof{\hfill\rule{2mm}{2mm}} \def\NN{\mathbb{N}} \def\mn{\mbox{-}} \def\t{$\times$} \newcommand{\supsc}[1]{\ensuremath{^{\small \mbox{#1}}}} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Tiling with L's and Squares } \vskip 1cm \large Phyllis Chinn\\ Department of Mathematics\\ Humboldt State University\\ Arcata, CA 95521\\ USA\\ \href{mailto:phyllis@humboldt.edu}{\tt phyllis@humboldt.edu}\\ \ \\ Ralph Grimaldi \\ Department of Mathematics\\ Rose-Hulman Institute of Technology\\ Terre Haute, IN 47803 USA \\ \href{mailto:ralph.grimaldi@rose-hulman.edu}{\tt ralph.grimaldi@rose-hulman.edu}\\ \ \\ Silvia Heubach\\ Department of Mathematics\\ California State University, Los Angeles\\ Los Angeles, CA 90032\\ USA \\ \href{mailto:sheubac@calstatela.edu}{\tt sheubac@calstatela.edu} \\ \end{center} \vskip .2 in \begin{abstract} We consider tilings of $2\times n$, $3\times n$, and $4\times n$ boards with $1\times 1$ squares and L-shaped tiles covering an area of three square units, which can be used in four different orientations. For the $2\times n$ board, the recurrence relation for the number of tilings is of order three and, unlike most third order recurrence relations, can be solved exactly. For the $3\times n$ and $4 \times n$ board, we develop an algorithm that recursively creates the basic blocks (tilings that cannot be split vertically into smaller rectangular tilings) of size $3\times k$ and $4\times k$ from which we obtain the generating function for the total number of tilings. We also count the number of L-shaped tiles and $1\times 1$ squares in all the tilings of the $2 \times n$ and $3\times n$ boards and determine which type of tile is dominant in the long run. \end{abstract} %\newtheorem{theorem}{Theorem}[section] %\newtheorem{proposition}{Proposition}[section] %\newtheorem{corollary}{Corollary}[section] %\newtheorem{lemma}{Lemma}[section] \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{remark}[theorem]{Remark} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{fact}[theorem]{Fact} \newtheorem{example}[theorem]{Example} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{property}[theorem]{Property} \newtheorem{problem}[theorem]{Problem} \newtheorem{notation}[theorem]{Notation} %=========================================================================== \section{Introduction} Tiling 1$\times$$n$ boards with 1$\times$1 squares (henceforth referred to simply as squares) and dominoes (1$\times$2 tiles) leads to a connection with the Fibonacci numbers (see for example~\cite{ BenQui2003, BriCarChi1996}). These types of tilings have also been of interest in chemistry and statistical mechanics, where squares and dominoes are referred to as monomers and dimers (see for example~\cite{Caz1997, Kas1961, Ken1997, KenRanSin1996, Rog1979, TemFis1961}). There are many possible extensions to these most basic types of tilings (see for example~\cite{BriChiHol1994,Har1994, HarChi1994, Heu1999, HeuChi2001, HocRei2000}). Here, we consider tiling $2$$\times$$n$, $3$$\times$$n$, and $4$$\times$$n$ boards with two types of tiles: squares and L-shaped tiles, or L's (covering an area of three square units), where the L's can be used in four different orientations. %Our initial interest came from the fact that for the % 2$\times$$n$ board, the recurrence for the number of tilings leads to a % recurrence of order three which can be solved exactly. In Section~\ref{basic} we present notation and some general results on how the quantities of interest are related to each other. Section~\ref{2n} contains the results for the $2\times n$ boards. We obtain explicit results for the number of tilings, and the number of L's and squares in all the tilings of a given size. We also derive a combinatorial expression for the number of tilings in this case. In Section~\ref{3n} we give results for the $3\times n$ boards, where the picture gets a lot more complex. We develop an algorithm that creates recursively the {\it basic blocks} (tilings that cannot be split vertically into smaller rectangular tilings) of size 3$\times$$k$. This allows us to count the number of basic blocks of size 3$\times$$k$ for all $k$, and in turn leads us to the generating function for the total number of tilings. Finally, in Section~\ref{mn}, we obtain a generating function for the number of tilings of the $4\times n$ boards, and relate our approach to grammars. \section{Notation and basic results}\label{basic} We will count the number of tilings, as well as the number of squares and L's in all tilings of an $m \times n$ board, where $m$ denotes the vertical size of the board (or number of rows), and the second value (be it $n$, $k$, or $n-k$) refers to the horizontal dimension (or number of columns). We will use the following notation: \begin{center} \begin{tabular}{lcl} $T_{m,n}$& = & number of tilings of size $m$$\times$$n$ with L's and squares \\ $T_{m,n}^L $ & = & number of L's in all tilings of size $m$$\times$$n$ \\ $T_{m,n}^S$ & = & number of squares in all tilings of size $m$$\times$$n$\\ $B_{m,n}$ & = & number of basic blocks of size $m$$\times$$n$ \\ $B_{m,n}^L$& = & number of L's in all basic blocks of size $m$$\times$$n$ \\ $B_{m,n}^S$& = & number of squares in all basic blocks of size $m$$\times$$n$\\ \end{tabular} \end{center} For fixed $m$, we denote the generating function $\sum_{n=0}^{\infty}a_{m,n}x^n$ for a sequence $\{a_{m,n}\}_{0}^{\infty}$ by $G_{a_m}(x)$. Since we can decompose any tiling of size $m \times n$ into a basic block of size $m \times k$ on the left and a smaller tiling of size $m \times (n-k)$ following it, we get this recursion: \begin{eqnarray} \label{conv} T_{m,n} &=& \sum_{k=1}^n B_{m,k}\cdot T_{m,n-k} \quad \mbox{ for} \quad m,n \ge 1, \end{eqnarray} where we define $T_{m,0}=1$ for any $m \ge 1$. (A tiling of size $m$\t$n$ can consist of just a basic block of size $m\times n$.) Since the recursion for $T_{m,n}$ is a convolution, the respective generating functions multiply (see for example~\cite{Wil1994}, Section 2.2, Rule 3). Multiplying Eq.~(\ref{conv}) by $x^n$, summing over $n \ge 1$, and using the definition of the generating function, we obtain \begin{eqnarray} \label{convgf} % \nonumber to remove numbering (before each equation) G_{T_{m}}(x)-1 = G_{B_{m}}(x)G_{T_{m}}(x) \Rightarrow G_{T_{m}}(x)=\frac{1}{1-G_{B_{m}}(x)}. \end{eqnarray} We will also count the number of squares and L's in all the tilings of an $m$\t$n$ board. Looking at the total area covered by all such tilings and splitting it up according to areas covered by L's and squares, we have the following equation: \begin{eqnarray} \label{area} m \cdot n \cdot T_{m,n} = 3 T_{m,n}^L+ T_{m,n}^S. \end{eqnarray} Therefore, we have to count only one of the two types of tiles. Again, we decompose each tiling into a basic block and a smaller tiling. For each such basic block, we get all the squares in the tilings of the smaller size, and then, for each such smaller tiling, we get the number of squares in the basic block. Thus, for $m \ge 2$ and $n \ge 1$, \begin{eqnarray} \label{Ss} T_{m,n}^S = \sum_{k=1}^n B_{m,k} \cdot T_{m,n-k}^S + \sum_{k=1}^n B_{m,k}^S \cdot T_{m,n-k}. \end{eqnarray} Once more, this is a convolution, and we obtain \begin{eqnarray} \label{Ssgf} \quad \quad G_{T_m^S}(x)=G_{B_m}(x)G_{T_m^S}(x)+G_{B_m^S}(x)G_{T_m}(x)\; \Rightarrow \; G_{T_m^S}(x)=\frac{G_{B_m^S}(x)G_{T_m}(x)}{1-G_{B_m}(x)}. \end{eqnarray} The same type of argument gives these results for L's: \begin{eqnarray} \label{Ls} \quad \quad T_{m,n}^L = \sum_{k=1}^n B_{m,k} \cdot T_{m,n-k}^L + \sum_{k=1}^n B_{m,k}^L \cdot T_{m,n-k} \; \mbox{and} \; G_{T_m^L}(x)=\frac{G_{B_m^L}(x)G_{T_m}(x)}{1-G_{B_m}(x)}. \end{eqnarray} %-------------New Section------------------- \section{Tiling 2$\times$$n$ boards} \label{2n} We first look at the number of basic blocks of size 2$\times$$k$. Clearly, $B_{2,1}=1$, $B_{2,2}=4$, and $B_{2,3}=2$. There are no basic blocks for $k > 3$. Figure~\ref{bb2} shows all the basic blocks of size 2$\times$$k$. \begin{figure}[h] \begin{center} \epsfxsize=400.0pt \epsffile{2bb.eps} %\includegraphics{2bb} \caption{The basic blocks of size 2$\times$$k$} \label{bb2} \end{center} \end{figure} Using Eq.~(\ref{conv}), we get a recursion for $T_{2,n}$ for $n \ge 3$: \begin{equation}\label{rec2} T_{2,n}=T_{2,n-1}+4T_{2,n-2}+2T_{2,n-3}, \end{equation} with $T_{2,0}=1$, $T_{2,1}=1$, $T_{2,2}=5$ (all the basic blocks of size $2 \times 2$ and the tiling consisting of four squares). The corresponding characteristic equation is given by $x^3-x^2-4x-2=(x+1)(x^2-2x-2)=0$, and the characteristic roots are -1, $1+ \sqrt{3}$, and $1- \sqrt{3}$. Consequently, $T_{2,n}=c_1(-1)^n+c_2(1+\sqrt{3})^n+c_3(1-\sqrt{3})^n$, and using the initial conditions, we obtain $c_1=1$, $c_2 = 1/\sqrt{3}$, and $c_3 = -1/\sqrt{3}$. Since the resulting formula also gives the correct answers for $n=1,2$ and $3$, we have obtained an explicit formula for $T_{2,n}$. The generating function for $T_{2,n}$ can easily be derived from the generating function for $B_{2,n}$ by using Eq.~(\ref{convgf}). From Figure~\ref{bb2}, we can ``read off'' that $G_{B_{2,n}}=x+4x^{2}+3x^{3}$. We summarize these results in the following theorem. \begin{theorem} \label{expl2n} The number of tilings of size 2$\times$$n$ with L-shaped tiles and squares is given by $$T_{2,n}=(-1)^n+(1/\sqrt{3})((1+\sqrt{3})^n-(1-\sqrt{3})^n), \qquad \mbox{ for } n \ge 0,$$ with generating function $G_{T_{2,n}}(x)=1/(1-x-4x^2-2x^3)$. \end{theorem} Note that the recurrence in Eq.~(\ref{rec2}) is of the form given in Combinatorial Theorem 4 in~\cite{BenQui2003}. Thus, tilings of 2$\times$$n$ boards with L's and squares are in one-to-one correspondence with tilings of a 1$\times$$n$ board with tiles of length at most 3, where there is one tile of size 1$\times$1, four different colored tiles of size 1$\times$2, and two different colored tiles of size 1$\times$3, as shown in Figure~\ref{coltiles}. Obviously, the idea of mapping basic blocks of size $m \times k$ to colored tiles of size $1 \times k$ is applicable no matter what the shape of the tiles is, and the number of colors used for a tile of size $1 \times k$ is equal to the number of basic blocks of size $m \times k$. \begin{figure}[h] \begin{center} \epsfxsize=350.0pt \epsffile{Coltiles.eps} %\includegraphics{coltiles} \caption{Correspondence with colored tilings of 1$\times$$k$ rectangles} \label{coltiles} \end{center} \end{figure} The values for $T_{2,n}$ for $n=0,\ldots,20$ are given by $\{1$, $ 1$, $ 5$, $ 11$, $ 33$, $ 87$, $ 241$, $ 655$, $ 1793$, $ 4895$, $ 13377$, $ 36543$, $ 99841$, $ 272767$, $745217$, $ 2035967$, $ 5562369$, $ 15196671$, $ 41518081$, $ 113429503$, $ 309895169\}$. The signed version of this sequence appears in ~\cite{Sloane} as \seqnum{A077917}. No combinatorial explanation for the signed sequence is given. We now count the number of L's and squares for tilings of the $2$\t$n$ board. One way to do this is to think of a tiling as a sequence of basic blocks. Let \begin{center} \begin{tabular}{lll} $s$ &= & the number of basic blocks of size $2$\t$1$ (singles), \\ $d$ &= & the number of basic blocks of size $2$\t$2$ (doubles), and \\ $t$ &= & the number of basic blocks of size $2$\t$3$ (triples). \\ \end{tabular} \end{center} Note that $s+2d+3t = n$ and that $s+d+t=n-d-2t$ gives the number of basic blocks in the tiling. \begin{theorem} The number of squares and L-shaped tiles for tilings of the $2$\t$n$ board are given in combinatorial form by \begin{eqnarray*} T_{2,n}^S & =&\sum_{t = 0}^{n/3} \sum_{d=0}^{(n-3t)/2} \binom{n-d-2t}{t}\binom{n-d-3t}{d}(2s + d)4^d 2^t, \\ T_{2,n}^L & =&\sum_{t = 0}^{n/3} \sum_{d=0}^{(n-3t)/2} \binom{n-d-2t}{t}\binom{n-d-3t}{d}(d+2t)4^d 2^t, \end{eqnarray*} or, explicitly, by \begin{eqnarray} \label{numS} T_{2,n}^S&=& (2n-12)(-1)^n+\frac{2}{3}((9-5\sqrt{3})(1+\sqrt{3})^n+(9+5\sqrt{3})(1-\sqrt{3})^n) \\ \nonumber && \qquad +\frac{n}{\sqrt{3}}((\sqrt{3}-1)(1+\sqrt{3})^n + (\sqrt{3}+1)(1-\sqrt{3})^n) \end{eqnarray} and \begin{eqnarray} \label{numL} T_{2,n}^L&=& 4(-1)^n-\frac{2}{9}((9-5\sqrt{3})(1+\sqrt{3})^n+(9+5\sqrt{3})(1-\sqrt{3})^n) \\ \nonumber && \qquad -\frac{n}{3}((1-\sqrt{3})(1+\sqrt{3})^n + (1+\sqrt{3})(1-\sqrt{3})^n). \end{eqnarray} The respective generating functions are $$G_{T_2^S}(x)=\frac{2x(1+2x)}{(1+x)^2(1-2x-2x^2)^2}\; \mbox{ and } \; G_{T_2^L}(x)=\frac{4x^2}{(1+x)(1-2x-2x^2)^2}.$$ \end{theorem} \begin{proof} The combinatorial formula for the respective number of tiles is derived using the fact that each tiling of size $2$\t$n$ is made up by a succession of basic blocks. We count the number of squares and L's, respectively, according to the number of singles, doubles and triples in a particular tiling, then sum over all possible {\em configurations} $(s,d,t)$. If a tiling has configuration $(s,d,t)$, then there are $S(s,d,t)=2s+d$ squares and $L(s,d,t)=d+2t$ L's in that tiling. To count the number of tilings with configuration $(s,d,t)$, we first select the $t$ positions for the triples out of the possible $n-d-2t$ positions. Next we select the $d$ positions for the doubles out of the remaining $(n-d-2t)-t$ positions. The remaining $s = n-2d-3t$ positions are filled with singles. Once the positions have been selected, we can now fill each ``triple position'' with one of the two types of triples, and each ``double position'' with one of the four types of doubles. Thus there are $\binom{n-d-2t}{t} \binom{n-d-3t}{d} 1^s 4^d 2^t$ tilings with configuration $(s,t,d)$, containing $ \sum_{s+2d+3t=n}\binom{n-d-2t}{t}\binom{n-d-3t}{d} 1^s 4^d 2^t S(s,d,t)$ squares and $ \sum_{s+2d+3t=n}\binom{n-d-2t}{t} \binom{n-d-3t}{d} 1^s 4^d 2^t L(s,d,t)$ L's. The summation can be written as a double sum by realizing that there can be at most $n/3$ triples and at most $(n-3t)/2$ doubles, together with exactly $n-2d-3t$ singles. Substituting gives the stated result. Alternatively, since we have basic blocks only for $k=1, 2, 3$, we actually get a third order recurrence from Equations~(\ref{Ss}) and~(\ref{Ls}) for either the squares or L's. However, we now obtain a nonhomogeneous recurrence equation: \begin{eqnarray} % \nonumber to remove numbering (before each equation) T_{2,n}^S &=& (T_{2,n-1}^S+4\cdot T_{2,n-2}^S+2 \cdot T_{2,n-3}^S)+(2\cdot T_{2,n-1}+4\cdot T_{2,n-2}) \\ T_{2,n}^L &=& (T_{2,n-1}^L+4\cdot T_{2,n-2}^L+2 \cdot T_{2,n-3}^L)+(4\cdot T_{2,n-2}+4\cdot T_{2,n-3}) \end{eqnarray} We solve the recursion for the L's. Using Theorem~\ref{expl2n} we find that the nonhomogeneous part $a_n=4\cdot T_{2,n-2}+4\cdot T_{2,n-3}$ has the explicit form $a_n=\frac{\sqrt{3}+2}{\sqrt{3}}(1+\sqrt{3})^n+\frac{\sqrt{3}-2}{\sqrt{3}}(1-\sqrt{3})^n$. The homogeneous equation is identical to that for $T_{2,n}$, thus we get the roots $-1, 1+\sqrt{3},1-\sqrt{3}$, as before. This gives a general solution (see for example~\cite{Gri2004}) of the form $$T_{2,n}^L=c_1(-1)^n+c_2(1+\sqrt{3})^n+c_3(1-\sqrt{3})^n+A\cdot n(1+\sqrt{3})^n + B\cdot n (1-\sqrt{3})^n.$$ We use Mathematica to solve the system of five equations that results from substituting the initial conditions $T_{2,0}^L=0$, $T_{2,1}^L=0$, $T_{2,2}^L=4$, $T_{2,3}^L=12$, $T_{2,5}^L=52$ and obtain \begin{eqnarray*} T_{2,n}^L&=& 4(-1)^n-\frac{2}{9}((9-5\sqrt{3})(1+\sqrt{3})^n+(9+5\sqrt{3})(1-\sqrt{3})^n) \\ && \qquad -\frac{n}{3}((1-\sqrt{3})(1+\sqrt{3})^n + (1+\sqrt{3})(1-\sqrt{3})^n). \end{eqnarray*} Using Eq.~(\ref{area}) and the result for $T_{2,n}^L$ yields the result for $T_{2,n}^S$. The generating functions follow easily from Eqs.~(\ref{Ssgf}) and~(\ref{Ls}), where $G_{B_2^S}(x)=2x+4x^2=2x(1+2x)$ and $G_{B_2^L}(x)=4x^2+4x^3=4x^2(1+x)$ can be read off directly from Figure~\ref{bb2}. For example, the basic block of size $1\times1$ contains 2 squares, and the basic blocks of size $2\times2$ contain 4 squares. \end{proof} The numbers of squares and L's in all $2$\t$n$ tilings for $n=1,\ldots,15$ are given by $\{2$, $ 8$, $ 30$, $ 108$, $ 354$, $ 1152$, $ 3614$, $ 11204$, $ 34170$, $ 103176$, $ 308598$, $ 916236$, $2702834$, $ 7929872$, $ 23155182\}$ and $\{0$, $ 4$, $ 12$, $ 52$, $ 172$, $ 580$, $ 1852$, $ 5828$, $ 17980$, $ 54788$, $ 165116$, $ 493316$, $ 1463036$, $ 4312068$, $ 12641276\}$, respectively. Neither of these sequences occurred previously in ~\cite{Sloane}. We also note that the sequence $a_n=T_{2,n+1}+T_{2,n}$ which occurs in the nonhomogeneous part of the equation for $T_{2,n}^L$ satisfies $a_n=2(a_{n-1}+a_{n-2})$, since \begin{eqnarray*} a_n&=& (T_{2,n}+4\,T_{2,n-1}+2\,T_{2,n-2})+ T_{2,n}\\ &=& (2\,T_{2,n}+2\,T_{2,n-1})+(2\,T_{2,n-1}+2\,T_{2,n-2})= 2(a_{n-1}+a_{n-2}). \end{eqnarray*} The sequence $\{a_n/2 \}_{n=0}^\infty$ occurs in~\cite{Sloane} as \seqnum{A028859}, and counts the number of words on the alphabet \{0,1,2\} without adjacent zeros. A direct bijection between these words and the set of tilings of consecutive size is not obvious. Richard Anstee posed the question which of the two types of tiles becomes dominant in the long run, where dominant can have two meanings - in terms of actual number of tiles, or in terms of area covered by the specific type of tile. From Eqs.~(\ref{numS}) and~(\ref{numL}), we find that $$T_{{2,n}}^{S}\sim \frac{n(\sqrt{3}-1)}{\sqrt{3}}(1+\sqrt{3})^{n}\quad\mbox{and}\quad T_{{2,n}}^{L}\sim \frac{n(\sqrt{3}-1)}{3}(1+\sqrt{3})^{n}.$$ Thus, $$\frac{T_{{2,n}}^{S}}{T_{{2,n}}^{L}}\sim \sqrt{3} \quad \mbox{and} \quad \frac{T_{{2,n}}^{S}}{3\cdot T_{{2,n}}^{L}}\sim1/\sqrt{3},$$ i.e., there are more squares than L's by a factor of $\sqrt{3}$, but the area covered by L's is larger than the area covered by squares by the same factor. %-----------------------NEW SECTION----------------------- \section{Tiling 3$\times$$n$ boards} \label{3n} Tiling the 2$\times$$n$ board was straightforward because there were only basic blocks of size 2$\times$$k$ for $k=1, 2$ and $3$. This resulted in a linear recursion of order three that can be solved explicitly. However, for the $3$$\times$$n$ board we get basic blocks of all sizes. As before, we get one basic block of size 3$\times$1, which consists of three squares. There are eight basic blocks of size $3\times$ 2, as we can place the L's in exactly two positions for each of the four orientations. In addition, there are two basic blocks that contain two L's each. Figure~\ref{bb32} shows the ten basic blocks of size 3$\times$2. \begin{figure}[h] \begin{center} \epsfxsize=350.0pt \epsffile{3-2bb.eps} %\includegraphics[scale=1.2]{3-2bb} \caption{The ten basic blocks of size 3$\times$2} \label{bb32} \end{center} \end{figure} The 3$\times$3 basic blocks have two L's each, and it becomes clear that we need to use a systematic way to create the basic blocks to ensure that there are no duplicates and that we actually have found all of the basic blocks. We will create them recursively, by extending to the right, i.e., we create the basic blocks of size 3$\times$$(k+1)$ from those of size 3$\times k$ for $k \ge 2$. Since we do not want to destroy the basic block property, we cannot replace an L in the last column; we can only remove one or more squares and replace it/them with an L in such a way that the L fits into the additional column. We denote each 1$\times$1 area of the tiling as a {\it cell} to distinguish it from the square (tile). {\bf Basic Block Creation (BBC) Algorithm:} \begin{enumerate} \item Start with all basic blocks of size $m \times 2$, and determine the possible compositions of the last column in terms of cells covered by L's and squares. \item For each different composition (up to horizontal symmetry), assign a type. \item For each type, determine all possible ways to extend a basic block of that type by placing at least one L over one or two squares in the last column, and then filling the remaining cells in the newly created column with squares. \end{enumerate} Note that (3) ensures that the basic block property is maintained, so only basic blocks are created. On the other hand, given a basic block of size $m \times (k+1)$, it must have at least one L-shaped tile that spans the $k$th and ($k+1$)st columns. Taking away any L-shaped tiles that span the two rightmost columns, as well as all the square tiles of the rightmost column, and then placing square tiles into any empty cells in the $k$th column creates the basic block of size $m \times k$ from which the basic block of size $m \times (k+1)$ was created by extension. Thus, by exhaustively listing all the possible types and their extensions, we can ensure that all basic blocks of size $m \times (k+1)$ are created from those of size $m \times k$. In the case of $3\times k$ basic blocks, these are the possible types: \begin{itemize} \item {\it Type I}: The last column has two adjacent cells covered by a single L. (Note that we cannot have two nonadjacent cells covered by two different L's, as these L's would have to overlap in the center of the next-to-last column). \item {\it Type II}: The last column has two nonadjacent cells covered with squares (thus the center cell is covered by an L). \item {\it Type III}: The last column has two adjacent cells covered with squares (thus either the top or bottom cell is covered by an L). \end{itemize} The only other composition for a basic block of size $3\times 2$ is to have all cells covered with L's, but this type cannot be extended and therefore, is not assigned a type. In Figure~\ref{bb32}, the first four blocks are of Type I, the 6\supsc{th} and 7\supsc{th} are of Type II, and the 5\supsc{th} and 8\supsc{th} are of Type III. The last two blocks do not have a type. We now apply the BBC algorithm. For each basic block of Type I, there is exactly one way to extend, as shown in Figure~\ref{typeIext} for a basic block of size 3$\times$2. (For easy reference, the cell where the square is replaced by an L is marked with a dot.) The resulting basic block is again of Type I, since two adjacent cells in the last column are covered by an L. \begin{figure}[h] \begin{center} \epsfxsize=150.0pt \epsffile{Iext.eps} %\includegraphics{Iext} \caption{Extension for Type I} \label{typeIext} \end{center} \end{figure} For Type II basic blocks, the extension can be done either at the top or the bottom cell, i.e., each Type II basic block of size 3$\times$$k$ creates two basic blocks of size 3$\times$$(k+1)$, and both are of Type I (since two adjacent cells in the last column are covered by an L.) Again, for each of these extensions there is exactly one way, as indicated in Figure~\ref{typeIIext}, for one of the basic blocks of size 3$\times$2. \begin{figure}[h] \begin{center} \epsfxsize=400.0pt \epsffile{IIext.eps} %\includegraphics{IIext} \caption{Extension for Type II} \label{typeIIext} \end{center} \end{figure} Finally, we look at the extension for Type III blocks. There are several possibilities. If we replace the square in the middle ``row'', then there are two ways to place the L, pointing either upward or downward. In either case, the new block is of Type I. If we replace the square at the top or bottom (depending on the particular block), which can be done in exactly one way, a Type I basic block is created. Finally, since there are two adjacent cells covered by squares, we can place the L so that it covers those two cells. This can be done in two ways, one of which creates a Type II block, whereas the other one creates a Type III block. Figure~\ref{typeIIIext} shows the different possibilities. \begin{figure}[h] \begin{center} \epsfxsize=450.0pt \epsffile{IIIext.eps} %\includegraphics{IIIext} \caption{Extension for Type III} \label{typeIIIext} \end{center} \end{figure} Figure~\ref{3-3bb} shows the basic blocks of size 3$\times$3. Note that the first fourteen blocks are of Type I, the 15\supsc{th} and 16\supsc{th} are of Type II and the last two are of Type III. \begin{figure}[h] \begin{center} \epsfxsize=450.0pt \epsffile{3-3bb.eps} %\includegraphics{3-3bb} \caption{The basic blocks of size 3$\times$3} \label{3-3bb} \end{center} \end{figure} The BBC algorithm can be visualized from Figures~\ref{3-3bb} and~\ref{3-4bb}, which show the basic blocks of size 3$\times$3 and 3$\times$4, respectively. The first fourteen blocks in Figure~\ref{3-4bb} are the extensions of the fourteen Type I blocks of size 3$\times$3. The next four blocks result from the two extensions each of the two Type II blocks (15\supsc{th} and 16\supsc{th} in Figure~\ref{3-3bb}), which are also of Type I. The remaining ten blocks result from the extensions of the two Type III blocks. The first six extensions are Type I blocks, followed by two extensions of Type II, and finally two extensions of Type III. \begin{figure}[h] \begin{center} \epsfxsize=400.0pt \epsffile{3-4bb.eps} %\includegraphics{3-4bb} \caption{The basic blocks of size 3$\times$4} \label{3-4bb} \end{center} \end{figure} Using the BBC algorithm, we obtain an explicit formula for the number of basic blocks of size 3$\times$$k$, and from Eq.~(\ref{conv}), a generating function for the number of tilings of size 3$\times$$n$. \begin{theorem} \label{BT3} The number of basic blocks of size 3$\times$$k$ is given by $$B_{3,1}=1, B_{3,2}=10, \mbox{ and } B_{3,k}=10k-12 \quad \mbox{for } k \ge 3.$$ The generating functions for the number of basic blocks and the number of tilings are given by $$G_{B_3}(x)=\frac{x+8x^2-x^3+2x^4}{(1-x)^2}\quad \mbox{and} \quad G_{T_3}(x)=\frac{(1-x)^2}{1-3x-7x^2+x^3-2x^4}.$$ \end{theorem} \begin{proof}First of all we note that the BBC algorithm does not create duplicates. The extensions (if there are more than one) of a given basic block of size 3$\times$$k$ produce different basic blocks of size 3$\times$$(k+1)$ as the last columns differ (see Figures~\ref{typeIext}, \ref{typeIIext}, and \ref{typeIIIext}). Extensions from different basic blocks of size 3$\times$$k$ may produce the same last column, but will differ somewhere in the first $k$ columns. The algorithm also produces all basic blocks of a given size, as the three types are the only ones that can occur for $m=3$, and the extensions take into account all possibilities. Hence all blocks of size 3$\times$$(k+1)$ are created. Let $b_{k,t}$ be the number of basic blocks of size 3$\times$$k$ of type $t=I,II,III$, for $k \ge 2$. Then, for $k \ge 3$, $B_{3,k}=b_{k,I}+b_{k,II}+b_{k,III}$. From Figure~\ref{bb32} we can read off the initial conditions $b_{2,I}=4$, $b_{2,II}=2$, and $b_{2,III}=2$, and the BBC algorithm yields the following recursions for $k\ge 3$: $$b_{k+1,III}=b_{k,III}(=\ldots=b_{2,III}=2), \quad b_{k+1,II}=b_{k,III}=2 $$ and $$b_{k+1,I}=b_{k,I}+ 2 b_{k,II}+ 3 b_{k,III}=b_{k,I}+10,$$ from which the formula for $B_{3,k}$ follows. To obtain the generating functions, we use the initial conditions $B_{3,1}=1$ (the basic block consisting of all squares) and $B_{3,2}=10$ (see Figure~\ref{bb32}). Thus, \begin{eqnarray*} G_{B_3}(x)=\sum_{k\ge1}B_{3,k}x^k &=& x+10x^2+ \left(\left(\sum_{k\ge1}(10k-12)x^k\right) - \left(-2x+8x^2\right)\right)\\ &=& 3x+2x^2+10\sum_{k\ge1}k\,x^k -12\sum_{k\ge1}x^k\\ &=& 3x+2x^2+10\frac{x}{(1-x)^2}-12\frac{x}{1-x}= \frac{x+8x^2-x^3+2x^4}{(1-x)^2}. \end{eqnarray*} The result for $ G_{T_3}(x)$ follows from Eq.~(\ref{convgf}) and simplifying. \end{proof} The values for $T_{3,n}$ for $n=0,\ldots,15$ are given by $\{1$, $1$, $11$, $39$, $195$, $849$, $3895$, $17511$, $79339$, $358397$, $1620843$, $7326991$, \ $33127155$, $149766353$, $677103839$, $3061202815\}.$ This sequence did not previously occur in~\cite{Sloane}. Now we will count the number of L's and squares in the tilings of a $3$\t$n$ board. In light of Eqs.~(\ref{Ss}) and~(\ref{Ls}), we see that we have to obtain the generating function for either the number of L's or the number of squares in all basic blocks. Figures~\ref{3-3bb} and~\ref{3-4bb} suggest that each of the basic blocks of size $3$\t$k$ (except those for $k = 1, 2$) have exactly three squares. Thus, we will count the squares first, and then use Eq.~(\ref{area}) to obtain the result for the L's. \begin{theorem} The generating functions for the numbers of squares and L-shaped tiles in all tilings of the $3$\t$n$ board are given by $$G_{T_3^S}(x)=\frac{3x(1-x)^2(1+6x+3x^2)}{(1-3x-7x^2+x^3-2x^4)^2}\; \mbox{ and } \; G_{T_3^L}(x)=\frac{4x^2(3-3x+3x^2-4x^3+x^4)}{(1-3x-7x^2+x^3-2x^4)^2}.$$ \end{theorem} \begin{proof} Using the BBC algorithm, we can show that each basic block of size $3$\t$k$ for $k \ge 3$ contains exactly three squares. Figure~\ref{3-3bb} shows that the induction hypothesis is true for $k=3$. In the extension process we always obtain as many squares in the additional column as get covered in the prior last column, i.e., the number of squares remains the same. Thus, $B_{3,k}^S=3\cdot B_{3,k}$ for $k \ge 3$. Actually, this formula also holds for $k=1$. For $k=2$, we get $B_{3,k}^S=24=3\,B_{3,k}-6$. Therefore, $G_{B_3^S}(x)=3\cdot G_{B_3}(x)-6x^2 = 3x(1+6x+3x^2)/(1-x)^2$, where the last equality follows from Theorem~\ref{BT3}. Using Eq.~(\ref{Ssgf}), we obtain the desired result for $G_{T_3^S}(x)$. We note in passing that $B_{3,k}^S=3\,(10k-12)=30\,(k-1)-6$ for $k \ge 3$ (from Theorem~\ref{BT3}). This result also holds for $k=2$. Turning to the number of L's, Eq.~(\ref{area}) gives $T_{3,n}^L=n\cdot T_{3,n}-T_{3,n}^S/3$ for $n \ge 0$. In terms of generating functions, this translates to $G_{T_3^L}(x)=x \cdot G_{T_3}'(x)-G_{T_3^S}(x)/3$ (see for example~\cite{Wil1994}, Section 2.2, Rule 2), which gives the desired result after simplification. \end{proof} The values for $n = 1,\ldots 15$ for the numbers of squares and L's in $3$\t$n$ tilings are given by $\{3$, $ 30$, $ 171$, $ 1044$, $ 5691$, $ 30678$, $ 159891$, $ 821100$, $ 4151511$, $ 20764590$, $ 102880755$, $ 505866804$, $ 2471159019$, $ 12004723878$, $ 58037429739\}$ and $\{ 0$, $ 12$, $ 60$, $ 432$, $ 2348$, $ 13144$, $ 69280$, $ 361012$, $ 1841736$, $ 9286900$, $ 46303316$, $ \ 228903592$, $ 1123242916$, $ 5477879120$, $ 26572232312\}$, respectively. These sequences did not previously occur in~\cite{Sloane}. To answer the question about which type of tile dominates in the case of the $3\times n$ tilings, we need to use results from complex analysis about the asymptotic behavior for meromorphic functions. Recall that if $f$ is a meromorphic function in a region $\mathcal{R}$ and $z_{0}$ is a pole of order $r$, $1 \le r < \infty$, of $f$, then in some punctured disk centered at $z_{0}$, $f$ has an expansion of the form $$ f(z)=\sum_{j=1}^{r}\frac{a_{-j}}{(z-z_{0})^{j}}+ \sum_{j=0}^{\infty}a_{j}(z-z_{0})^{j}=PP(f;z_{0}) + \sum_{j=0}^{\infty}a_{j}(z-z_{0})^{j},$$ and the principal part $PP(f;z_{0})$ is given by (see \cite{Wil1994}, Eq.~(5.2.4)) \begin{equation}\label{Wilfeq} PP(f;z_{0})=\sum_{n \ge 0}z^{n}\left\{ \sum_{j=1}^{r}\frac{(-1)^{j}a_{-j}}{z_{0}^{n+j}}\binom{n+j-1}{j-1}\right\}. \end{equation} In addition, for poles of order 2, the coefficients $a_{-1}$ and $a_{-2}$ for a function $f(z) = g(z)/h(z)$ at the pole $z_{0}$ are given by (see for example~\cite{MarHof1987}, Proposition 4.1.4 and proof thereof) \begin{equation} \label{coeff} a_{-1}=Res\left(\frac{g}{h},z_{0}\right)=2\frac{g'(z_{0})}{h''(z_{0})}-\frac{2}{3}\frac{g(z_{0})h'''(z_{0})}{[h''(z_{0})]^{2}} \quad \mbox{and} \quad a_{-2}=\frac{2g(z_{0})}{h''(z_{0})}. \end{equation} We are now ready to state the asymptotic result. \begin{corollary} \label{3asym} The asymptotic expressions for the number of squares and L-shaped tiles in all tilings of the $3$\t$n$ board are given by \begin{eqnarray*} T_{3,n}^S& \,\sim & (0.234746 + 0.558529\, n) c_{1}^{n} +(0.0641066 + 0.329504\,n)c_{2}^{n}, \\ T_{3,n}^L &\, \sim & (-0.0782485 + 0.268102\, n) c_{1}^{n} +(-0.0213689 + 0.460065\,n) c_{2}^{n}, \end{eqnarray*} where $ c_{1}=4.52104$, $c_{2} = -1.738438$, and the error term is of order $O\left(\left(0.504457+\epsilon\right)^{n}\right)$. \end{corollary} \begin{proof} Both generating functions have the same denominator, and thus the same poles. Using Mathematica, we find that there are four different roots, two real ones, $z_{0}= 0.221188$ and $z_{1}= -0.575250$, and two complex ones with modulus $R =1.98233$. (Note that Mathematica gives exact roots that are used in the subsequent calculations. We give numerical values to six digits precision.) Applying Theorem 5.2.1~\cite{Wil1994} twice to the poles at the real roots, we obtain \begin{eqnarray*} [z^{n}]f(z)&=&[z^{n}]\left(PP(f,z_{0})+PP(f,z_{1})\right)+O\left(\left(\frac{1}{R}+\epsilon\right)^{n}\right)\\ &=&\sum_{i=0,1}\left(\frac{-a_{i,-1}}{z_{i}}+\frac{(n+1)a_{i,-2}}{z_{i}^{2}}\right)\left(\frac{1}{z_{i}}\right)^{n}+O\left(\left(\frac{1}{R}+\epsilon\right)^{n}\right), \end{eqnarray*} where $a_{i,-j}$ denotes the coefficient $a_{-j}$ for the pole $z_{i}$. Using Eqs.~(\ref{Wilfeq}) and (\ref{coeff}), we find that for $G_{T_3^S}(z)$, $a_{0,-1}=0.0716171$, $a_{0,-2}=0.0273256$, $a_{1,-1}= - 0.152670$, and $a_{1,-2}=0.109037$. For $G_{T_3^L}(z)$, the respective values are $0.0766088$, $0.0131167$, $-0.276945$, and $0.152241$. These values were obtained by using the exact roots computed in Mathematica. Simplifying the expressions gives the desired asymptotic results. \end{proof} The approximation is quite good for both the number of squares and the number of L's. For small values of $n$, rounding the approximate value to the nearest integer gives the correct result, and for larger values, the approximation provides at least 10 significant digits. Using Corollary~\ref{3asym}, we obtain $$\frac{T_{{3,n}}^{S}}{T_{{3,n}}^{L}}\sim \frac{0.5585}{0.2681}=2.08318\quad \mbox{and} \quad \frac{T_{{2,n}}^{S}}{3\cdot T_{{2,n}}^{L}}\sim0.694393,$$ and can answer the question on which type of tile dominates. The number of squares is approximately twice the number of L-shaped tiles, but the area covered by the L-shaped tiles is about 50\% more than the area covered by the squares. %-----------------------NEW SECTION----------------------- \section{Tiling $m \times$$n$ boards} \label{mn} Trying to obtain results for $m > 3$ becomes increasingly difficult, as illustrated below for the case $m = 4$. The BBC algorithm can still be used for $m = 3$, but its limitation for larger values of $m$ becomes obvious. Not only does the number of basic blocks increase quite dramatically, but the number of types also increases rapidly. For the $4\times 2$ board, there are 32 basic blocks instead of the 10 basic blocks of size $3\times 2$. Figure~\ref{bb42} shows the basic blocks up to symmetry (horizontal reflection), where all but the last four blocks also occur in reflected form. \begin{figure}[h] \begin{center} \epsfxsize=400.0pt \epsffile{bb42.eps} %\includegraphics{bb42} \caption{Basic blocks of size 4$\times$2} \label{bb42} \end{center} \end{figure} There are now nine different end shapes, where what matters is the position of the squares, as this is where the extension takes place. Table~1 shows the possible types (up to horizontal reflection): Types I and II both have three squares, Types III - VI have two squares, Types VII and VIII have one square, and Type IX has no square. \begin{table}[htdp] \label{types} \begin{center} \caption{The nine types of end shapes for 4$\times k$ basic blocks} \begin{tabular}{|c|c|c|c|} I \phantom{xxx} II &\phantom{x} III \phantom{xxx} IV \phantom{xxxx} V \phantom{xxxx} VI \phantom{x}& VII \phantom{xx} VIII & IX\\ \hline \epsfxsize=75.0pt \epsffile{3s.eps} & \epsfxsize=165.0pt \epsffile{2s.eps} & \epsfxsize=75.0pt \epsffile{1s.eps}& \epsfxsize=30.0pt \epsffile{0s.eps} %\includegraphics{3s} & \includegraphics{2s} & \includegraphics{1s} & \includegraphics{0s} \end{tabular} \end{center} \end{table} Type IX does not extend, but gets created from some of the other types, whereas Types V and VI exist only for $n=2$. They can extend, but this type of end shape never gets created (since the two columns form a basic block by themselves and thus cannot be a part of a larger basic block). Applying the BBC Algorithm described in Section~\ref{3n} for each of the types we obtain Table~2, which describes how many basic blocks of each type are created when extending a basic block of a certain type. For example, a Type III basic block will create one basic block each of Type I, II and IV, and two basic blocks of Type III. \begin{table}[htdp] \begin{center} \caption{Results of the BBC algorithm} \begin{tabular}{|c|ccccccccc|} \phantom{x} & \multicolumn{9}{c|}{Extension Type}\\ \hline Type & I & II & III & IV & V & VI & VII & VIII & IX\\ \hline I & 1 & 3 & 3 & 2 & - & - & 1 & 3 & 2\\ II & 1 & 1 & 3 & 1 & - & - & 1 & 1 & 2\\ III & 1 & 1 & 2 & 1 & - & - & - & - & -\\ IV & - & - & 2 & - & - & - & - & - & 1\\ V & - & 2 & 2 & 2 & - & - & - & - & 1\\ VI & - & - & 2 & 1 & - & - & - & - & 1\\ VII & - & - & 1 & 1 & - & - & - & - & -\\ VIII & - & - & 1 & - & - & - & - & - & -\\ IX & - & - & - & - & - & - & - & - & -\\ \end{tabular} \end{center} \label{4exten} \end{table}% Let $\tilde{b}_{k,t}$ denote the number of basic blocks of size 4$\times k$ of type $t = I, II, \ldots IX$, for $k \ge 2$. From Figure~\ref{bb42}, we can read off the values for $\tilde{b}_{2,t}$, and then, using Table~2, we can compute the values for $\tilde{b}_{3,t}$, which are given in Table~3. \begin{table}[htdp] \begin{center} \caption{Initial conditions for $\tilde{b}_{n,t}$ } \begin{tabular}{c|ccccccccc|c} Type & I & II & III & IV & V & VI & VII & VIII & IX & total\\ \hline $\tilde{b}_{2,t}$ & 2 & 4 & 4 & 3 & 1& 2 & 4 & 8 & 4& 32\\ $\tilde{b}_{3,t}$ & 10 & 16 & 50 & 20 & 0 & 0 & 6 & 10 & 18& 130\\ \end{tabular} \end{center} \label{inicond} \end{table}% Using Table~2 we can also read off a system of recurrence relations for $\tilde{b}_{n,t}$ for $t = I, \ldots , IV, VII, VIII$, and $IX$. For example, Column 4 of Table~2 gives this relation: $$ \tilde{b}_{n+1,IV} = 2 \tilde{b}_{n,I} + \tilde{b}_{n,II}+\tilde{b}_{n,III}+2\tilde{b}_{n,VII}, $$ since $\tilde{b}_{n,V}=\tilde{b}_{n,VI}=0$ for $n > 2$. Adding the equation $$ B_{4,n+1}= \tilde{b}_{n+1,I} + \tilde{b}_{n+1,II}+\tilde{b}_{n+1,III}+\tilde{b}_{n+1,IV}+\tilde{b}_{n+1,VII}+\tilde{b}_{n+1,VIII}+\tilde{b}_{n+1,IX},$$ and using the initial conditions for $n=3$, we can use the Mathematica function GeneratingFunction from the package DiscreteMath$^{\backprime}$RSolve to compute the generating function for $B_{4,n}$ for $n \ge 3$. Adjusting this generating function by adding in the terms $B_{4,1}$ and $B_{4,2}$, we obtain the following theorem for the $4\times n$ tilings, where the generating function for $T_{4,n}$ follows from Eq.~(\ref{convgf}). \begin{theorem} The generating function for the number basic blocks and the number of tilings of the $4$\t$n$ board with L-shaped tiles and squares is given by $$G_{B_4}(x)=\frac{z(1 + 28z - 4z^2 - 80z^3 - 32z^4 + 74z^5 - 10z^6 - 4z^7 - 4z^8)}{1 - 4z - 6z^2 - 10z^3 - 8z^4 - 4z^5}$$ and $$G_{T_4}(x)=\frac{1 - 4 z - 6 z^2 - 10 z^3 - 8 z^4 - 4 z^5}{1 - 5z - 34 z^2 - 6 z^3 + 72 z^4 + 28 z^5 - 74 z^6 +10 z^7 + 4 z^8 + 4 z^{9}}.$$ \end{theorem} The values for $n = 0,\ldots, 15$ for the number of tilings of the $4 \times n$ board are given by $\{1$, $1$, $ 33$, $ 195$, $2023$, $ 16839$, $ 151817$, $ 1328849$, $ 11758369$, $ 103628653$, $ 914646205$, $ 8068452381$, $ 71189251649$, $ 628067760289$, $ 5541284098945$, $ 48888866203241\}$. Results for the numbers of L's and squares are much more difficult to obtain, as the basic blocks no longer have a constant number of squares, and one would have to set up a system of recurrence relations for the number of squares according to the type of basic blocks, similar to that for the basic blocks themselves. An alternative approach is to express tiling problems in terms of grammars, which allows for automation of the process~\cite{ MarMerRoc2000, MerSprVer2000, MerSprVer2002}. Similar to the extension process described in Section~\ref{3n}, in the grammar approach a tiling is built up by placing tiles onto the board in lexicographic order, describing for each partial tiling (which has a ragged right edge) which tiles can be placed in the next step. This process produces a system of recurrence relations, which can be solved using a computer program. Note that the underlying ideas are similar to the extension algorithm, but that there are also differences. The states used in the grammar approach are not complete tilings except for the initial state, and one cannot separate out the basic blocks from a composite tiling which is made up from more than one basic block. Even with the grammar approach, the tiling problem is solvable only for small to midsize problems, as the complexity increases exponentially. Focusing on basic blocks cuts down the size of the problem, but so far there is no automatic algorithm that creates basic blocks only and for which the methodology used by Merlini and her co-authors can be applied. \section{Acknowledgments} We would like to thank Richard Anstee for raising the question on which type of tile dominates in the long run, and the anonymous referee for an extremely careful reading of the manuscript. \begin{thebibliography}{99} \bibitem{BenQui2003} A.~T. Benjamin and J.~J. Quinn. \newblock {\em Proofs that really count}, Vol.~27 of {\em The Dolciani Mathematical Expositions}. \newblock Mathematical Association of America, Washington, DC, 2003. %\newblock The art of combinatorial proof. \bibitem{BriCarChi1996} R.~C. Brigham, R.~M. Caron, P.~Z. Chinn, and R.~P. Grimaldi. \newblock A tiling scheme for the {Fibonacci} numbers. \newblock {\em J. Recreational Math.}, {\bf 28} (1996) 10--17. \bibitem{BriChiHol1994} R.~C. Brigham, P.~Z. Chinn, L.~M. Holt, and R.~S. Wilson. \newblock Finding the recurrence relation for tiling {$2\times n$} rectangles. \newblock {\em Congr. Numer.}, {\bf 105} (1994) 134--138. \bibitem{Caz1997} F.~Cazals. \newblock Monomer-dimer tilings. \\ \newblock \href{http://citeseer.ist.psu.edu/cazals97monomerdimer.html}{\tt http://citeseer.ist.psu.edu/cazals97monomerdimer.html}, 1997. \bibitem{Gri2004} R.~Grimaldi. \newblock {\em Discrete and Combinatorial Mathematics}, 5th Edition. \newblock Pearson Education, Inc., 2004. \bibitem{Har1994} E.~O. Hare. \newblock Tiling a {$3\times n$} area with {C}uisenaire rods of length less than or equal to {$k$}. \newblock {\em Congr. Numer.}, {\bf 105} (1994) 33--45. \bibitem{HarChi1994} E.~O. Hare and P.~Z. Chinn. \newblock Tiling with {C}uisenaire rods. \newblock In {\em Applications of Fibonacci Numbers}, Vol.\ 6 (Pullman, WA, 1994), 165--171. Kluwer Acad. Publ., Dordrecht, 1996. \bibitem{Heu1999} S.~Heubach. \newblock Tiling an $m$-by-$n$ area with squares of size up to $k$-by-$k$ with $m \le 5$. \newblock {\em Congr. Numer.}, {\bf 140} (1999) 43--64. \bibitem{HeuChi2001} S.~Heubach and P. Z.~Chinn. \newblock Patterns arising from tiling rectangles with 1-by-1 and 2-by-2 squares. \newblock {\em Congr. Numer.}, {\bf 150} (2001) 173--192. \bibitem{HocRei2000} R. Hochberg and M. Reid. \newblock Tiling with notched cubes. \newblock {\em Discrete Math.}, {\bf 214} (2000) 255--261. \bibitem{Kas1961} P. W. Kasteleyn. \newblock The statistics of dimers on a lattice. \newblock {\em Physica}, {\bf 27} (1961) 1209--1225. \bibitem{Ken1997} R. Kenyon. \newblock Local statistics of lattice dimers. \newblock {\em Ann. Inst. H. Poincar\'e Probab. Statist.}, {\bf 33} (1997) 591--618. \bibitem{KenRanSin1996} C. Kenyon, D. Randall, and A. Sinclair. \newblock Approximating the number of monomer-dimer coverings of a lattice. \newblock {\em J. Statist. Phys.}, {\bf 83} (1996) 637--659. \bibitem{MarHof1987} J. E. Marsden and M. J. Hoffman. \newblock {\em Basic Complex Analysis}, 2nd Edition. \newblock W. H. Freeman and Company, 1987. \bibitem{MarMerRoc2000} L. Martinelli, D. Merlini, et.al. \newblock A software to solve strip tiling problems. \newblock {\em Formal Power Series and Algebraic Combinatorics (FPSAC, Moscow 2000)}, 801--805, Springer Berlin, 2000. \bibitem{MerSprVer2000} D. Merlini, R. Sprugnoli, and M.~C. Verri. \newblock Strip tiling and regular grammars. \newblock {\em Theoretical Computer Science}, {\bf 242} (2000) 109--124. \bibitem{MerSprVer2002} D. Merlini, R. Sprugnoli, and M.~C. Verri. \newblock A strip-like tiling algorithm. \newblock {\em Theoretical Computer Science}, {\bf 282} (2002) 337--352. \bibitem{Rog1979} D.~G. Rogers. \newblock An application of renewal sequences to the dimer problem. \newblock In {\em Combinatorial mathematics, VI (Proc. Sixth Austral. Conf., Univ. New England, Armidale, 1978)}, volume 748 of {\em Lecture Notes in Math.}, 143--153. Springer, Berlin, 1979. \bibitem{Sloane} N. J. A. Sloane. \newblock The on-line encyclopedia of integer sequences. \newblock published electronically at \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/$\sim$njas/sequences/}, 2007. \bibitem{TemFis1961} H. N. V. Temperley and M. E. Fisher. \newblock Dimer problem in statistical mechanics, an exact result. \newblock {\em Philosophical Magazine}, {\bf 6} (1961) 1061--1063. \bibitem{Wil1994} H.~S. Wilf. \newblock {\em Generatingfunctionology}, 2nd Edition. \newblock Academic Press, Inc., 1994. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 52C20; Secondary 52C22. \noindent \emph{Keywords: } Tilings, trominoes, recurrence relations, generating functions. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A028859} and \seqnum{A077917}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 21 2006; revised version received February 28 2007. Published in {\it Journal of Integer Sequences}, March 19 2007. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}