Counting Colorful Tilings of Rectangular Arrays

Kathryn Haymaker and Sara Robertson Villanova University Department of Mathematics and Statistics St. Augustine Center 305 800 E. Lancaster Avenue Villanova, PA 19085 USA

                kathryn.haymaker@villanova.edu
                    srober23@villanova.edu

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

1 Introduction

How many ways are there to tile a rectangular board with painted squares and dominoes, when there are a available colors for the squares and b available colors for the dominoes? There is no closed-form expression for the number of tilings of an m×n board with dominoes and squares, but the problem has been extensively studied in the area of mathematical physics, where the pieces are called monomers and dimers [9, 4, 5, 6, 2, 3]. Jerrum [7] shows that the general monomer-dimer problem is computationally intractable.

The number of ways to tile a 2 × n board using squares and dominoes is given by the sequence 1, 2, 7, 22, 71, … (\underline{A030186}). This sequence, as well as its corresponding recursion, have been well-studied [9, 4]. In a generalization of this result, Katz and Stenson found a recursion for the number of painted tilings of a 2 × n board [8]. Using a different approach, we obtain a recursion for the number of tilings of a 3 × n board with painted dominoes and squares. We begin by introducing the technique pioneered by Read to count unpainted square-domino tilings [10], and we demonstrate a modification of that method to obtain a generating function for the number of tilings of a 2×n board with painted squares, dominoes, and I-trominoes (also called trimers). Following the convention in earlier work [10], in this paper we will refer to I-trominoes as simply trominoes—see Figure 1.

Figure 1: A square, domino, and I-tromino (which we refer to as a ‘tromino’, excluding the L-tromino shape in this work).

We then obtain the recursion for the number of tilings of a 3 × n board with painted squares and dominoes. The final section of the paper generalizes the approach of Ahrens [1] for counting the number of painted square-domino tilings of general rectangular arrays.

2 Coverings of 2 × n boards with squares, dominoes, and trominoes

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

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

Theorem 1. The following recurrence relation holds for n ≥ 4:

s_{n}^{a,b,c} = (a^{2} + 2b)s_{n−1}^{a,b,c} + (a^{2}b + ac)s_{n−2}^{a,b,c} + (a^{3}c + 3abc − b^{3} + 2c^{2})s_{n−3}^{a,b,c}
+ (a^{2}c^{2} − ab^{2}c − 2bc^{2})s_{n−4}^{a,b,c} + (b^{2}c^{2} − ac^{3})s_{n−5}^{a,b,c} − c^{4}s_{n−6}^{a,b,c}

with the following initial conditions:

s_{−2}^{a,b,c} := 0
s_{−1}^{a,b,c} := 0
s_{0}^{a,b,c} = 1
s_{1}^{a,b,c} = a^{2} + b
s_{2}^{a,b,c} = a^{4} + 4a^{2}b + 2b^{2}
s_{3}^{a,b,c} = a^{6} + 7a^{4}b + 11a^{2}b^{2} + 3b^{3} + 2a^{3}c + 4abc + c^{2}.

Proof. We begin by determining the finite number of possible profiles which may occur on a 2 × n board at any stage in the tiling process. Tiling begins on the left-hand-side of the board; the profiles describe the boundary preceding the portion of the board that remains untiled. Each profile defines a target square, the topmost uncovered square in the leftmost column which has yet to be completely tiled, indicated using an *. Placing either a square, domino, or a tromino on the target square results in a new profile.

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

Each profile can be expressed as a generating function in terms of the addition of the necessary tile to those profiles from which it is derived. For example, as profile D can only be created by adding a tromino to profile A, it follows that D(x, y, z) = zA(x, y, z). By dropping the arguments, we obtain the following simplified equations:

\begin{aligned}A & = 1 + xA + xB + yC + zD + yE + xF \\ B & = xA + yD + zE \\ C & = yA + yB + xD + xE + zF \\ D & = zA \\ E & = zB + xC + yF \\ F & = zC. \end{aligned}

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

As D, E, and F can be written in terms of A, B, and C, substitutions can be made to produce the simplified equations:

\begin{aligned}A(1 − x − z^{2}) & = 1 + B(x + xz) + C(y + xy + y^{2}z + xz) \\ B(1 − z^{2}) & = A(x + yz) + C(xz + yz^{2}) \\ C(1 − x^{2} − xyz − z^{2}) & = A(y + xz) + B(y + xz). \end{aligned}

