Tiling with L’s and Squares

Phyllis Chinn Department of Mathematics Humboldt State University Arcata, CA 95521 USA

                 phyllis@humboldt.edu

Ralph Grimaldi Department of Mathematics Rose-Hulman Institute of Technology Terre Haute, IN 47803 USA

            ralph.grimaldi@rose-hulman.edu

Silvia Heubach Department of Mathematics California State University, Los Angeles Los Angeles, CA 90032 USA

                sheubac@calstatela.edu

Abstract

We consider tilings of 2 × n, 3 × n, and 4 × n boards with 1 × 1 squares and Lshaped tiles covering an area of three square units, which can be used in four different orientations. For the 2 × 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 × n and 4 × 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 × k and 4 × 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 × 1 squares in all the tilings of the 2 × n and 3 × n boards and determine which type of tile is dominant in the long run.

1 Introduction

Tiling 1×n boards with 1×1 squares (henceforth referred to simply as squares) and dominoes (1×2 tiles) leads to a connection with the Fibonacci numbers (see for example [1, 2]). 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 [4, 11, 12, 13, 18, 20]). There are many possible extensions to these most basic types of tilings (see for example [3, 6, 7, 8, 9, 10]). Here, we consider tiling 2×n, 3×n, and 4×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.

In Section 2 we present notation and some general results on how the quantities of interest are related to each other. Section 3 contains the results for the 2 × 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 4 we give results for the 3 × n boards, where the picture gets a lot more complex. We develop an algorithm that creates recursively the basic blocks (tilings that cannot be split vertically into smaller rectangular tilings) of size 3×k. This allows us to count the number of basic blocks of size 3×k for all k, and in turn leads us to the generating function for the total number of tilings. Finally, in Section 5, we obtain a generating function for the number of tilings of the 4 × n boards, and relate our approach to grammars.

2 Notation and basic results

We will count the number of tilings, as well as the number of squares and L’s in all tilings of an m × 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:

T_{m,n} = number of tilings of size m×n with L’s and squares
T_{m,n}^{L} = number of L’s in all tilings of size m×n
T_{m,n}^{S} = number of squares in all tilings of size m×n
B_{m,n} = number of basic blocks of size m×n
B_{m,n}^{L} = number of L’s in all basic blocks of size m×n
B_{m,n}^{S} = number of squares in all basic blocks of size m×n

For fixed m, we denote the generating function ∑_{n=0}^{∞} a_{m,n}x^{n} for a sequence {a_{m,n}}_{0}^{∞} by G_{a_{m}}(x). Since we can decompose any tiling of size m × n into a basic block of size m × k on the left and a smaller tiling of size m × (n − k) following it, we get this recursion:

T_{m,n} = ∑_{k=1}^{n} B_{m,k} · T_{m,n−k} for m, n ≥ 1,  (2.1)

where we define T_{m,0} = 1 for any m ≥ 1. (A tiling of size m×n can consist of just a basic block of size m × n.) Since the recursion for T_{m,n} is a convolution, the respective generating functions multiply (see for example [21], Section 2.2, Rule 3). Multiplying Eq. (2.1) by x^{n}, summing over n ≥ 1, and using the definition of the generating function, we obtain

G_{T_{m}}(x) − 1 = G_{B_{m}}(x)G_{T_{m}}(x) ⇒ G_{T_{m}}(x) = \frac{1}{1 − G_{B_{m}}(x)}.  (2.2)

We will also count the number of squares and L’s in all the tilings of an m×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:

m · n · T_{m,n} = 3T_{m,n}^{L} + T_{m,n}^{S}.  (2.3)

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 ≥ 2 and n ≥ 1,

T_{m,n}^{S} = ∑_{k=1}^{n} B_{m,k} · T_{m,n−k}^{S} + ∑_{k=1}^{n} B_{m,k}^{S} · T_{m,n−k}.  (2.4)

Once more, this is a convolution, and we obtain

G_{T_{m}^{S}}(x) = G_{B_{m}}(x)G_{T_{m}^{S}}(x) + G_{B_{m}^{S}}(x)G_{T_{m}}(x) ⇒ G_{T_{m}^{S}}(x) = \frac{G_{B_{m}^{S}}(x)G_{T_{m}}(x)}{1 − G_{B_{m}}(x)}. (2.5)

