Tiling a (2 × n)-Board with Squares and Dominoes

Matt Katz Pennsylvania State University Mathematics Department 109 McAllister Building University Park, PA 16802 USA

                   katz@math.psu.edu

Catherine Stenson^{1} Juniata College 1700 Moore Street Huntingdon, PA 16652 USA

                  stenson@juniata.edu

Abstract

The Fibonacci numbers and the Pell numbers can be interpreted as the number of tilings of a (1 × n)-board by colored squares and dominoes. We explore the tilings of (2 × n)-boards by colored squares and dominoes. We develop a recurrence relation and prove several combinatorial identities in the style of recent work by Benjamin and Quinn. We also give a bijection between these (2 × n)-tilings and a set of weighted (1 × n)-tilings.

1 Introduction

The Fibonacci numbers (\underline{A000045}) count the tilings of a (1 × n)-board with dominoes and squares. Benjamin and Quinn [2] have used this interpretation to provide tiling proofs of many Fibonacci identities. The Pell numbers (\underline{A000129}) count the tilings of a (1 × n)-board with dominoes and two colors of squares, and Benjamin, Plott, and Sellers [1] used this interpretation to prove still more combinatorial identities. What if we expand the board– what can we say about tilings of a (2 × n)-board by squares and dominoes?

1All correspondence should be directed to this author.

McQuistan and Lichtman [5] studied such tilings in the context of placing dimers on a lattice. They found a recurrence relation and a generating function and looked at some statistical questions for large values of n. Grimson [4] studied the generating function for q dominoes on a (2 × n)-board.

In Section 2, we generalize McQuistan and Lichtman’s recurrence to tilings by a colors of squares and b colors of dominoes and give a direct combinatorial proof in the style of Benjamin and Quinn. In Section 3, we prove several combinatorial identities, and in Section 4, we provide a correspondence between these tilings and an equivalent set of weighted (1 × n)-tilings.

2 A Recurrence Relation

Let k_{n} count the number of tilings of a (2 × n)-board using (1 × 1) squares and (1 × 2) dominoes. The sequence (\underline{A030186} in the Online Encyclopedia of Integer Sequences [6]) begins with k_{0} = 1, k_{1} = 2, k_{2} = 7, and k_{3} = 22. More generally, let k_{n}^{a,b} be the number of tilings of a (2 × n)-board using a colors of squares and b colors of dominoes. Below is a table of some values of k_{n}^{a,b}.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ k_{n} & 1 & 2 & 7 & 22 & 71 & 228 & 733 & 2356 & 7573 \\ k_{n}^{2,3} & 1 & 7 & 82 & 877 & 9565 & 103960 & 1130701 & 12296275 & 133724242 \\ k_{n}^{4,2} & 1 & 18 & 392 & 8408 & 180560 & 3877120 & 83253056 & 1787684480 & 38386770432 \end{matrix}

Table 1: Some values of k_{n} and k_{n}^{a,b}.

McQuistan and Lichtman [5] proved that for n ≥ 3,

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

Their proof used repeated applications of other recurrence relations. Here we generalize their relation to k_{n}^{a,b} and offer a more direct proof in the style of Benjamin and Quinn [2].

Theorem 1. Let k_{n}^{a,b} count the number of tilings of a (2 × n)-board with a colors of squares and b colors of dominoes. Then k_{0}^{a,b} = 1, k_{1}^{a,b} = a^{2} + b, k_{2}^{a,b} = a^{4} + 4a^{2}b + 2b^{2}, and, for n ≥ 3,

k_{n}^{a,b} = (a^{2} + 2b)k_{n−1}^{a,b} + a^{2}bk_{n−2}^{a,b} − b^{3}k_{n−3}^{a,b}.  (2)

Proof. First we verify the initial conditions. We define k_{0}^{a,b} = 1. On a (2 × 1)-board, there are a^{2} tilings with two squares and b tilings with one vertical domino, giving k_{1}^{a,b} = a^{2} + b.