Figure 2: Profiles for 2 × n case with squares, dominoes, and trominoes.

Ultimately, it is only necessary to solve for A(x, y, z), as this represents all tilings that begin with the vertical profile. Thus,

A(x, y, z) = \frac{U}{V}

where U = 1 − x − yz − z^{2}, and

V =1 + x^{2}yz − x^{2}z^{2} − y^{3}z − y^{2}z^{2} + yz^{3} + z^{4} + x^{3} − xy^{2} − 3xyz + 2xz^{2}
− y^{2} − yz − 2z^{2} − 2x

As our ultimate goal is to create a generating function for a recursion which counts the number of painted tilings for a 2 × n board, we need our function to account for the length of our board, n. To do this, we first replace x by bu^{2}, y by au, and z by cu^{3}. Now, the power of u will account for the number of ‘spaces’ on the board the tile occupies. The total number of spaces in a 2 × n board is 2n, so the coefficient of u^{2n} will count the number of tilings of this board. Thus, every power of u will be even, so we can replace u^{2} by t, where the power of t will now correspond to the length of the board, n.

This produces the generating function

A(a, b, c, t) = \frac{U}{V}

where U = 1 − bt − act^{2} − c^{2}t^{3}, and

\begin{matrix}V = & 1 − (a^{2} + 2b)t − (a^{2}b + ac)t^{2} − (a^{3}c − b^{3} + 3abc + 2c^{2})t^{3} \\ − (a^{2}c^{2} − ab^{2}c − 2bc^{2})t^{4} − (b^{2}c^{2} − ac^{3})t^{5} + c^{4}t^{6}. \end{matrix}  (1)

We will use the notation V = 1 − V′, where V′ is the polynomial in a, b, c and t as above.

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

Using a similar procedure to Read [10, pp. 55–56], we can obtain a recurrence relation from Equation (1). Let s_{n}(a, b, c) denote the polynomial corresponding to the number of possible placements of a squares, b dominoes, and c trominoes on a 2 × n board. Then

A(a, b, c, t) = ∑ s_{n}(a, b, c)t^{n}

and from Equation (1) we obtain

∑ s_{n}(a, b, c)t^{n} = \frac{1 − bt − act^{2} − c^{2}t^{3}}{V} .

By multiplying both sides by V, we obtain

(1 − V′) ∑ s_{n}(a, b, c)t^{n} = 1 − bt − act^{2} − c^{2}t^{3},

which we can use to solve for the coefficients s_{n}(a, b, c):

∑ s_{n}(a, b, c)t^{n} = (1 − bt − act^{2} − c^{2}t^{3}) + V′ ∑ s_{n}(a, b, c)t^{n}.

For n ≥ 4, the right-hand side of this equation will give a recursive definition for the coefficient of t^{n}. We can distribute V′ over the sum ∑ s_{n}(a, b, c)t^{n} (denoted below as ∑ s_{n}t^{n}) and re-index as follows:

∑_{n≥4} s_{n}t^{n} = (a^{2} + 2b)t ∑_{N≥3} s_{N}t^{N} + (a^{2}b + ac)t^{2} ∑_{N≥2} s_{N}t^{N} + ⋯ + c^{4}t^{6} ∑_{N≥−2} s_{N}t^{N}

= (a^{2} + 2b) ∑_{n≥4} s_{n−1}t^{n} + ⋯ + c^{4} ∑_{n≥4} s_{n−6}t^{n},

where s_{n}(a, b, c) := 0 for all n ≤ 0. By gathering the coefficients of t^{n}, we obtain the following expression for s_{n}(a, b, c):

s_{n}(a, b, c) = (a^{2} + 2b)s_{n−1}(a, b, c) + (a^{2}b + ac)s_{n−2}(a, b, c) + (a^{3}c + 3abc − b^{3} + 2c^{2})s_{n−3}(a, b, c)
+ (a^{2}c^{2} − ab^{2}c − 2bc^{2})s_{n−4}(a, b, c) + (b^{2}c^{2} − ac^{3})s_{n−5}(a, b, c) − c^{4}s_{n−6}(a, b, c).

A case-by-case analysis gives the initial conditions in the theorem.

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