The same type of argument gives these results for L’s:

T_{m,n}^{L} = ∑_{k=1}^{n} B_{m,k} · T_{m,n−k}^{L} + ∑_{k=1}^{n} B_{m,k}^{L} · T_{m,n−k} and G_{T_{m}^{L}}(x) = \frac{G_{B_{m}^{L}}(x)G_{T_{m}}(x)}{1 − G_{B_{m}}(x)}. (2.6)

3 Tiling 2×n boards

We first look at the number of basic blocks of size 2×k. Clearly, B_{2,1} = 1, B_{2,2} = 4, and B_{2,3} = 2. There are no basic blocks for k > 3. Figure 1 shows all the basic blocks of size 2×k.

Figure 1: The basic blocks of size 2×k

Using Eq. (2.1), we get a recursion for T_{2,n} for n ≥ 3:

T_{2,n} = T_{2,n−1} + 4T_{2,n−2} + 2T_{2,n−3},  (3.1)

with T_{2,0} = 1, T_{2,1} = 1, T_{2,2} = 5 (all the basic blocks of size 2 × 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. (2.2). From Figure 1, we can “read off” that G_{B_{2,n}} = x + 4x^{2} + 3x^{3}. We summarize these results in the following theorem.

Theorem 3.1. The number of tilings of size 2×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}), for n ≥ 0,

with generating function G_{T_{2,n}}(x) = 1/(1 − x − 4x^{2} − 2x^{3}).

Note that the recurrence in Eq. (3.1) is of the form given in Combinatorial Theorem 4 in [1]. Thus, tilings of 2×n boards with L’s and squares are in one-to-one correspondence with tilings of a 1×n board with tiles of length at most 3, where there is one tile of size 1×1, four different colored tiles of size 1×2, and two different colored tiles of size 1×3, as shown in Figure 2. Obviously, the idea of mapping basic blocks of size m × k to colored tiles of size 1 × k is applicable no matter what the shape of the tiles is, and the number of colors used for a tile of size 1 × k is equal to the number of basic blocks of size m × k.

Figure 2: Correspondence with colored tilings of 1×k rectangles

The values for T_{2,n} for n = 0, …, 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 [19] as \underline{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×n board. One way to do this is to think of a tiling as a sequence of basic blocks. Let

s = the number of basic blocks of size 2×1 (singles),
d = the number of basic blocks of size 2×2 (doubles), and
t = the number of basic blocks of size 2×3 (triples).

Note that s + 2d + 3t = n and that s + d + t = n − d − 2t gives the number of basic blocks in the tiling.

Theorem 3.2. The number of squares and L-shaped tiles for tilings of the 2×n board are given in combinatorial form by

T_{2,n}^{S} = ∑_{t=0}^{n/3} ∑_{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} = ∑_{t=0}^{n/3} ∑_{d=0}^{(n−3t)/2} \binom{n − d − 2t}{t}\binom{n − d − 3t}{d}(d + 2t)4^{d}2^{t},

or, explicitly, by

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}) (3.2)

+\frac{n}{\sqrt{3}}((\sqrt{3} − 1)(1 + \sqrt{3})^{n} + (\sqrt{3} + 1)(1 − \sqrt{3})^{n})

and

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})  (3.3)

−\frac{n}{3}((1 − \sqrt{3})(1 + \sqrt{3})^{n} + (1 + \sqrt{3})(1 − \sqrt{3})^{n}).

The respective generating functions are

G_{T_{2}^{S}}(x) = \frac{2x(1 + 2x)}{(1 + x)^{2}(1 − 2x − 2x^{2})^{2}} and G_{T_{2}^{L}}(x) = \frac{4x^{2}}{(1 + x)(1 − 2x − 2x^{2})^{2}} .

