Fault-Free Tilings of the 3 × n Rectangle With Squares and Dominos

Oluwatobi Jemima Alabi Government Science Secondary School Pyakasa, Abuja Nigeria

                    tobialabi609@gmail.com

Greg Dresden Washington & Lee University Lexington, VA 24450 USA

                       dresdeng@wlu.edu

Abstract A (completely) fault-free tiling of a board is a tiling with no vertical or horizontal faults. We find a fourth-order recurrence relation for the number of ways to tile such a board using squares and dominos, and we do the same for a vertical-fault-free board (which could have horizontal faults).

1 Introduction

Tiling problems appear frequently in the mathematical literature. McQuistan and Lichtman [3] found the number of tilings of a 2 × n rectangle with squares and dominos (given by \underline{A030186}), and Read [5] did the same for 3 × n (see \underline{A033506}). And of course, the tilings of a 1 × n rectangle are counted by the Fibonacci numbers.

One variation on these kinds of tiling problems is to ask for fault-free tilings, in which there are no “clean breaks” of the tiling along any horizontal or vertical line.

Figure 1: A 3 × 6 tiling with a horizontal fault but no vertical fault.

Figure 1 gives a tiling of a 3 × 6 rectangle (using only dominos) which has a horizontal fault but no vertical fault (we would call this a vertical-fault-free tiling).

Recent articles on fault-free tilings with dominos include Graham’s paper [2] on rectangles, a preprint by Montelius [4] which expands on Graham’s work to consider cylinders, tori, and Möbius strips, and a paper by Atkinson and Lunnon [1] which enumerates fault-free rectangles in which each fault crosses a fixed number of dominos. Graham points out that there does not exist a fault-free tiling of a 3 × n rectangle using only dominos. However, if we use dominos and squares, there are quite a few fault-free tilings, and that is the subject of our paper. Here is one fault-free tiling:

Figure 2: A 3 × 6 tiling which has neither vertical nor horizontal faults.

In what follows, we will count the number of such tilings (with dominos and squares) of the 3 × n rectangle. We let U_{n} represent the number of completely fault-free tilings, and V_{n} represent the number of vertical-fault-free tilings. (We are using the expression completely fault-free, instead of just fault-free, to avoid confusion with the expression vertical-fault-free. Keep in mind that most authors use the expression fault-free instead of completely fault-free.)

2 Initial work on counting the tilings

Let us look at some initial values for U_{n} and V_{n}. Fortunately, the tilings at n = 1 are easy. Figure 3 shows all possible tilings, and so we see that U_{1} = 0 and V_{1} = 3.

Figure 3: All possible tilings of a 3 × 1 rectangle with squares and dominos.

For n = 2, all the vertical-fault-free tilings are given in Figure 4. Since none of them are also horizontally-fault-free, we have U_{2} = 0 and V_{2} = 13.

Figure 4: All possible vertical-fault-free tilings of a 3 × 2 rectangle.

For n = 3 and n = 4 there are exactly two completely fault-free tilings as shown in Figure 5, so U_{3} = U_{4} = 2. (It turns out that V_{3} = 26 and V_{4} = 66 but we will show that later.)

Figure 5: The completely fault-free tilings of a 3 × 3 and 3 × 4 rectangle.

Now, to tile a fault-free 3 × n board, we must take three very important issues into consideration.

1. First, for a 3×n tiling to be vertical-fault-free, there must not be any vertical dominoes in the middle of the board; they can only be at the beginning or end (if at all). As seen in Figure 6, using vertical dominos in the middle of a tiling causes vertical faults (represented by dashed lines).

Figure 6: Interior vertical dominos create interior vertical faults.

2. Second, for a tiling to be horizontal-fault-free, then since there can not be vertical dominos in the middle we must instead have (unaligned) vertical dominos on the ends, as shown in the two diagrams in Figure 7.

Figure 7: Vertical dominos on each end are required for completely fault-free tilings.

3. Finally, there are six recurring profiles which we will use to count tilings for n ≥ 3, based on what happens when one tries to break the tiling, vertically, at position m for 1 ≤ m ≤ n − 1. Figure 8 illustrates the six profiles (similar to those used by Read in [5]), which we arbitrarily label A through F.

Figure 8: Six profiles in which a tiling fails to have a vertical fault.

3 Vertical-fault-free tilings

Let us now determine the number of vertical-fault-free tilings V_{n} for a 3 × n rectangle. From our drawings earlier, we know that V_{1} = 3 and V_{2} = 13.