On a (2 × 2)-board, there are a^{4} tilings with four squares, 4a^{2}b tilings with two squares and one domino, and 2b^{2} tilings with two dominoes, giving k_{2}^{a,b} = a^{4} + 4a^{2}b + 2b^{2}.

Now we turn to the recurrence relation for (2×n)-boards, n ≥ 3. There are a^{2}k_{n−1}^{a,b} tilings of a (2 × n)-board that end with two squares in column n and bk_{n−1}^{a,b} tilings that end with a vertical domino in column n. There are a^{2}bk_{n−2}^{a,b} tilings that end with two squares in the top row and a horizontal domino in the bottom row. We need to show that the remaining tilings are counted by bk_{n−1}^{a,b} − b^{3}k_{n−3}^{a,b}.

The tilings that remain to be counted are those ending in two horizontal dominoes, those ending with a horizontal domino in the top row and a square in the bottom row, and those ending with a horizontal domino in the bottom row, a square in column n of the top row, and a horizontal domino in columns n − 2 and n − 1 of the top row. These endings can be seen below in Figure 1.

Figure 1: The endings counted by bk_{n−1}^{a,b} − b^{3}k_{n−3}^{a,b}.

We will show that the (2×n)-tilings with these endings correspond to certain (2×(n−1))- tilings. In particular, there are b^{2}k_{n−3}^{a,b} tilings of a (2 × (n − 1))-board that end with two horizontal dominoes in the last two columns. So we need to show that each (2×(n−1))-tiling that does not end in two horizontal dominoes corresponds to b tilings of a (2 × n)-board that end as in Figure 1.

A (2 × (n − 1))-tiling that does not end in two horizontal dominoes may end with a vertical domino, with a square in column n − 1 of the top row, or with a horizontal domino in columns n − 2 and n − 1 of the top row and a square in column n − 1 of the bottom row.

If our (2 × (n − 1))-tiling ends in a vertical domino, create a (2 × n)-tiling by turning the vertical domino into a horizontal domino in columns n − 1 and n of the bottom row and filling in columns n − 1 and n of the top row with any of the b colors of dominoes.

If our (2 × (n − 1))-tiling ends with a square in column n − 1 of the top row, create a (2 × n)-tiling by moving the square to column n of the bottom row and filling in columns n − 1 and n of the top row with any of the b colors of dominoes.

If our (2 × (n − 1))-tiling ends with a horizontal domino in the top row and a square in the bottom row, create a (2 × n)-tiling by moving the square to column n of the top row and filling in columns n − 1 and n of the bottom row with any of the b colors of dominoes. This mapping can be seen in Figure 2 below.

Figure 2: Mapping (2 × (n − 1))-tilings to (2 × n)-tilings.

These one-to-b mappings reverse to b-to-one mappings, and this correspondence completes the proof of (2). McQuistan and Lichtman’s recurrence relation (1) is the special case a = b = 1.

Using standard methods (see, for example, Brualdi’s discussion [3, Chapter 7]), we can find that the generating function for k_{n}^{a,b} is

G^{a,b}(x) = \frac{1 − x}{1 − (a^{2} + 2b)x − a^{2}bx^{2} + b^{3}x^{3}} .  (3)

3 Combinatorial Identities

The tilings of a (1×n)-board by squares and dominoes are counted by the Fibonacci number usually denoted F_{n+1}, with F_{0} = 0 and F_{1} = 1. Because we would like our subscript to match our board size, we follow the notation of Benjamin and Quinn [2] and define f_{n} = F_{n+1}, with f_{0} = 1, f_{1} = 1, and f_{n} = f_{n−1} + f_{n−2}. We also note that f_{n} = k_{n}^{0,1}; that is, f_{n} counts the tilings of a (2 × n)-board by dominoes. To see this, notice that the top row of a (2 × n)-tiling by dominoes is just a (1 × n)-tiling by dominoes and squares, and that the top row of a (2 × n)-tiling by dominoes completely determines the bottom row. In this case, equation (1) becomes the Fibonacci identity f_{n} = 2f_{n−1} + f_{n−3}. Because of these connections, we expect that many Fibonacci-style identities will apply to (2 × n)-tilings.