Proof. The combinatorial formula for the respective number of tiles is derived using the fact that each tiling of size 2×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 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 ∑_{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 ∑_{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 (2.4) and (2.6) for either the squares or L’s. However, we now obtain a nonhomogeneous recurrence equation:

T_{2,n}^{S} = (T_{2,n−1}^{S} + 4 · T_{2,n−2}^{S} + 2 · T_{2,n−3}^{S}) + (2 · T_{2,n−1} + 4 · T_{2,n−2})  (3.4)
T_{2,n}^{L} = (T_{2,n−1}^{L} + 4 · T_{2,n−2}^{L} + 2 · T_{2,n−3}^{L}) + (4 · T_{2,n−2} + 4 · T_{2,n−3})  (3.5)

We solve the recursion for the L’s. Using Theorem 3.1 we find that the nonhomogeneous part a_{n} = 4·T_{2,n−2} +4·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 [5]) of the form

T_{2,n}^{L} = c_{1}(−1)^{n} + c_{2}(1 + \sqrt{3})^{n} + c_{3}(1 − \sqrt{3})^{n} + A · n(1 + \sqrt{3})^{n} + B · 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

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})

−\frac{n}{3}((1 − \sqrt{3})(1 + \sqrt{3})^{n} + (1 + \sqrt{3})(1 − \sqrt{3})^{n}).

Using Eq. (2.3) and the result for T_{2,n}^{L} yields the result for T_{2,n}^{S}. The generating functions follow easily from Eqs. (2.5) and (2.6), 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 1. For example, the basic block of size 1 × 1 contains 2 squares, and the basic blocks of size 2 × 2 contain 4 squares.

The numbers of squares and L’s in all 2×n tilings for n = 1, …, 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 [19].

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

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}).

The sequence \{a_{n}/2\}_{n=0}^{∞} occurs in [19] as \underline{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. (3.2) and (3.3), we find that

T_{2,n}^{S} ∼ \frac{n(\sqrt{3} − 1)}{\sqrt{3}}(1 + \sqrt{3})^{n} and T_{2,n}^{L} ∼ \frac{n(\sqrt{3} − 1)}{3}(1 + \sqrt{3})^{n}.

Thus,

\frac{T_{2,n}^{S}}{T_{2,n}^{L}} ∼ \sqrt{3} and \frac{T_{2,n}^{S}}{3 · T_{2,n}^{L}} ∼ 1/\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.

4 Tiling 3×n boards

Tiling the 2×n board was straightforward because there were only basic blocks of size 2×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×n board we get basic blocks of all sizes. As before, we get one basic block of size 3×1, which consists of three squares. There are eight basic blocks of size 3× 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 3 shows the ten basic blocks of size 3×2.

Figure 3: The ten basic blocks of size 3×2

The 3×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×(k + 1) from those of size 3×k for k ≥ 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×1 area of the tiling as a cell to distinguish it from the square (tile).

Basic Block Creation (BBC) Algorithm:

1. Start with all basic blocks of size m × 2, and determine the possible compositions of the last column in terms of cells covered by L’s and squares.

2. For each different composition (up to horizontal symmetry), assign a type.

3. 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.

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 × (k + 1), it must have at least one L-shaped tile that spans the kth 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 kth column creates the basic block of size m × k from which the basic block of size m × (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 × (k + 1) are created from those of size m × k.

In the case of 3 × k basic blocks, these are the possible types:

• 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).

• Type II: The last column has two nonadjacent cells covered with squares (thus the center cell is covered by an L).

• Type III: The last column has two adjacent cells covered with squares (thus either the top or bottom cell is covered by an L).

The only other composition for a basic block of size 3 × 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 3, the first four blocks are of Type I, the 6th and 7th are of Type II, and the 5th and 8th 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 4 for a basic block of size 3×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.

Figure 4: Extension for Type I

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×k creates two basic blocks of size 3×(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 5, for one of the basic blocks of size 3×2.

Figure 5: Extension for Type II

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 6 shows the different possibilities.

Figure 6: Extension for Type III

Figure 7 shows the basic blocks of size 3×3. Note that the first fourteen blocks are of Type I, the 15th and 16th are of Type II and the last two are of Type III.

Figure 7: The basic blocks of size 3×3

The BBC algorithm can be visualized from Figures 7 and 8, which show the basic blocks of size 3×3 and 3×4, respectively. The first fourteen blocks in Figure 8 are the extensions of the fourteen Type I blocks of size 3×3. The next four blocks result from the two extensions each of the two Type II blocks (15th and 16th in Figure 7), 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.

Using the BBC algorithm, we obtain an explicit formula for the number of basic blocks of size 3×k, and from Eq. (2.1), a generating function for the number of tilings of size 3×n.

Theorem 4.1. The number of basic blocks of size 3×k is given by

B_{3,1} = 1, B_{3,2} = 10, and B_{3,k} = 10k − 12 for k ≥ 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}} and G_{T_{3}}(x) = \frac{(1 − x)^{2}}{1 − 3x − 7x^{2} + x^{3} − 2x^{4}} .