First, we define A_{n}, B_{n}, …, F_{n} to be the number of ways to tile a vertical-fault-free 3×n rectangle ending in profiles A, B, …, F from Figure 8, respectively, where the one or two rectangles in each profile extend one unit beyond the end on the right. For example, A_{1} = 2 and A_{2} = 4, thanks to the tilings in Figure 9, and B_{1} = 1 and B_{2} = 5 as seen in Figure 10. Since profile C is just a reflection (around a horizontal axis) of profile A, then we also have C_{1} = 2 and C_{2} = 4.

Figure 9: A_{1} = 2 and A_{2} = 4; flip the picture to see that C_{1} = 2 and C_{2} = 4.

Figure 10: B_{1} = 1 and B_{2} = 5.

But what about profile D? If we study Figure 11, we see that D_{2} = 2 and D_{3} = 4, and furthermore we can see that in general, D_{n} = A_{n−1} because any profile-D tiling must have a horizontal domino (in orange) above the two horizontal dominos (in yellow) as shown, to avoid a vertical fault to the left of those two horizontal dominos.

Figure 11: D_{2} = A_{1} = 2 and D_{3} = A_{2} = 4.

Glancing back at Figure 8, we see that we can find other recurrence relations for these six sequences A_{n}, B_{n}, …, F_{n}. If we look at Figure 12, we can see that a tiling that ends in profile A must, in order to prevent a vertical fault before that yellow domino, have either one or two (orange) horizontal dominos below, and slightly to the left, of that original (yellow) horizontal domino, which means that A_{n} must equal B_{n−1} + C_{n−1} + D_{n−1}.

Figure 12: Illustrating that A_{n} = B_{n−1} + C_{n−1} + D_{n−1}.

We have shown that D_{n} = A_{n−1} and that A_{n} = B_{n−1} + C_{n−1} + D_{n−1}. Using similar drawing arguments, we arrive at the six recurrence relations shown in (1), which all hold for n ≥ 2.

\begin{aligned}A_{n} & = B_{n−1} + C_{n−1} + D_{n−1} \\ B_{n} & = A_{n−1} + C_{n−1} + E_{n−1} \\ C_{n} & = A_{n−1} + B_{n−1} + F_{n−1} \end{aligned}  \begin{aligned}D_{n} & = A_{n−1} \\ E_{n} & = B_{n−1} \\ F_{n} & = C_{n−1} \end{aligned}  (1)

Note that for n ≥ 3 we can substitute the last three equations from (1) into the first three, to obtain

A_{n} = B_{n−1} + C_{n−1} + A_{n−2},  (2)
B_{n} = A_{n−1} + C_{n−1} + B_{n−2},  (3)
C_{n} = A_{n−1} + B_{n−1} + C_{n−2}.  (4)

At this point, we would like to “unlink” these linked recurrence formulas in equations (2), (3), and (4). After a few minutes of calculations (and with initial values that we drew out by hand), we noticed that A_{n}, B_{n}, and C_{n} all seem to satisfy the fourth-order recurrence relation with signature (1, 4, −1, −1), which is to say that A_{n} seems to equal 1A_{n−1} + 4A_{n−2} − 1A_{n−3} − 1A_{n−4} and likewise for B_{n} and C_{n}. We now prove that this observation is correct.

Lemma 1. With A_{n}, B_{n}, and C_{n} defined in equations (2), (3), and (4), then for n ≥ 5, we have

A_{n} = A_{n−1} + 4A_{n−2} − A_{n−3} − A_{n−4},
B_{n} = B_{n−1} + 4B_{n−2} − B_{n−3} − B_{n−4},
C_{n} = C_{n−1} + 4C_{n−2} − C_{n−3} − C_{n−4}.

Proof. We give a direct proof that follows immediately from (2), (3), and (4). Starting with equation (2), we have

A_{n} = B_{n−1} + C_{n−1} + A_{n−2},

and if we substitute B_{n−1} = A_{n−2} + C_{n−2} + B_{n−3} from (3) and a similar expression for C_{n−1} from (4), we obtain

A_{n} = (A_{n−2} + C_{n−2} + B_{n−3}) + (A_{n−2} + B_{n−2} + C_{n−3}) + A_{n−2}.

We now substitute B_{n−3} = A_{n−2} − C_{n−3} − A_{n−4} and B_{n−2} = A_{n−1} − C_{n−2} − A_{n−3} from (2) to obtain

A_{n} = (A_{n−2} + C_{n−2} + (A_{n−2} − C_{n−3} − A_{n−4})) + (A_{n−2} + (A_{n−1} − C_{n−2} − A_{n−3})) + C_{n−3}) + A_{n−2},

which simplifies nicely to become our desired recurrence relation. A similar method would give us the same recurrence relations for B_{n} and C_{n}.

We can now begin to calculate V_{n}. From earlier, we know that V_{1} = 3 and V_{2} = 13. With some clever drawings, we can establish the following formula that relates V_{n} to the A_{n}, B_{n}, and C_{n}’s discussed earlier.