To prove some of these identities, we need the notion of breakability. We say that a tiling of a (2 × n)-board is breakable at column m (1 ≤ m ≤ n − 1) if it can be separated into a tiling of a (2 × m)-board and a tiling of a (2 × (n − m))-board. A tiling is unbreakable if it is not breakable at any column. First we consider the case a = b = 1. Both tilings of a (2 × 1)-board are unbreakable, and three of the tilings of a (2 × 2)-board are unbreakable (the ones with at least one horizontal domino). For n ≥ 3, there are two unbreakable (2 × n) tilings, each consisting of n − 1 staggered horizontal dominoes and one square in the first column and one square in the last column. See Figure 3. If n is even, the two squares will be in the same row, and if n is odd, they will be in different rows.

Figure 3: The two unbreakable tilings of length 8.

In the general case of a colors of squares and b colors of dominoes, there are a^{2} + b unbreakable tilings of a (2 × 1)-board, 2a^{2}b + b^{2} unbreakable tilings of a (2 × 2)-board, and 2a^{2}b^{n−1} unbreakable tilings of a (2 × n)-board for n ≥ 3.

We now offer several identities with proofs using breakability. The first generalizes the usual Fibonacci recurrence.

Identity 1.

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

(ii) k_{n}^{a,b} = (a^{2} + b)k_{n−1}^{a,b} + (2a^{2}b + b^{2})k_{n−2}^{a,b} + 2a^{2} ∑_{i=0}^{n−3} b^{n−i−1}k_{i}^{a,b}.

Proof. We prove statement (ii) by conditioning on the location of the rightmost break; statement (i) is just the case a = 1, b = 1. Say this break occurs at column i; we allow i = 0 if the tiling is unbreakable. The tiling begins with one of the k_{i}^{a,b} tilings of a (2 × i)-board and ends with an unbreakable tiling of a (2 × (n − i))-board. If n − i = 1, there are a^{2} + b such unbreakable tilings. If n − i = 2, there are 2a^{2}b + b^{2} unbreakable tilings. Finally, if n − i ≥ 3, there are 2a^{2}b^{n−i−1} unbreakable tilings.

In the special case a = 0, b = 1, identity (ii) reduces to the Fibonacci recurrence f_{n} = f_{n−1} + f_{n−2}. Identity 1 (ii) can be used to give an alternative proof of Theorem 1: begin with the identity, add and subtract bk_{n−1}^{a,b} on the right-hand side, use the identity again to expand −bk_{n−1}^{a,b}, and simplify.

Benjamin and Quinn [2] prove the Fibonacci identity f_{m+n} = f_{m}f_{n} + f_{m−1}f_{n−1} by considering whether or not a tiling is breakable at column m. We use the same technique to prove the next identity.

Identity 2. For m, n ≥ 0,

(i) k_{m+n} = k_{m}k_{n} + k_{m−1}k_{n−1} + 2 ∑_{i=0}^{m−1} ∑_{j=m+1}^{m+n} k_{i}k_{m+n−j}

(ii) k_{m+n}^{a,b} = k_{m}^{a,b}k_{n}^{a,b} + b^{2}k_{m−1}^{a,b}k_{n−1}^{a,b} + 2a^{2} ∑_{i=0}^{m−1} ∑_{j=m+1}^{m+n} b^{j−i−1}k_{i}^{a,b}k_{m+n−j}^{a,b}.