Figure 8: The basic blocks of size 3×4

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×k produce different basic blocks of size 3×(k+1) as the last columns differ (see Figures 4, 5, and 6). Extensions from different basic blocks of size 3×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×(k + 1) are created.

Let b_{k,t} be the number of basic blocks of size 3×k of type t = I, II, III, for k ≥ 2. Then, for k ≥ 3, B_{3,k} = b_{k,I} + b_{k,II} + b_{k,III}. From Figure 3 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 ≥ 3:

b_{k+1,III} = b_{k,III}(= … = b_{2,III} = 2), b_{k+1,II} = b_{k,III} = 2

and

b_{k+1,I} = b_{k,I} + 2b_{k,II} + 3b_{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 3). Thus,

G_{B_{3}}(x) = ∑_{k≥1} B_{3,k}x^{k} = x + 10x^{2} + ((∑_{k≥1}(10k − 12)x^{k}) − (−2x + 8x^{2}))
= 3x + 2x^{2} + 10 ∑_{k≥1} k x^{k} − 12 ∑_{k≥1} 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}} .

The result for G_{T_{3}}(x) follows from Eq. (2.2) and simplifying.

The values for T_{3,n} for n = 0, …, 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 [19].

Now we will count the number of L’s and squares in the tilings of a 3×n board. In light of Eqs. (2.4) and (2.6), 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 7 and 8 suggest that each of the basic blocks of size 3×k (except those for k = 1, 2) have exactly three squares. Thus, we will count the squares first, and then use Eq. (2.3) to obtain the result for the L’s.

Theorem 4.2. The generating functions for the numbers of squares and L-shaped tiles in all tilings of the 3×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}} 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}}.

Proof. Using the BBC algorithm, we can show that each basic block of size 3×k for k ≥ 3 contains exactly three squares. Figure 7 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 · B_{3,k} for k ≥ 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 · G_{B_{3}}(x) − 6x^{2} = 3x(1 + 6x + 3x^{2})/(1 − x)^{2}, where the last equality follows from Theorem 4.1. Using Eq. (2.5), 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 ≥ 3 (from Theorem 4.1). This result also holds for k = 2. Turning to the number of L’s, Eq. (2.3) gives T_{3,n}^{L} = n · T_{3,n} − T_{3,n}^{S}/3 for n ≥ 0. In terms of generating functions, this translates to G_{T_{3}^{L}}(x) = x · G′_{T_{3}}(x) − G_{T_{3}^{S}}(x)/3 (see for example [21], Section 2.2, Rule 2), which gives the desired result after simplification.

The values for n = 1, … 15 for the numbers of squares and L’s in 3×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 [19].

To answer the question about which type of tile dominates in the case of the 3×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 R and z_{0} is a pole of order r, 1 ≤ r < ∞, of f, then in some punctured disk centered at z_{0}, f has an expansion of the form

f(z) = ∑_{j=1}^{r} \frac{a_{−j}}{(z − z_{0})^{j}} + ∑_{j=0}^{∞} a_{j}(z − z_{0})^{j} = P P (f; z_{0}) + ∑_{j=0}^{∞} a_{j}(z − z_{0})^{j},

and the principal part P P (f; z_{0}) is given by (see [21], Eq. (5.2.4))

P P (f; z_{0}) = ∑_{n≥0} z^{n} \{∑_{j=1}^{r} \frac{(−1)^{j}a_{−j}}{z_{0}^{n+j}} \binom{n + j − 1}{j − 1}\} .  (4.1)

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 [14], Proposition 4.1.4 and proof thereof)