Lemma 2. For n ≥ 3 we have

V_{n} = 2A_{n−1} + B_{n−1} + 2C_{n−1} + A_{n−2} + B_{n−2} + C_{n−2}.

Proof. We will first establish that for n ≥ 3,

V_{n} = 2A_{n−1} + B_{n−1} + 2C_{n−1} + D_{n−1} + E_{n−1} + F_{n−1}.  (5)

To see this, we imagine a vertical-fault-free tiling of the entire length of a 3 × n rectangle (with n ≥ 3), and we separate it into cases based on how many horizontal dominos are at the right-hand end of the rectangle. We can not have three horizontal dominos (as then the tiling would have a vertical fault at n − 2), nor can we have zero horizontal dominos (as then the tiling would have a vertical fault at n − 1), and so there must be either one or two horizontal dominos.

Suppose there is one horizontal domino at the far right-hand side, and suppose it is located in the upper right corner. Figure 13 shows that the number of such tilings is 2A_{n−1}, since there could be either two stacked squares, or a single vertical domino, below the horizontal domino and so we have to double the number of tilings in profile A_{n−1}.

Figure 13: Vertical-fault-free tilings with an upper-right horizontal domino.

Using similar diagrams, it is not hard to show that a horizontal domino at the far-right side in the middle gives B_{n−1} ways to tile the rectangle, a horizontal domino in the bottom right corner has 2C_{n−1} tilings, and so on. This gives us equation (5).

We can now use the last three equations in (1) to replace the D_{n−1}, E_{n−1}, and F_{n−1} with A_{n−2}, B_{n−2}, and C_{n−2} respectively, and so equation (5) becomes

V_{n} = 2A_{n−1} + B_{n−1} + 2C_{n−1} + A_{n−2} + B_{n−2} + C_{n−2},  (6)

as desired.

We are now ready to establish the following properties for our sequence V_{n}.

Theorem 3. With V_{n} the number of ways to tile a vertical-fault-free 3 × n rectangle with squares and dominos, 1. The first six values of V_{n}, starting at n = 1, are 3, 13, 26, 66, 154, 380.

2. For n ≥ 7, we have V_{n} = V_{n−1} + 4V_{n−2} − V_{n−3} − V_{n−4}.

We note that this theorem verifies the recursion formula (and subsequent values) in \underline{A335747}.

Proof. We consider each part separately.

1. The values of V_{1} and V_{2} (namely, 3 and 13) have already been calculated in Figures 3 and 4. As for V_{3}, V_{4}, V_{5}, V_{6}, and V_{7}, we can use Lemma 2 to calculate them from A_{n}, B_{n}, and C_{n}. Fortunately, A_{n}, B_{n}, and C_{n} satisfy the recurrences in equations (2), (3), and (4), and so the only hand-calculations we need are for n = 1 and 2. Thanks to Figures 9 and 10, we know that A_{1} = 2, A_{2} = 4, and B_{1} = 1, B_{2} = 5. Recall also from the discussion at the beginning of Section 3 and in the caption for Figure 9 that C_{n} = A_{n}. So, the recurrence relations in (2) and (3) give us the sequences {2, 4, 11, 24, 62 … } for A_{n} and C_{n}, and {1, 5, 9, 27, 57, … } for B_{n}. Applying these values to Lemma 2 gives us V_{3} = 26, V_{4} = 66, V_{5} = 154, and V_{6} = 380.

2. To establish the recurrence relation for V_{n}, we look once more at Lemma 2. Since V_{n} is defined in terms of A_{n−1} and A_{n−2}, B_{n−1} and B_{n−2}, and C_{n−1} and C_{n−2}, and since these all satisfy our fourth-order recurrence formula thanks to Lemma 1, then so long as n − 2 ≥ 5 (that is to say, so long as n ≥ 7) we have that V_{n} also satisfies the same fourth-order recurrence formula.

4 Completely fault-free tilings

We now turn our attention to finding U_{n}, the number of completely fault-free tilings of a 3 × n rectangle. We have already shown in Section 1 that U_{1} = U_{2} = 0, and (thanks to Figure 5) that U_{3} = U_{4} = 2. As seen in Figure 7, we must have vertical dominos on each end for a completely fault-free tiling, and those two diagrams suggest that we can count U_{n} by instead counting the number of completely fault-free tilings that have a vertical domino in the lower left corner (as seen in the left-hand diagram in Figure 7) and then doubling that number.

With this in mind, we let T_{n} equal the number of completely fault-free tilings that have a vertical domino in the lower left corner. From the previous paragraph, we have that T_{1} = T_{2} = 0 and T_{3} = T_{4} = 1. Figure 14 shows that T_{5} = 5, and Figure 17 at the end of the paper demonstrates that T_{6} = 8.