Corollary 2. The recurrence relation for tilings of a 2 × n board with squares, dominoes, and trominoes is

S_{n} = 3S_{n−1} + 2S_{n−2} + 5S_{n−3} − 2S_{n−4} − S_{n−6},

with initial conditions

S_{0} = 1, S_{1} = 2, S_{2} = 7, S_{3} = 29, S_{4} = 109.

Remark 3. The sequence in Corollary 2 is sequence \underline{A278815} in the OEIS.

3 A recurrence relation for 3 × n boards

Now that we have seen an example of Read’s method applied to the case of painted squares, dominoes, and trominoes, we return to the original question of counting the number of tilings of a 3 × n board with only painted squares and dominoes. For the sake of space, we refer to “The dimer problem for narrow rectangular arrays” for the profiles in the 3 × n case, and for the profile equations [10, Fig. 5 and Eq. (3.1)].

Using the same notation as in Section 2, A(x, t) denotes the generating function for the number of tilings of a 3 × n board with squares and dominoes, where the power of x corresponds to the number of dominoes and the power of t corresponds to the width of the rectangle, n. The following result is by Read [10].

Theorem 4 (Read, 1982). The generating function for tilings of a 3 × n board with squares and dominoes is

A(x, t) = \frac{(1 − 2xt − x^{3}t^{2})(1 + xt − x^{3}t^{2})}{V},

where

V = 1−(1+3x)t−(2x+7x^{2}+5x^{3})t^{2}−(x^{2}+x^{3}−2x^{4})t^{3}+(2x^{4}+3x^{5}+5x^{6})t^{4}−(x^{6}−x^{7})t^{5}−x^{9}t^{6}.

The recurrence for P_{n} is

P_{n} = 4P_{n−1} + 14P_{n−2} − 10P_{n−4} + P_{n−6},

with initial conditions

P_{0} = 1, P_{1} = 3, P_{2} = 22, P_{3} = 823, P_{4} = 5096.

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

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

Theorem 5. The following recurrence relation holds for n ≥ 5:

τ_{n}^{a,b} =(a^{3} + 3ab)τ_{n−1}^{a,b} + (2a^{4}b + 7a^{2}b^{2} + 5b^{3})τ_{n−2}^{a,b}+
(a^{5}b^{2} + a^{3}b^{3} − 2ab^{4})τ_{n−3}^{a,b} − (2a^{4}b^{4} + 3a^{2}b^{5} + 5b^{6})τ_{n−4}^{a,b}+
(a^{3}b^{6} − ab^{7})τ_{n−5}^{a,b} + b^{9}τ_{n−6}^{a,b},

with the following initial conditions:

τ_{−1}^{a,b} := 0
τ_{0}^{a,b} = 1
τ_{1}^{a,b} = a^{3} + 2ab
τ_{2}^{a,b} = a^{6} + 7a^{4}b + 11a^{2}b^{2} + 3b^{3}
τ_{3}^{a,b} = a^{9} + 12a^{7}b + 44a^{5}b^{2} + 56a^{3}b^{3} + 18ab^{4}
τ_{4}^{a,b} = a^{12} + 17a^{10}b + 102a^{8}b^{2} + 267a^{6}b^{3} + 302a^{4}b^{4} + 123a^{2}b^{5} + 11b^{6}.

Proof. Using Read’s equation [10, Eq. (3.5)], we modify the change of variable procedure to account for a available square colors and b available domino colors with similar reasoning to that used in Theorem 1. Replacing x by bu^{2} and y by au, and then u^{3} by t, we obtain

A(a, b, t) = \frac{U}{V} ,  (2)

where U = (1 − b^{3}t^{2} − 2abt)(1 − b^{3}t^{2} + abt), and

V =1 − t(a^{3} + 3ab) − t^{2}(2a^{4}b + 7a^{2}b^{2} + 5b^{3}) − t^{3}(a^{5}b^{2} + a^{3}b^{3} − 2ab^{4})+
t^{4}(2a^{4}b^{4} + 3a^{2}b^{5} + 5b^{6}) − t^{5}(a^{3}b^{6} − ab^{7}) − t^{6}b^{9}.

Denote V by 1 − V′.

Equation (2) is a generating function where the coefficient of t^{n} is the number of tilings of a 3×n board with squares and dominoes, with a available colors of squares and b available colors of dominoes.