a_{−1} = Res (\frac{g}{h}, z_{0}) = 2\frac{g′(z_{0})}{h′′(z_{0})} − \frac{2}{3} \frac{g(z_{0})h′′′(z_{0})}{[h′′(z_{0})]^{2}} and a_{−2} = \frac{2g(z_{0})}{h′′(z_{0})}.  (4.2)

We are now ready to state the asymptotic result.

Corollary 4.3. The asymptotic expressions for the number of squares and L-shaped tiles in all tilings of the 3×n board are given by

T_{3,n}^{S} ∼ (0.234746 + 0.558529 n)c_{1}^{n} + (0.0641066 + 0.329504 n)c_{2}^{n},
T_{3,n}^{L} ∼ (−0.0782485 + 0.268102 n)c_{1}^{n} + (−0.0213689 + 0.460065 n)c_{2}^{n},

where c_{1} = 4.52104, c_{2} = −1.738438, and the error term is of order O ((0.504457 + ϵ)^{n}).

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 [21] twice to the poles at the real roots, we obtain

[z^{n}]f(z) = [z^{n}] (P P (f, z_{0}) + P P (f, z_{1})) + O ((\frac{1}{R} + ϵ)^{n})
= ∑_{i=0,1} (\frac{−a_{i,−1}}{z_{i}} + \frac{(n + 1)a_{i,−2}}{z_{i}^{2}} ) (\frac{1}{z_{i}} )^{n} + O ((\frac{1}{R} + ϵ)^{n}) ,

where a_{i,−j} denotes the coefficient a_{−j} for the pole z_{i}. Using Eqs. (4.1) and (4.2), 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.

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 4.3, we obtain

\frac{T_{3,n}^{S}}{T_{3,n}^{L}} ∼ \frac{0.5585}{0.2681} = 2.08318 and \frac{T_{2,n}^{S}}{3 · T_{2,n}^{L}} ∼ 0.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.

5 Tiling m×n boards

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 × 2 board, there are 32 basic blocks instead of the 10 basic blocks of size 3×2. Figure 9 shows the basic blocks up to symmetry (horizontal reflection), where all but the last four blocks also occur in reflected form.

Figure 9: Basic blocks of size 4×2

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.

Table 1: The nine types of end shapes for 4×k basic blocks

I  II  III  IV  V  VI  VII VIII  IX

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 4 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.

Table 2: Results of the BBC algorithm

Extension Type

Type I II III IV V VI VII VIII IX
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 - - - - - - -  -  -

Let b̃_{k,t} denote the number of basic blocks of size 4×k of type t = I, II, … IX, for k ≥ 2. From Figure 9, we can read off the values for b̃_{2,t}, and then, using Table 2, we can compute the values for b̃_{3,t}, which are given in Table 3.

Table 3: Initial conditions for b̃_{n,t}

Type I II III IV V VI VII VIII IX total
b̃_{2,t} 2 4 4 3 1 2 4  8 4 32
b̃_{3,t} 10 16 50 20 0 0 6 10 18 130

Using Table 2 we can also read off a system of recurrence relations for b̃_{n,t} for t = I, …, IV, V II, V III, and IX. For example, Column 4 of Table 2 gives this relation:

b̃_{n+1,IV} = 2b̃_{n,I} + b̃_{n,II} + b̃_{n,III} + 2b̃_{n,V II},

since b̃_{n,V} = b̃_{n,V I} = 0 for n > 2. Adding the equation

B_{4,n+1} = b̃_{n+1,I} + b̃_{n+1,II} + b̃_{n+1,III} + b̃_{n+1,IV} + b̃_{n+1,V II} + b̃_{n+1,V III} + b̃_{n+1,IX},

and using the initial conditions for n = 3, we can use the Mathematica function GeneratingFunction from the package DiscreteMath^{‵}RSolve to compute the generating function for B_{4,n} for n ≥ 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 × n tilings, where the generating function for T_{4,n} follows from Eq. (2.2).

Theorem 5.1. The generating function for the number basic blocks and the number of tilings of the 4×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 − 4z − 6z^{2} − 10z^{3} − 8z^{4} − 4z^{5}}{1 − 5z − 34z^{2} − 6z^{3} + 72z^{4} + 28z^{5} − 74z^{6} + 10z^{7} + 4z^{8} + 4z^{9}} .

