Tiling a 2 × n board with dominos and L-shaped trominos

Gregory Dresden Department of Mathematics Washington & Lee University Lexington, VA 24450 USA

                       dresdeng@wlu.edu

Michael Tulskikh East Mountain High School Sandia Park, NM 87047 USA

                   tulskikhmichael@gmail.com

Abstract

We count the number of ways to tile 2 × n rectangles and bracelets using dominos and L-shaped trominos. We show that these 2×n tilings can be related to 1×n tilings with squares, dominos, and two colors of k-minos for k ≥ 3, and we discover some new identities for old sequences.

1 Introduction

How many ways are there to tile a 2 × n board? Naturally, it all depends on the tiles we use. With just dominos, we obtain the familiar Fibonacci sequence. For dominos and squares, we look to McQuistan and Lichtman [?] and the sequence \underline{A030186} from the On-Line Encyclopedia of Integer Sequences (OEIS) [?], and for colored dominos and squares we have papers by Kahkeshani [?], Kahkeshani and Arab [?], and Katz and Stenson [?]. Squares, dominos, and (straight) trominos were covered by Haymaker and Robertson [?] and are counted by \underline{A278815}. For L-shaped trominos and squares, we can turn to to a recent paper by Chinn, Grimaldi, and Heubach [?] as seen in \underline{A077917}. An interesting variation on the 2 × n board was given by Bodeen, Butler, Kim, Sun, and Wang [?] who looked at tiling a 2 × n lozenge with triangles, giving nice combinatorial interpretations to the sequences \underline{A000129}, \underline{A000133}, \underline{A097075}, and \underline{A097076}.

In this paper, we count the tilings of the 2×n board using a slightly different collection of tiles: we use dominos and L-shaped trominos. We derive a number of results and identities for these kinds of tilings. In addition, we are able to relate this question to the problem of tiling a 1 × n board with squares, dominos, and colored k-minos, and this allows us to establish new identities for the sequences \underline{A052980}, \underline{A080204}, and \underline{A332647}. Our work follows closely the tiling techniques studied by Benjamin and Quinn in their book, “Proofs That Really Count” [?].

To begin with, let us define a_{n} to be the number of different ways to tile a 2 × n board with dominos and “bent trominos” in the shape of the letter L (henceforth, we will call these L-shaped trominos, or simply “trominos” if it is clear from the context). It is convenient to define a_{0} = 1. As an example, Figure 1 gives all five possible tilings for n = 3, thus demonstrating that a_{3} = 5. The trominos are shaded for ease of reading.

Figure 1: Demonstrating that a_{3} = 5.

A few minutes of work with pencil and paper will give us the sequence 1, 1, 2, 5, 11, 24, 53, … (starting with a_{0} = 1), and in the next section we will show that this sequence equals \underline{A052980}. But first, inspired by a similar coloring trick in Chinn, Grimaldi, and Heubach’s article [?], we show that we can reduce this 2 × n tiling problem to a 1 × n problem: our numbers a_{n} are exactly the number of ways to tile a 1×n strip with (white) squares, (white) dominos, and colored (red or blue) k-minos of arbitrary length k ≥ 3. To see this equivalence, first note that any 2 × n tiling can be broken along vertical lines into indivisible segments. Two examples are given here in Figure 2, with the trominos shaded for easy visibility.

Figure 2: Breaking a 2 × n tiling along vertical lines.

By parity, each indivisible segment must contain an even number of trominos. Furthermore, each tromino induces a single vertical break in the tiling, as seen in Figure 3 (we will explain the red and blue coloring in Figure 3 in a moment).

Hence, we conclude that for each indivisible segment, it either has no trominos, or it has exactly two trominos with one at each end of the segment. As seen in Figure 3, a tromino at

Figure 3: Trominos that can appear at the ends of indivisible segments.

the beginning of an indivisible segment is either oriented like the letter “r” (which we have colored red) or like the letter “b” (which we have colored blue). Likewise, a tromino at the end of an indivisible segment must be one of the two grey trominos at the right of Figure 3. Also, an indivisible segment with no trominos must begin with (and hence must be equal to) either a single vertical domino or two stacked horizontal dominos; any longer and the segment would break.