Proof. We prove statement (ii) here; statement (i) is just the case a = 1, b = 1. There are k_{m}^{a,b}k_{n}^{a,b} tilings of a (2 × (m + n))-board that are breakable at column m. If a tiling is not breakable at column m, then look for the last break before column m (say it occurs at column i) and the first break after column m (say it occurs at column j). Then the tiling is breakable at columns i and j (0 ≤ i ≤ m − 1, m + 1 ≤ j ≤ m + n) and unbreakable between these columns. We allow i = 0 when the tiling has no breaks to the left of column m and j = m + n when the tiling has no breaks to the right of column m. When i = m − 1 and j = m + 1, there are 2a^{2}b + b^{2} possible unbreakable tilings of the two columns in between, and therefore there are (2a^{2}b + b^{2})k_{m−1}^{a,b}k_{n−1}^{a,b} tilings with these values of i and j. For all other choices of i and j, there are 2a^{2}b^{j−i−1} unbreakable tilings between columns i and j, and therefore there are 2a^{2}b^{j−i−1}k_{i}^{a,b}k_{m+n−j}^{a,b} tilings with the chosen values of i and j. We sum over all possible values of i and j to get the identity. If a = 0 and b = 1, identity (ii) reduces to the Fibonacci identity above.

The remaining four identities all follow from counting tilings that contain at least one of a certain kind of tile. We begin by considering tilings that contain at least one domino.

Identity 3. For n ≥ 0,

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

Proof. The left-hand side counts the number of tilings of a (2 × n)-board with at least one domino, since there is only one tiling using all squares. We will show that the right-hand side counts the same thing. We condition on the location of the rightmost break in the tiling that still has at least one domino to its right. Say this break occurs at column i; we allow i = 0 if there is no such break within the tiling. There are k_{i} ways to fill in the first i columns of such a tiling. The remaining n − i columns begin with an unbreakable tiling of length j (1 ≤ j ≤ n − i) containing at least one domino and end with n − i − j columns of squares. If j = 1, the only appropriate unbreakable tiling is a vertical domino. If j = 2, there are three unbreakable tilings, and if j ≥ 3, there are two unbreakable tilings. (See Figure 3.) If we sum these possibilities over all j, we get 1 in the case i = n − 1 and 2(n − i) in the case 0 ≤ i ≤ n − 2 . This gives us the right-hand side of the identity.

The next identity counts tilings that contain at least one square.

Identity 4. For n ≥ 1,

k_{n} − f_{n} = ∑_{i=0}^{n−1} k_{i}(f_{n−i−1} + 2 ∑_{j=2}^{n−i} f_{n−i−j})  (4)

= ∑_{i=0}^{n−1} k_{i}(f_{n−i+2} − 2).  (5)

Proof. The left-hand side of (4) counts the number of tilings of a (2 × n)-board with at least one square, since there are f_{n} tilings using only dominoes. We will show that the right-hand side of (4) counts the same thing. We condition on the location of the rightmost break in the tiling that still has at least one square to its right. Say this break occurs at column i; we allow i = 0 if there is no such break within the tiling. There are k_{i} ways to fill in the first i columns of such a tiling. The remaining n − i columns begin with an unbreakable tiling of length j (1 ≤ j ≤ n − i) containing at least one square and end with a tiling of length n − i − j using only dominoes. If j = 1, the only appropriate unbreakable tiling is a pair of squares. If j = 2, there are two unbreakable tilings with at least one square (a horizontal domino in one row and two squares in the other). If j ≥ 3, there are two unbreakable tilings. There are f_{n−i−j} tilings of length n − i − j using only dominoes. If we sum over all j, we get the right-hand side of (4).

We get (5) by applying the identity ∑_{j=2}^{n−i} f_{n−i−j} = f_{n−i} − 1 to get

k_{n} − f_{n} = ∑_{i=1}^{n−1} k_{i}(f_{n−i−1} + 2 ∑_{j=2}^{n−i} f_{n−i−j})

= ∑_{i=1}^{n−1} k_{i}(f_{n−i−1} + 2f_{n−i} − 2)