The values for n = 0, …, 15 for the number of tilings of the 4 × 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 [15, 16, 17]. Similar to the extension process described in Section 4, 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.

6 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.

References

[1] A. T. Benjamin and J. J. Quinn. Proofs that really count, Vol. 27 of The Dolciani Mathematical Expositions. Mathematical Association of America, Washington, DC, 2003.

[2] R. C. Brigham, R. M. Caron, P. Z. Chinn, and R. P. Grimaldi. A tiling scheme for the Fibonacci numbers. J. Recreational Math., 28 (1996) 10–17.

[3] R. C. Brigham, P. Z. Chinn, L. M. Holt, and R. S. Wilson. Finding the recurrence relation for tiling 2 × n rectangles. Congr. Numer., 105 (1994) 134–138.

[4] F. Cazals. Monomer-dimer tilings.

    http://citeseer.ist.psu.edu/cazals97monomerdimer.html, 1997.

[5] R. Grimaldi. Discrete and Combinatorial Mathematics, 5th Edition. Pearson Education, Inc., 2004.

[6] E. O. Hare. Tiling a 3 × n area with Cuisenaire rods of length less than or equal to k. Congr. Numer., 105 (1994) 33–45.

[7] E. O. Hare and P. Z. Chinn. Tiling with Cuisenaire rods. In Applications of Fibonacci Numbers, Vol. 6 (Pullman, WA, 1994), 165–171. Kluwer Acad. Publ., Dordrecht, 1996.

[8] S. Heubach. Tiling an m-by-n area with squares of size up to k-by-k with m ≤ 5. Congr. Numer., 140 (1999) 43–64.

[9] S. Heubach and P. Z. Chinn. Patterns arising from tiling rectangles with 1-by-1 and 2-by-2 squares. Congr. Numer., 150 (2001) 173–192.

[10] R. Hochberg and M. Reid. Tiling with notched cubes. Discrete Math., 214 (2000) 255–261.

[11] P. W. Kasteleyn. The statistics of dimers on a lattice. Physica, 27 (1961) 1209–1225.

[12] R. Kenyon. Local statistics of lattice dimers. Ann. Inst. H. Poincaré Probab. Statist., 33 (1997) 591–618.

[13] C. Kenyon, D. Randall, and A. Sinclair. Approximating the number of monomer-dimer coverings of a lattice. J. Statist. Phys., 83 (1996) 637–659.

[14] J. E. Marsden and M. J. Hoffman. Basic Complex Analysis, 2nd Edition. W. H. Freeman and Company, 1987.

[15] L. Martinelli, D. Merlini, et.al. A software to solve strip tiling problems. Formal Power Series and Algebraic Combinatorics (FPSAC, Moscow 2000), 801–805, Springer Berlin, 2000.

[16] D. Merlini, R. Sprugnoli, and M. C. Verri. Strip tiling and regular grammars. Theoretical Computer Science, 242 (2000) 109–124.

[17] D. Merlini, R. Sprugnoli, and M. C. Verri. A strip-like tiling algorithm. Theoretical Computer Science, 282 (2002) 337–352.

[18] D. G. Rogers. An application of renewal sequences to the dimer problem. In Combinatorial mathematics, VI (Proc. Sixth Austral. Conf., Univ. New England, Armidale, 1978), volume 748 of Lecture Notes in Math., 143–153. Springer, Berlin, 1979.

[19] N. J. A. Sloane. The on-line encyclopedia of integer sequences. published electronically

at http://www.research.att.com/∼njas/sequences/, 2007.

[20] H. N. V. Temperley and M. E. Fisher. Dimer problem in statistical mechanics, an exact result. Philosophical Magazine, 6 (1961) 1061–1063.

[21] H. S. Wilf. Generatingfunctionology, 2nd Edition. Academic Press, Inc., 1994.

2000 Mathematics Subject Classification: Primary 52C20; Secondary 52C22. Keywords: Tilings, trominoes, recurrence relations, generating functions.

(Concerned with sequences \underline{A028859} and \underline{A077917}.)

Received April 21 2006; revised version received February 28 2007. Published in Journal of Integer Sequences, March 19 2007.

Return to Journal of Integer Sequences home page.