These insights now allow us to establish the following relationship between our 2 × n tilings and our 1 × n tilings. After breaking up a 2 × n tiling into indivisible segments, and after coloring each tromino at the beginning of each segment either red or blue depending on its orientation as seen in Figure 3, we map each segment of length k beginning with a red tromino to a red k-mino and likewise each segment of length k beginning with a blue tromino to a blue k-mino, each single vertical domino to a white square, and each aligned pair of horizontal doninos to a white domino. We give here in Figure 4 an example based on the tilings in Figure 2.

Figure 4: Mapping from our 2 × n tilings to our to 1 × n tilings.

To reverse the mapping, we apply the following algorithm to a 1 × n tiling: we replace each square with a vertical domino, we replace each domino with two stacked horizontal dominos, and we replace each red k-mino with a segment that begins with the red tromino from Figure 3 followed by k − 3 staggered horizontal dominos and then one of the two grey trominos on the right of Figure 3. (A similar procedure is used for replacing each blue kmino.) We then “uncolor” each colored tromino, repainting the red and blue trominos with a neutral grey. We give an example in Figure 5

Figure 5: Mapping from our 1 × n tilings to our to 2 × n tilings.

It is clear that we have a one-to-one and onto mapping between our 2 × n tilings and our 1 × n tilings.

As an aside, we note that other types of tilings that use both single-color and multicolored tiles have interesting connections to seemingly-unrelated sequences. For example, Milan Janjic comments in \underline{A001333} in the OEIS that the numerators of the continued fraction expansion for \sqrt{2} also count the number of tilings using single-color squares and two colors of k-minos for k ≥ 2. As for tilings with single-color squares and three colors of k-minos for k ≥ 2, this gives us \underline{A026150} which is related to \sqrt{3}. Thus, we should not be surprised to learn that our tiling method (using single-color squares, single-color dominos, and two colors of k-minos for k ≥ 3) also turns up in the OEIS, and that is the subject of the next section.

2 Establishing that our tiling sequence equals A052980

The sequence \underline{A052980}, defined in the OEIS as the sequence with generating function (1 − x)/(1−2x−x^{3}), has initial values 1, 1, 2, 5, 11 and recurrence formula x_{n} = 2x_{n−1}+x_{n−3}. We now show (in Corollary 2 to Theorem 1) that our sequence (a_{n})_{n≥0} has the same recurrence, and since it also has the same initial values then it must equal \underline{A052980}.

Theorem 1. For n ≥ 3, we have

a_{n} = a_{n−1} + a_{n−2} + 2 (a_{n−3} + a_{n−4} + ⋯ + a_{1} + a_{0}) .  (1)

Proof. In the spirit of Benjamin and Quinn, we ask: how many ways can we tile a board of length n using squares, dominos, and red or blue k-minos with k ≥ 3? On the one hand, by our equivalence discussed in the introduction there are a_{n} ways to tile it. On the other hand, we can condition based on the first tile. If it is a square, there are a_{n−1} ways to tile the remaining length of n − 1. Likewise, if the first tile is a domino, we have a_{n−2} ways. Finally, if the tiling begins with a k-mino for k ≥ 3, we recall that each k-mino has two possible colorings, and can also be any length greater than or equal to three. Therefore, any tiling starting with a k-mino has 2a_{n−k} ways to tile the rest of the strip. Summing up all the different ways, and comparing it to a_{n}, we have our desired equation (1).

Corollary 2. For n ≥ 3, we have

a_{n} = 2a_{n−1} + a_{n−3}.  (2)

Proof. Since our first few values for a_{n} starting with a_{0} are 1, 1, 2, 5, …, then the corollary clearly holds for n = 3. As for n ≥ 4, we use equation (1) from Theorem 1 to state that

a_{n} = a_{n−1} + a_{n−2} + 2 ∑_{i=0}^{n−3} a_{i},  (3)

which also implies

a_{n−1} = a_{n−2} + a_{n−3} + 2 ∑_{i=0}^{n−4} a_{i}.  (4)

Subtracting equation (4) from equation (3), and noticing that just about everything cancels, we get

a_{n} − a_{n−1} = a_{n−1} + a_{n−3}.

Therefore, a_{n} = 2a_{n−1} + a_{n−3}, as desired.