= ∑_{i=1}^{n−1} k_{i}(f_{n−i+2} − 2).

The next identity counts tilings which contain at least one vertical domino. After the last vertical domino, such a tiling will fall into two (1 × j)-tilings for some j. Benjamin, Plott, and Sellers [1] noted that the tilings of a (1 × n)-board by dominoes and two colors of squares are counted by the Pell number P_{n+1}. They introduced the notation p_{n} = P_{n+1} with p_{0} = 1, p_{1} = 2, and p_{n} = 2p_{n−1} + p_{n−2} (analogous to the Fibonacci notation f_{n}), and we follow that notation here.

Identity 5. For n ≥ 0,

(i) k_{n} − (f_{n})^{2} = ∑_{m=1}^{n} k_{m−1}(f_{n−m})^{2}  (6)

(ii) k_{n}^{2,1} − (p_{n})^{2} = ∑_{m=1}^{n} k_{m−1}^{2,1}(p_{n−m})^{2}.  (7)

Proof. Identity (i) is due to Cipra and stated without proof in Sloane [6]. In both (i) and (ii), the right- and left-hand sides represent two different ways of counting the number of tilings of a (2×n)-board with at least one vertical domino. A tiling with no vertical dominoes breaks into two (1 × n)-tilings; there are (f_{n})^{2} such tilings in the case a = 1, b = 1 and (p_{n})^{2} in the case a = 2, b = 1. This gives us the left-hand sides in (i) and (ii), respectively. To get the right-hand sides, condition on the position of the last vertical domino. Say it is in column m. This domino is preceded by a tiling of a (2 × (m − 1))-board, of which there are k_{m−1} in case (i) and k_{m−1}^{2,1} in case (ii). This domino is followed by a tiling of a (2 × (n − m))-board with no vertical dominoes, of which there are (f_{n−m})^{2} in case (i) and (p_{n−m})^{2} in case (ii).

This identity can be generalized for any second order linear recurrence l_{n} = al_{n−1} + bl_{n−2} which has l_{0} = 1 and l_{1} = a.

Our last identity counts tilings which contain at least one horizontal domino.

Identity 6. For n ≥ 2,

(i) k_{n} − 2^{n} = ∑_{i=0}^{n−2} k_{i}(2^{n−i−2} + 2^{n−i} − 2)

(ii) k_{n}^{a,b} − (a^{2} + b)^{n} = ∑_{i=0}^{n−2} k_{i}(b^{2}(a^{2} + b)^{n−i−2} + 2(b(a^{2} + b)^{n−i−1} − b^{n−i})).

Proof. Once again, statement (i) is the case a = 1, b = 1 of statement (ii). The left-hand side counts the number of tilings with at least one horizontal domino. If a tiling has no horizontal dominoes, then each column contains either a vertical domino or two squares. There are n columns and a^{2} + b possibilities for each column, so there are (a^{2} + b)^{n} such tilings. The right-hand side also counts tilings with at least one horizontal domino. To show this, we condition on the rightmost break with at least one horizontal domino to its right. Say this break occurs at column i; we allow i = 0 if there is no such break within the tiling. There are k_{i}^{a,b} ways to fill in the first i columns of such a tiling. If the n − i columns after this break begin with two stacked horizontal dominoes, we have b^{2} possibilities for these first two dominoes and (a^{2} + b)^{n−i−2} possibilities for the remaining columns.

Otherwise, the tiling of the last n − i columns begins with an unbreakable tiling of length j (j ≥ 2) containing two squares and j − 1 dominoes. Let’s consider the case when the first of the two squares appears in the top row; the case when the first square appears in the bottom row is handled in the same way and accounts for the factor of 2 in the right-hand side of (ii). To make these tilings easier to count, turn this unbreakable segment into j − 1 vertical dominoes followed by one column of two squares. The m^{th} horizontal domino in the unbreakable tiling becomes the m^{th} vertical domino in the new tiling, and the first and second squares in the unbreakable tiling become the top and bottom squares, respectively, in column j of the new tiling. Finally, append the remaining n−i−j columns of the original tiling to this new tiling. Now we have a tiling of a (2 × (n − i))-board that begins with a vertical domino and contains no horizontal dominoes.