Solving for the coefficient of t^{n} in Equation (2) will result in the desired recursion for τ_{n}^{a,b}. Using a method analogous to the proof of Theorem 1, we write A(a, b, t) = ∑_{n≥0} τ_{n}(a, b)t^{n}

so that Equation (2) becomes

∑_{n≥0} τ_{n}(a, b)t^{n} = \frac{U}{V} .

Therefore, multiplying both sides by V and solving for ∑_{n≥0} τ_{n}(a, b)t^{n}, we obtain

∑_{n≥0} τ_{n}(a, b)t^{n} = U + V′ (∑_{n≥0} τ_{n}(a, b)t^{n}) .

Since we seek a recursive expression for τ_{n}(a, b), we will focus on n ≥ 5, where the terms V′ ∑ τ_{n}(a, b)t^{n} appear.

As in the proof of Theorem 1, by distributing V′ and gathering coefficients of t^{n} on the right-hand side, we obtain the following recursion:

τ_{n}(a, b) =(a^{3} + 3ab)τ_{n−1}(a, b) + (2a^{4}b + 7a^{2}b^{2} + 5b^{3})τ_{n−2}(a, b)+
(a^{5}b^{2} + a^{3}b^{3} − 2ab^{4})τ_{n−3}(a, b) − (2a^{4}b^{4} + 3a^{2}b^{5} + 5b^{6})τ_{n−4}(a, b)+
(a^{3}b^{6} − ab^{7})τ_{n−5}(a, b) + b^{9}τ_{n−6}(a, b).

The initial conditions for the recurrence relation are calculated using case-by-case analysis.

While the method in this section is useful to obtain an explicit recursion for τ_{n}^{a,b}, a different approach introduced by Ahrens [1] gives a way to calculate the number of tilings for any rectangular array of dimensions m×n. (Although it does not give a single closed-form expression for all m, n.) In the next section we generalize the work of Ahrens to include the parameters a and b. However, the subsequent technique cannot be used to obtain the results in Section 2 on tilings with squares, dominoes, and trominoes. A more detailed contrast of the two enumeration methods will be discussed in Section 4.

4 Tilings of m × n boards using transfer matrices

While the approach in the previous section considered building tilings horizontally using ‘profiles’, the techniques in this section will build tilings vertically. Of course, the number of tilings of a 3 × n board will be the same as the number for an m × 3 board when m = n, so we will interchange the fixed dimension for the rectangular boards in this section.

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

As an example, Figure 3 gives all tilings of a 2 × 3 board with squares and dominoes that have signature i = 7, i.e., i_{b} = 111.

Figure 3: The five 2 × 3 tilings with signature i = 7.

Ahrens defines a transfer matrix to be a 2^{n} × 2^{n} matrix containing entries a_{i,j}, where a_{i,j} counts the number of ways that an m × n tiling with binary signature i_{b} can become an (m + 1) × n tiling with binary signature j_{b} by the addition of squares or dominoes in the final row [1]. In this process, we consider a square to be an ‘empty’ space, so a square in row m can be covered by a domino that spans from row m to row m + 1 in the extended tiling. The transfer matrix that Ahrens produces [1] has entries in ℤ^{+}.

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

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

Figure 4: Extending 2 × 3 tilings with a signature of 7 to 3 × 3 tilings with a signature of 0.

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

Let A_{n} denote the transfer matrix for m × n boards. The m × 1 transfer matrix is

A_{1} = [\begin{matrix}a & \frac{b}{a} \\ a & 0 \end{matrix}] .

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

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

Figure 5: Images illustrating the entries a_{i,j} for the m × 2-board transfer matrix.

The transfer matrix for m × 2 painted tilings is given below:

A_{2} = [\begin{matrix}a^{2} & b & b & b + \frac{b^{2}}{a^{2}} \\ a^{2} & 0 & b & b \\ a^{2} & b & 0 & b \\ a^{2} & 0 & 0 & b \end{matrix} ] .

4.1 Recursive construction of the transfer matrix

The 2^{n} × 2^{n} transfer matrix that describes the transitions from an (m − 1) × n board to an m × n board can be constructed recursively from the 2^{i} × 2^{i} transfer matrices for i < n. In Table 4.1 we provide a key to this recursive construction. This is a generalization of the process detailed in Ahrens [1, p. 279]. Throughout this subsection we use i for the binary representation of the integer i, instead of i_{b}.

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