Thanks to Corollary 2 above, we can now conclude that our sequence (a_{n})_{n≥0} is indeed the sequence \underline{A052980}, as both have the same initial values and the same recurrence formula.

It is worth noting that Corollary 2 can be proved directly using the following clever tiling argument: on the one hand, there are a_{n} ways to tile a strip of length n with squares, dominos, and red or blue k-minos. On the other hand, we can look at the first tile of our strip of length n.

1. If a square, remove it to get a strip of length n − 1.

2. If a domino, replace it with a square to get an n − 1 tiling that begins with a square.

3. If a red 3-mino, remove it to get a strip of length n − 3.

4. If a blue 3-mino, replace it with a domino to get an n − 1 tiling that begins with a domino.

5. If a (red or blue) k-mino for k ≥ 4, reduce the length of this k-mino by one to get an n − 1 tiling that begins with a (red or blue) k-mino.

To sum up, part 1 gives us a_{n−1} tilings, part 3 gives us a_{n−3} tilings, and parts 2, 4, and 5 add up to give us another a_{n−1}. In total, we have a_{n−1} + a_{n−3} + a_{n−1}, and since this must equal a_{n} then we have our desired equation (2).

3 Additional identities

Benjamin and Quinn’s book [?] is full of ingenious tiling proofs for various identities. Since our sequence (a_{n})_{n≥0} is also a tiling sequence, we can use Benjamin and Quinn’s methods (just as we did in the proof of Theorem 1) to come up with new identities for our sequence. For example, this next formula comes from looking at where the tiling breaks into two.

Theorem 3. For n, m ≥ 2, we have

a_{m+n} = a_{m}a_{n} − a_{m−1}a_{n−1} + \frac{1}{2}(a_{m+2} − a_{m+1} − a_{m})(a_{n+2} − a_{n+1} − a_{n}).  (5)

Proof. Just like in our proof of Theorem 1, we ask: how many ways can we tile a board of length m + n with squares, dominos, and red or blue k-minos with k ≥ 3? On the one hand, this is simply a_{m+n}. On the other hand, we can look at what happens between cell m and cell m + 1. There are three options.

1. The tiling breaks between cell m and m + 1. See Figure 6.

Figure 6: A break between cells m and m + 1.

In this case, it is easy to see that there are a_{m} tilings on the left of the break, and a_{n} tilings on the right, giving a_{m}a_{n} ways to tile this board.

2. There is a domino covering the break between cells m and m + 1. See Figure 7.

Figure 7: Covering the break with a domino.

Using the same argument as above, we can see that the total number of ways to tile this board is a_{m−1}a_{n−1}.

3. There is a red or blue k-mino covering the break between cells m and m + 1.

As seen in Figure 8, there are a_{m−i} tilings to the left of the central k-mino, then two possible colorings (red or blue) for the k-mino, and then a_{n−j} tilings to the right, giving a_{m−i} · 2 · a_{n−j} tilings. We now imagine central k-minos of different sizes, and we see that i can range from 1 to m and likewise j can range from 1 to n, but we note that

Figure 8: Covering the break with a red or blue k-mino.

we can not have both i and j equal to 1 at the same time, as this would imply that the central k-mino would be of length 2 instead of the required 3 or above. Hence, the total number of tilings in this configuration can be written as

(2 · ∑_{i=1}^{m} a_{m−i} · ∑_{j=1}^{n} a_{n−j}) − 2a_{m−1}a_{n−1},  (6)

where we have included, and then removed, the forbidden case where i = j = 1.

We have now covered all possible cases. Since a_{m+n} must equal the sum of the expressions from the above three options, we have

a_{m+n} = a_{m}a_{n} + a_{m−1}a_{n−1} + (2 · ∑_{i=1}^{m} a_{m−i} · ∑_{j=1}^{n} a_{n−j}) − 2a_{m−1}a_{n−1},

= a_{m}a_{n} − a_{m−1}a_{n−1} + 2 ∑_{i=1}^{m} a_{m−i} ∑_{j=1}^{n} a_{n−j}.  (7)