This process is almost invertible. Start with a tiling of a (2 × (n − i))-board that begins with a vertical domino and has no horizontal dominoes; there are b(a^{2} + b)^{n−i−1} such tilings.

Say it starts with l consecutive columns of vertical dominoes (l ≥ 1) followed by a column of two squares. Turn these l dominoes and two squares into an unbreakable tiling of length l+1, putting the top square in the first column of the unbreakable tiling and the bottom square in the last column and turning the m^{th} vertical domino into the m^{th} horizontal domino. Append the remaining n − i − l − 1 columns to create a (2 × (n − i))-board with an unbreakable tiling of length l + 1 followed by n − i − l − i columns with no horizontal dominoes. The only tilings that cannot undergo this process are those that do not begin with some number of vertical dominoes followed by a column of two squares. These are the tilings that use only vertical dominoes, and there are b^{n−i} of these. Thus we have the right-hand side.

In the case a = 0, b = 1, this is the Fibonacci recurrence f_{n} − 1 = ∑_{i=0}^{n−2} f_{i}.

4 Equivalent Tilings on a (1 × n)-board

Benjamin and Quinn [2, Section 3.5] give an interpretation of any jth order linear recurrence in terms of weighted (1×n)-tilings. In this setting, McQuistan and Lichtman’s recurrence in equation (1) describes the tilings of a (1 × n)-board with squares of three colors, dominoes of one color, and (3 × 1) trominoes of one color with the following condition: if the tile in column 1 is a square, it can be Color 1 or Color 2 but not Color 3. The weight of an individual tiling is 1 if the tiling has an even number of trominoes and −1 if it has an odd number of trominoes. A tiling with a negative weight counts negatively toward the total number of (1×n)-tilings. For example, when n = 3 there are 24 unweighted tilings: 2×3×3 with three squares, 2 × 1 with one square followed by one domino, 1 × 3 with one domino followed by one square, and 1 with one tromino. Since the tiling with a single tromino has weight −1, the total number of weighted tilings is 22, which is indeed k_{3}.

Because these two types of tilings are both counted by k_{n}, we looked for a correspondence between them.

Theorem 2. There is a one-to-one correspondence between the tilings of a (2×n)-board with squares and dominoes and the weighted tilings of a (1 × n)-board described above which do not contain either a tromino or a domino followed immediately by a square of Color 3. The weights of the (1 × n)-tilings which do contain a tromino or a domino followed immediately by a Color 3 square sum to 0.

Proof. We begin with a (1 × n)-tiling with does not contain either a tromino or a domino followed immediately by a square of Color 3 and use it to construct a tiling of a (2×n)-board with squares and dominoes. See Figure 4 for an example.

1. If column i of the (1 × n)-tiling contains a Color 1 square then put two squares in column i of the (2 × n)-board.

2. If column i of the (1 × n)-tiling contains a Color 2 square then put a vertical domino in column i of the (2 × n)-board.

3. If columns i and i + 1 of the (1 × n)-tiling contain a domino then put two horizontal dominoes across columns i and i + 1 of the (2 × n)-board.

4. If column i in the (1 × n)-tiling is a Color 3 square then the action depends on what is in column i − 1 of the (1 × n)-tiling. (Recall that a Color 3 square will never appear in column 1.)

(a) If column i − 1 in the (1 × n)-tiling contains a Color 1 square, then remove the lower square in column i − 1 of the (2 × n)-tiling, place a horizontal domino in the bottom row of columns i − 1 and i, and place a square in the top row of column i.