i/j  j ≡ 0 (mod 4) j ≡ 1 (mod 4) j ≡ 2 (mod 4) j ≡ 3 (mod 4)
i ≡ 0 (mod 2) a_{ij} = a · a_{i′j′} a_{ij} = \frac{b}{a} · a_{i′j′} a_{ij} = a · a_{i′j′} a_{ij} = \frac{b}{a}a_{i′j′} + b · a_{i′′j′′}
i ≡ 1 (mod 2) a_{ij} = a · a_{i′j′} 0  a_{ij} = a · a_{i′j′} a_{ij} = b · a_{i′′j′′}

Table 1: Transfer matrix construction

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

The remaining entries can be calculated in a similar way. We will explain the case of i ≡ 0 (mod 2), j ≡ 3 (mod 4) since it also requires the term a_{i′′j′′}.

Since j ≡ 3 (mod 4), the binary representation of j ends in 11. There are two ways to obtain an ending of 11 in j, given that i ends in 0—either have (i) a vertical domino that ends in the last position of j, or (ii) a horizontal domino that ends in the last position of j.

Case (i) can occur in \frac{b}{a}a_{i′j′} ways, since we can cover the final 0 (square) in i with a vertical domino to obtain the final 1 in j. There are \frac{b}{a} ways to complete this extension of the last position of i to the last position of j. The remaining positions are accounted for by the term a_{i′j′}, which counts the ways to extend a tiling with signature i′ to one with signature j′. Therefore there are a total of \frac{b}{a}a_{i′j′} ways.

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

4.2 Enumeration using the transfer matrix

Using the recursive construction described in the previous section, we obtain A_{3}, the transfer matrix for m × 3 rectangular boards:

A_{3} = [ \begin{matrix}a^{3} & ab & ab & \frac{b^{2}}{a} + ab & ab & \frac{b^{2}}{a} & \frac{b^{2}}{a} + ab & \frac{b^{3}}{a^{3}} + 2\frac{b^{2}}{a} \\ a^{3} & 0 & ab & ab & ab & 0 & \frac{b^{2}}{a} + ab & \frac{b^{2}}{a} \\ a^{3} & ab & 0 & ab & ab & \frac{b^{2}}{a} & ab & 2\frac{b^{2}}{a} \\ a^{3} & 0 & 0 & ab & ab & 0 & ab & \frac{b^{2}}{a} \\ a^{3} & ab & ab & \frac{b^{2}}{a} + ab & 0 & 0 & ab & \frac{b^{2}}{a} \\ a^{3} & 0 & ab & ab & 0 & 0 & ab & 0 \\ a^{3} & ab & 0 & ab & 0 & 0 & ab & \frac{b^{2}}{a} \\ a^{3} & 0 & 0 & ab & 0 & 0 & ab & 0 \end{matrix} ] .

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

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

v^{(m)} = v^{(0)}(A_{3})^{m}.  (3)

More generally, let A_{n} be the transfer matrix for an m × n board, obtained recursively. The number of ways to tile an m × n board with painted squares and dominoes is the sum of the entries of v^{(m)}, where

v^{(m)} = v^{(0)}(A_{n})^{m}.

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

Ahrens [1] provides an algorithm to speed up the computation time for the expression above, and we note that the algorithm could be adjusted in a straightforward way for the colorful tiling case.

Using 3, determining the number of painted tilings of an m × 3, or equivalently a 3 × n board, is computationally straightforward. For instance, using A_{3} as defined previously, we can easily calculate the number of tilings of a 3 × 2 board:

v^{(2)} = v^{(0)}(A_{3})^{2}

= [ 0 0 0 0 0 0 0 1 ] [ \begin{matrix}a^{3} & ab & ab & \frac{b^{2}}{a} + ab & ab & \frac{b^{2}}{a} & \frac{b^{2}}{a} + ab & \frac{b^{3}}{a^{3}} + 2\frac{b^{2}}{a} \\ a^{3} & 0 & ab & ab & ab & 0 & \frac{b^{2}}{a} + ab & \frac{b^{2}}{a} \\ a^{3} & ab & 0 & ab & ab & \frac{b^{2}}{a} & ab & 2\frac{b^{2}}{a} \\ a^{3} & 0 & 0 & ab & ab & 0 & ab & \frac{b^{2}}{a} \\ a^{3} & ab & ab & \frac{b^{2}}{a} + ab & 0 & 0 & ab & \frac{b^{2}}{a} \\ a^{3} & 0 & ab & ab & 0 & 0 & ab & 0 \\ a^{3} & ab & 0 & ab & 0 & 0 & ab & \frac{b^{2}}{a} \\ a^{3} & 0 & 0 & ab & 0 & 0 & ab & 0 \end{matrix} ]^{2}