For the sum ∑_{i=1}^{m} a_{m−i} in equation (7), we replace i with m − i to obtain ∑_{i=0}^{m−1} a_{i}. We note that Theorem 1 tells us that a_{m+2} = a_{m+1} + a_{m} + 2 ∑_{i=0}^{m−1} a_{i} and so we see that our sum ∑_{i=0}^{m−1} a_{i} can be replaced with \frac{1}{2} (a_{m+2} − a_{m+1} − a_{m}). This, along with a similar substitution for ∑_{j=1}^{n} a_{n−j}, allows us to simplify equation (7) to obtain our desired equation (5).

The following corollary is a nice variant on Theorem 3.

Corollary 4. For n ≥ 2, we have a_{2n} = a_{n}^{2} − a_{n−1}^{2} + \frac{1}{2}(a_{n} + a_{n−1} + a_{n−2})^{2}.

Proof. If we replace m with n in equation (5) of Theorem 3, we have

a_{2n} = a_{n}^{2} − a_{n−1}^{2} + \frac{1}{2}(a_{n+2} − a_{n+1} − a_{n})^{2}.  (8)

We can now use Corollary 2 to replace the a_{n+2} in equation (8) with 2a_{n+1} + a_{n−1}, giving us

a_{2n} = a_{n}^{2} − a_{n−1}^{2} + \frac{1}{2}(a_{n+1} − a_{n} + a_{n−1})^{2},  (9)

and we again use Corollary 2 but this time to replace the a_{n+1} in equation (9) with 2a_{n}+a_{n−2}, which gives us our desired formula.

We remind our reader of the Fibonacci numbers, which are traditionally defined as F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} +F_{n−2}. If we define f_{n} = F_{n+1} then the sequence (f_{n})_{n≥0} is exactly the number of ways to tile a board of length n with squares and dominos [?]. With this in mind, we present the following theorem on weighted sums.

Theorem 5. For n ≥ 3, we have

a_{n} = F_{n+1} + 2 ∑_{i=0}^{n−3} a_{i} (F_{n−i} − 1) ,  (10)

and for n ≥ 0, we have

a_{n+2} = F_{n+1} + a_{n+1} + 2 ∑_{i=0}^{n} a_{i}F_{n−i}.  (11)

Proof. As before, we count up the total number of tilings of a strip of length n and set it equal to a_{n} to obtain our formula. We recall that we have n ≥ 3.

If a particular tiling has no k-minos, it must be entirely made up of squares and dominos. By our observation earlier, this corresponds to f_{n} = F_{n+1} unique tilings. (Recall that when we talk about k-minos we always assume that k ≥ 3).

Suppose, instead, that the tiling has at least one k-mino. If we look at the last or rightmost k-mino, we see that this splits the length-n tiling into a tiling of length i (to the left of the k-mino) with squares, dominos and k-minos, followed by the red or blue k-mino in the middle, and ending with a tiling of length n − i − k (to the right of the k-mino) with just squares and dominos. An illustration is shown in Figure 9.

Figure 9: Tiling a board based on the location of the last (red or blue) k-mino.

There are exactly a_{i} ways to tile everything to the left of that last k-mino, there are two possible colors (red or blue) for that last k-mino, and there are f_{n−i−k} ways to tile everything to the right of that last k-mino (because to the right we have only squares and dominos). Hence, the particular configuration in Figure 9 has a_{i} · 2 · f_{n−i−k} tilings.

We now imagine fixing i at some permissible value, 0 ≤ i ≤ n − 3. Since k ≥ 3, then n − i − k ranges from 0 to n − i − 3, giving us

a_{i} · 2 · f_{0} + a_{i} · 2 · f_{1} + a_{i} · 2 · f_{2} + ⋯ + a_{i} · 2 · f_{n−i−3}

tilings for the configurations in Figure 9 for this fixed value of i. In other words, we have a_{i} · 2 · (f_{0} + f_{1} + f_{2} + ⋯ + f_{n−i−3}) ways to tile the board in Figure 9.

We now sum up these values over i as i ranges from 0 to n − 3, and we have

∑_{i=0}^{n−3} a_{i} · 2 · (f_{0} + f_{1} + f_{2} + ⋯ + f_{n−i−3}).  (12)

Thanks to a well-known identity, that sum of consecutive Fibonacci numbers in equation (12) can be replaced with f_{n−i−1} − 1. If we make this substitution, and also add in f_{n} (coming from the tilings with no k-minos) we obtain this total count for all tilings,