(b) If column i − 1 in the (1 × n)-tiling contains a Color 2 square, then remove the vertical domino in column i − 1 of the 2 × n tiling, place a horizontal domino in the top row of columns i − 1 and i, and place squares in the bottom row of columns i − 1 and i.

(c) If column i − 1 in the (1 × n)-tiling contains another Color 3 square and if column i − 2 contains a Color 1 or Color 2 square, then column i − 1 of the (2 × n)-tiling contains one square in one row and the second half of a horizontal domino in the other row. (See (a) and (b) above.) Remove the square and use a horizontal domino to fill in this position and the neighboring position in column i. Fill the remaining position in column i with a square. Because this operation leaves column i with a square and the second half of a horizontal domino, we can continue to apply this operation for any number of Color 3 squares in a row, creating an unbreakable segment in the (2 × n)-tiling. Since a sequence of Color 3 squares must be preceded by either a Color 1 square or a Color 2 square, we have covered all possibilities.

This procedure is invertible, so we have a one-to-one correspondence. Now we need to show that the weights of the (1 × n)-tilings which do contain a tromino or a domino followed immediately by a Color 3 square sum to 0. Given such a (1 × n)-tiling, find the rightmost occurrence of either a tromino or a domino followed by a Color 3 square. If it is a tromino, replace it with a domino and Color 3 square, and vice versa. The original tiling and the new tiling have weights of opposite sign, since one has one more tromino than the other. Since all the tilings under consideration can be paired this way, their weights sum to 0.

Figure 4: A transformation of a (1 × 10)-board to a (2 × 10)-board by the rules above.

5 Future Work

In this paper, we have extended earlier work on (2 × n)-tilings to colored tilings, proved several identities, and connected (2 × n)-tilings to weighted (1 × n)-tilings. There is still more to be learned about the sequences k_{n} and k_{n}^{a,b}. We have begun exploring the roots of the characteristic equation x^{3}−(a^{2}+2b)x^{2}−a^{2}bx+b^{3} = 0, which lead to an expression for k_{n}^{a,b} that is analogous to the Binet formula for the Fibonacci numbers. Since lim_{n→∞} k_{n+1}^{a,b}/k_{n}^{a,b} is one of these roots, we would like to be able to say more about them for various values of a and b. We would also like to know more about the arithmetic properties of k_{n} and k_{n}^{a,b}. Identity 3 shows that the parity of k_{n} alternates. It is straightforward to use the recurrence relation in Theorem 1 to check the behavior of the parity of k_{n}^{a,b} for different combinations of odd and even a and b, but we expect there is a good deal more to be said in this area. Finally, this general approach should extend to boards of other shapes and sizes.

6 Acknowledgments

Thanks to Art Benjamin for the discussion that led to this proof of Theorem 1. Thanks to an anonymous referee for several helpful comments, including the observation about parity and Identity 3. Thanks to Henry Escuadro for suggesting that we look at squares and dominoes, and especially to James Sellers for his talk on Pell numbers and for his comments on earlier versions of this work.

References

[1] Arthur T. Benjamin, Sean S. Plott, and James Sellers, Tiling proofs of recent sum identities involving Pell numbers, Ann. Comb., 12 (2008) 271–278.

[2] Arthur T. Benjamin and Jennifer J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.

[3] Richard A. Brualdi, Introductory Combinatorics, 4th edition, Pearson Prentice Hall, 2004.

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

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

[6] N. J. A. Sloane, (2008), The On-Line Encyclopedia of Integer Sequences, available at

   http://www.research.att.com/~njas/sequences/

2000 Mathematics Subject Classification: Primary 05A19; Secondary 05A15, 05B45. Keywords: dominoes, tiling, Fibonacci numbers, Pell numbers.

Concerned with sequences \underline{A000045}, \underline{A000129}, and \underline{A030186}. Received November 20 2008; revised version received January 14 2009. Published in Journal of Integer Sequences, January 16 2009. Return to Journal of Integer Sequences home page.