Figure 14: Completely fault-free 3 × 5 tilings with a lower-left vertical domino.

As we now show, it is quite easy to adapt our methods from Section 3 to the current problem. Just as we defined A_{n}, B_{n}, …, F_{n} to count the number of vertical-fault-free tilings ending in profiles A, B, …, F from Figure 8, we now define A′_{n}, B′_{n}, …, F′_{n} to give us the number of vertical-fault-free tilings beginning with a vertical domino in the lower left corner and ending in those same profiles A, B, …, F.

We know (thanks to Figure 7) that any completely fault-free tiling that begins with a vertical domino in the lower left corner, must end with a vertical domino in the upper right corner. Hence, T_{n} = C′_{n−1} as seen in Figure 15.

Figure 15: T_{n} = C′_{n−1}.

At this point, we recognize that the three sequences A′_{n}, B′_{n}, and C′_{n} satisfy exactly the same linked recurrence relations (2), (3), and (4) as do A_{n}, B_{n}, and C_{n} from Section 3; recall that we established those by studying diagrans such as Figure 12 and of course the scenario from that figure is exactly the same for our “new” sequences A′_{n}, B′_{n}, …, F′_{n}. And just as we showed that A_{n}, B_{n} and C_{n} satisfy our particular fourth-order recurrence relation in Lemma 1, we can assume that the same applies for A′_{n}, B′_{n}, and C′_{n}.

Now, since T_{n} = C′_{n−1}, we know that T_{n} also satisfies our particular fourth-order recurrence relation. To find the initial values for T_{n} we simply need to find the initial values for C′_{n}, which means we also need those value for A′_{n} and B′_{n}.

Fortunately, this is easy to do. Thanks to Figure 16, we see that A′_{1} = 1, B′_{1} = 0, C′_{1} = 0 and also A′_{2} = 0, B′_{2} = 1, C′_{2} = 1.

Figure 16: Initial values for A′_{n}, B′_{n}, C′_{n}.

We can now use equations (2), (3), and (4) to get that the initial values of C′_{n}, with n from 1 to 6, are {0, 1, 1, 5, 8, 26}, and so T_{n} has the same values (starting with n = 2) and satisfies the same fourth-order recurrence relation of T_{n} = T_{n−1} + 4T_{n−2} − T_{n−3} − T_{n−4} which (we find by checking) actually holds for all n ≥ 5 if we recall from earlier that T_{1} = 0. If we double these values, we have now proved the following theorem.

Theorem 4. With U_{n} the number of ways to tile a completely fault-free 3 × n rectangle with squares and dominos,

1. The first seven values of U_{n}, starting at n = 1, are 0, 0, 2, 2, 10, 16, 52.

2. For n ≥ 5, we have U_{n} = U_{n−1} + 4U_{n−2} − U_{n−3} − U_{n−4}.

This is sequence \underline{A334396}, and (surprisingly) these numbers U_{n} are twice \underline{A112577}.

As a final note, we also find it surprising that both our sequences (V_{n}, the number of ways to tile a vertical-fault-free rectangle, and U_{n}, the number of ways to tile a completely fault-free rectangle) satisfy the same recurrence relation. Surely there is a geometric or tiling explanation for why U_{n} = U_{n−1} + 4U_{n−2} − U_{n−3} − U_{n−4} and likewise V_{n}, and we hope an interested reader will be able to find it.

We conclude with a visual demonstration that T_{6} = 8 and hence U_{6} = 16.

Figure 17: A demonstration that T_{6} = 8.

5 Acknowledgments

The authors would like to thank Pioneer Academics for giving us the opportunity to work together. This paper is one of the results of our collaboration from our spring 2020 research class.

References

[1] M. D. Atkinson and W. F. Lunnon, Regular fault-free rectangles, Math. Gaz. 64 (1980), 99–106.

[2] R. L. Graham, Fault-free tilings of rectangles, in D. A. Klarner, ed., The Mathematical Gardner: A Collection in Honor of Martin Gardner, Wadsworth, 1981, pp. 120–126.

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

[4] E. Montelius, Fault-free tileability of rectangles, cylinders, tori, and Möbius strips with dominoes, preprint, 2019. Available at https://arxiv.org/abs/1912.04445.

[5] R. C. 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 52C20. Keywords: square, domino, tiling, fault-free, rectangle.

(Concerned with sequences \underline{A030186}, \underline{A033506}, \underline{A112577}, \underline{A124997}, \underline{A334396}, and \underline{A335747}.)

Received July 9 2020; revised versions received October 20 2020; December 22 2020. Published in Journal of Integer Sequences, December 28 2020.

Return to Journal of Integer Sequences home page.