a_{n} = f_{n} + 2 ∑_{i=0}^{n−3} a_{i}(f_{n−i−1} − 1),  (13)

and if we use the identity f_{n} = F_{n+1} on equation (13) we have

a_{n} = F_{n+1} + 2 ∑_{i=0}^{n−3} a_{i}(F_{n−i} − 1),  (14)

and this is a perfect match for equation (10) from the first part of the theorem.

It is now a simple matter to arrive at equation (11) from the second part of the theorem. We substitute equation (1) from Theorem 1 into equation (14) to obtain

a_{n} = F_{n+1} + 2 ∑_{i=0}^{n−3} a_{i}F_{n−i} − (a_{n} − a_{n−1} − a_{n−2})

= F_{n+1} + 2 ∑_{i=0}^{n} a_{i}F_{n−i} − 2(a_{n−2}F_{2} + a_{n−1}F_{1} + a_{n}F_{0}) − (a_{n} − a_{n−1} − a_{n−2})

= F_{n+1} + 2 ∑_{i=0}^{n} a_{i}F_{n−i} − (a_{n} + a_{n−1} + a_{n−2}).  (15)

From equation (15) we have 2a_{n} + a_{n−1} + a_{n−2} = F_{n+1} + 2 ∑_{i=0}^{n} a_{i}F_{n−i}, and by applying Corollary 2 twice we can replace the 2a_{n} + a_{n−1} + a_{n−2} on the left with a_{n+2} − a_{n+1}, which gives us the formula

a_{n+2} = F_{n+1} + a_{n+1} + 2 ∑_{i=0}^{n} a_{i}F_{n−i},  (16)

and this matches equation (11). Finally, while our proof of (16) was only valid for n ≥ 3, it is easy to check the cases n = 0, 1, 2 by hand and so our equation (16) actually holds for all n ≥ 0, as desired.

While Theorem 5 involved weighted sums with Fibonacci numbers, this next theorem presents a weighted sum with powers of 2.

Theorem 6. For n ≥ 0, we have

a_{n+3} = 2^{n+2} + ∑_{i=0}^{n} a_{i}2^{n−i}.  (17)

Proof. For now, let us assume that n ≥ 3. Just as in the proof of Theorem 5, we consider a strip of length n, but this time we condition on the location of the last blue k-mino. If there are no blue k-minos, we take all the red k-minos and color them white to match the white squares and white dominos; this means that our tiling now consists of single-color (white) tiles of arbitrary length. In order to find the number of ways to tile such a board, consider the length-n board in Figure 10. Note that there are exactly n − 1 interior vertical “dividing

Figure 10: A board of length n.

lines”. We can create unique tiling patterns by simply removing (some of the) dividing lines to produce tiles of arbitrary length. For each dividing line, there are only two options: keep it or remove it. Making this choice for every dividing line in Figure 10 gives 2^{n−1} possible tiling patterns.

Next, we suppose there is at least one blue k-mino, and we imagine that it starts at cell i + 1 and extends a distance k to the right, as seen in Figure 11.

Figure 11: Counting tilings based on location and length of last blue k-mino.

There are exactly a_{i} ways to tile everything to the left of that last blue k-mino. If i + k = n, then there is nothing to the right of that last blue k-mino and so we have a_{i} tilings overall. Assuming now that i + k < n, then to count the tilings to the right of that last blue k-mino we apply the same technique as at the beginning of the proof: we assign all tiles to the right of that last blue k-mino to be white so that we now are counting all tilings consisting of single-color (white) tiles of arbitrary length within a total length of n − i − k, giving us 2^{n−i−k−1} such tilings. In total, then, for Figure 11 we have a_{i} tilings for i + k = n and a_{i} · 2^{n−i−k−1} tilings for i + k < n.

It remains to carefully sum our number of tilings over the permissible values of i and k. While i can run from 0 to n − 3, and k can run from 3 to n − i, we need to separate the special case when i + k = n from the general case when i + k < n. The following list gives all possible options.

1. When i + k = n, we have just a_{i} tilings for each case, and when we sum over these

permissible values of i we get ∑_{i=0}^{n−3} a_{i} tilings.

2. When i + k < n, which occurs when 0 ≤ i ≤ n − 4 and 3 ≤ k ≤ n − i − 1, we have a_{i} · 2^{n−i−k−1} tilings. Summing this over these values of i and k gives us