= [ a^{3} 0 0 ab 0 0 ab 0 ] [ \begin{matrix}a^{3} & ab & ab & \frac{b^{2}}{a} + ab & ab & \frac{b^{2}}{a} & \frac{b^{2}}{a} + ab & \frac{b^{3}}{a^{3}} + 2\frac{b^{2}}{a} \\ a^{3} & 0 & ab & ab & ab & 0 & \frac{b^{2}}{a} + ab & \frac{b^{2}}{a} \\ a^{3} & ab & 0 & ab & ab & \frac{b^{2}}{a} & ab & 2\frac{b^{2}}{a} \\ a^{3} & 0 & 0 & ab & ab & 0 & ab & \frac{b^{2}}{a} \\ a^{3} & ab & ab & \frac{b^{2}}{a} + ab & 0 & 0 & ab & \frac{b^{2}}{a} \\ a^{3} & 0 & ab & ab & 0 & 0 & ab & 0 \\ a^{3} & ab & 0 & ab & 0 & 0 & ab & \frac{b^{2}}{a} \\ a^{3} & 0 & 0 & ab & 0 & 0 & ab & 0 \end{matrix} ]

= [ \begin{matrix}a^{6} + 2a^{4}b \\ a^{4}b + a^{2}b^{2} \\ a^{4}b \\ a^{3}(\frac{b^{2}}{a} + ab) + 2a^{2}b^{2} \\ a^{4}b + a^{2}b^{2} \\ a^{2}b^{2} \\ a^{3}(\frac{b^{2}}{a} + ab) + 2a^{2}b^{2} \\ a^{3}(\frac{b^{3}}{a^{3}} + \frac{2b^{2}}{a}) + 2b^{3} \end{matrix} ]^{T} .

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

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

5 Conclusion

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

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

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

References

[1] J. H. Ahrens, Paving the chessboard, J. Combin. Theory Ser. A 31 (1981), 277–288.

[2] I. Beichl, D. P. O’Leary, and F. Sullivan, Approximating the number of monomer-dimer coverings in periodic lattices, Phys. Review E 64 (2001), 1–6.

[3] A. Erickson, F. Ruskey, and J. Woodcock, Monomer-dimer tatami tilings of rectangular regions, Electronic J. Combin. 18 (2011), #P109.

[4] R. Grimson, Exact formulas for 2-by-n arrays of dumbbells, J. Math. Phys. 15 (1974), 214–216.

[5] J. Hock and R. McQuistan, A note on the occupational degeneracy for dimers on a saturated two-dimensional lattice space, Disc. Appl. Math. 8 (1984), 101–104.

[6] H. Hosoya and A. Motoyama, An effective algorithm for obtaining polynomials for dimer statistics, J. Math. Phys. 26 (1985), 157–167.

[7] M. Jerrum, Two-dimensional monomer-dimer systems are computationally intractable, J. Stat. Phys. 48 (1987), 121–134.

[8] M. Katz and C. Stenson, Tiling a (2 × n)-board with squares and dominoes, J. Integer Sequences 12 (2009), Article 09.2.2.

[9] R. B. McQuistan and S. J. Lichtman, Exact recursion relation for 2-by-N arrays of dumbbells, J. Math. Phys. 11 (1970), 3095–3099.

[10] R. Read, The dimer problem for narrow rectangular arrays: A unified method of solution, and some extensions, Aequationes Math. 24 (1982), 47–65.

2010 Mathematics Subject Classification: Primary 05B45; Secondary 05A15, 52C20. Keywords: domino, tiling, I-tromino, transfer matrix.

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

Received December 6 2016; revised version received April 11 2017. Published in Journal of Integer Sequences, June 24 2017.

Return to Journal of Integer Sequences home page.