∑_{i=0}^{n−4} ∑_{k=3}^{n−i−1} a_{i} · 2^{n−i−k−1}

tilings. We factor out the a_{i} and we re-index the inner sum by letting j = n − i − k − 1 to obtain

∑_{i=0}^{n−4} a_{i} ∑_{j=0}^{n−i−4} 2^{j},

and we sum up that inner sum to obtain ∑_{i=0}^{n−4} a_{i} (2^{n−i−3} − 1) .

Summing up the terms from these two cases gives us ∑_{i=0}^{n−3} a_{i} (2^{n−i−3}). When we add in the

2^{n−1} from the case where there are no blue k-minos, and when we compare this total to a_{n}, we obtain

a_{n} = 2^{n−1} + ∑_{i=0}^{n−3} a_{i}2^{n−i−3} for n ≥ 3.

Replacing n with n + 3 gives us

a_{n+3} = 2^{n+2} + ∑_{i=0}^{n} a_{i}2^{n−i}  for n ≥ 0,

which is our desired equation (17) in the statement of Theorem 6.

4 Bracelet numbers

Recall that the Fibonacci numbers f_{n} count the number of ways to tile a 1 × n strip with squares and dominos, and likewise the Lucas numbers count the number of ways to tile a 1 × n bracelet with squares and dominos [?]. Inspired by this relationship, we now ask: what are the corresponding “bracelet numbers” for our sequence (a_{n})_{n≥0}?

Surprisingly, there are two answers to this question! It all depends on whether we view a_{n} as counting the tilings of a 2 × n strip with dominos and trominos (which was our definition of a_{n}), or as counting the tilings of a 1×n strip with squares, dominos, and red/blue k-minos (which, as we showed in the Introduction, is exactly the same number). This equivalence between the 2 × n and the 1 × n situations isn’t quite perfect when we turn to bracelets, because while every 2×n strip with dominos and trominos can be broken along vertical lines into indivisible segments (which we then map to squares, dominos, and red or blue k-minos), when n is even there are exactly two tilings on a 2 × n bracelet which can not be broken; these are the two tilings with unaligned horizontal dominos that go “all the way around the bracelet”. (Imagine one such configuration; if we rotate the bracelet by one cell we will have the other configuration). When n is odd this configuration is not possible thanks to parity.

With this in mind, we define b′_{n} to be the number of ways to tile a 2 × n bracelet with dominos and trominos, and b_{n} to be the number of ways to tile a 1×n bracelet with squares, dominos, and red or blue k-minos. By our discussion above, b′_{n} = b_{n} + 2 for n even and b′_{n} = b_{n} for n odd. In what follows, we will focus on b_{n}.

Once again, a few minutes with pencil and paper give the initial values 1, 3, 10, 23, … for b_{n} (starting with b_{1} = 1), and we will show in a moment that this is the sequence A080204 (which, interestingly enough, comes from a Kolakoski sequence which has nothing to do with tilings). To show this equality, we need to begin with the following theorem.

Theorem 7. For a_{n} and b_{n} defined as above, we have

b_{n} = a_{n} + a_{n−2} + 2 ∑_{k=3}^{n}(k − 1)a_{n−k}  (18)

Proof. Inspired by the proofs of Theorems 1 and 3, we count the number of ways to tile a (1 × n) bracelet using squares, dominos, and red or blue k-minos, and we set that equal to b_{n}. We condition on the tile covering the “break” at the top of the bracelet, as shown in the following images. There are three options.

1. The tiling is breakable at the top, meaning that no single tile crosses over from the n^{th} position (immediately to the left of the break) to the first position (immediately to the right). See Figure ??. As the bracelet is breakable here, there are simply a_{n} ways to

Figure 12: A bracelet of length n.

tile the 1 × n strip we obtain when we unfold the bracelet.

2. The tiling is not breakable at the top, due to a domino covering the break. For this, we simply remove the domino and unfold the bracelet to give us a strip of length n−2, and hence there are a_{n−2} ways to tile it.

3. The tiling is not breakable at the top, due to a red or blue k-mino covering the break. In this case, for each k-mino covering the break there are exactly k − 1 ways to shift it such that the bracelet remains unbreakable at the top. There are two colors for the k-mino (red or blue), and the rest of the bracelet has length n − k. Hence, there are 2(k − 1)a_{n−k} ways to tile this particular bracelet. Since k can range from 3 to n, we get that the total number of ways to tile in this situation is 2 ∑_{k=3}^{n}(k − 1)a_{n−k}.

We have now covered all three possible cases. Adding the results will give equation (??), as desired.

To conclude, we present the following results for our bracelet sequence (b_{n})_{n≥0}. These can all be proved by induction, by Theorem ??, or by tilings; we leave the details to the reader.

Theorem 8. For a_{n} and b_{n} defined as above, we have

b_{n} = 3b_{n−1} − 2b_{n−2} + b_{n−3} − b_{n−4},  (19)
b_{n} = 2b_{n−1} + b_{n−3} + 2,  (20)
b_{n} = \frac{1}{2}(5a_{n} − a_{n−1} − a_{n−2}) − 1,  (21)
b_{n} = θ_{1}^{n} + θ_{2}^{n} + θ_{3}^{n} − 1, for θ_{1}, θ_{2}, θ_{3} the roots of x^{3} − 2x^{2} − 1 = 0.  (22)

With this recurrence relation (??) for b_{n}, and with our initial values for b_{n} of 1, 3, 10, and 23, we can conclude that we do indeed have the sequence A080204. Furthermore, the recurrence relation in (??) for b_{n} is also satisfied by a_{n}, as seen here in Lemma ??. Only the initial values are different.

Lemma 9. For n ≥ 4 we have

a_{n} = 3a_{n−1} − 2a_{n−2} + a_{n−3} − a_{n−4}.  (23)

Proof. From equation (2) in Corollary 2, we have that a_{n} = 2a_{n−1} + a_{n−3} and replacing n with n − 1 we have a_{n−1} = 2a_{n−2} + a_{n−4}. We subtract these two equations, and simplify, to obtain the desired result.

Finally, we can rewrite equation (??) in Theorem ?? as (b_{n} +1) = 2(b_{n−1} +1)+(b_{n−3} +1), which tells us that the numbers b_{n} + 1 have a particularly nice recurrence formula (in fact, the same recurrence formula as for a_{n} in Theorem 2). These numbers b_{n} + 1 appears in the OEIS as \underline{A332647}.

5 Acknowledgements

We express our gratitude to Pioneer Academics for making this collaboration possible, and to Brittney Miller and Jeffrey Shallit for their many helpful comments and suggestions for improving our paper.

References

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

[2] John Bodeen, Steve Butler, Taekyoung Kim, Xiyuan Sun, and Shenzhi Wang, Tiling a strip with triangles, Electron. J. Combin. 21(1) (2014), Paper 1.7, 15.

[3] Phyllis Chinn, Ralph Grimaldi, and Silvia Heubach, Tiling with L’s and squares, J. Integer Seq. 10(2) (2007), Article 07.2.8, 17.

[4] Kathryn Haymaker and Sara Robertson, Counting colorful tilings of rectangular arrays, J. Integer Seq. 20(5) (2017), Art. 17.5.8, 15.

[5] Reza Kahkeshani, The tilings of a (2 × n)-board and some new combinatorial identities, J. Integer Seq. 20(5) (2017), Art. 17.5.4, 9.

[6] Reza Kahkeshani and Meysam Arab, A generalized Binet formula that counts the tilings of a (2 × N)-board, Integers 18 (2018), Paper No. A91, 6.

[7] Matt Katz and Catherine Stenson, Tiling a (2 × n)-board with squares and dominoes, J. Integer Seq. 12(2) (2009), Article 09.2.2, 12.

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

[9] N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2019.

2010 Mathematics Subject Classification: Primary 05B45; Secondary 52C20. Keywords: domino, tromino, tiling, Fibonacci, rectangle.

(Concerned with sequences \underline{A000129}, \underline{A000133}, \underline{A001333}, \underline{A026150}, \underline{A030186}, \underline{A052980}, \underline{A077917}, \underline{A080204}, \underline{A097075}, \underline{A097076}, \underline{A278815}, and \underline{A332647}.)

Received January 18 2021; revised version received April 12 2021. Published in Journal of Integer Sequences, xxx xx 2021.

Return to Journal of Integer Sequences home page.