The Tilings of a (2 × n)-Board and Some New Combinatorial Identities

Reza Kahkeshani Department of Pure Mathematics Faculty of Mathematical Sciences University of Kashan Kashan Iran

                 kahkeshanireza@kashanu.ac.ir

Abstract We know that the Fibonacci numbers count the tilings of a (1×n)-board by squares and dominoes, or equivalently, the number of tilings of a (2×n)-board by dominoes. We use the tilings of a (2 × n)-board by colored unit squares and dominoes to obtain some new combinatorial identities. They are generalization of some known combinatorial identities and in the special case give us the Fibonacci identities.

1 Introduction

The Fibonacci numbers (\underline{A000045}), (F_{n})_{n≥0}, are the sequence defined by F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2 [3, 4]. It is easy to see that the tilings of a (1 × n)-board with (1 × 1) squares and (1 × 2) dominoes can be counted by the Fibonacci numbers. In fact, if f_{n} counts such tilings then f_{n} = F_{n+1}. From now on, we use the word “square(s)” to mean “(1 × 1) square(s)”. The Pell numbers (\underline{A000129}) are defined by P_{0} = 0, P_{1} = 1, and for n ≥ 2, P_{n} = 2P_{n−1} + P_{n−2}. The Pell number P_{n+1} counts the tilings of a (1 × n)-board with dominoes and two colors of squares. Benjamin, Quinn, Plott, and Sellers [1, 2] proved a number of combinatorial identities using these interpretations. McQuistan and Lichtman [6] also studied the tilings of a (2 × n)-board by squares and dominoes for placing dimers on a lattice and proved that

k_{n} = 3k_{n−1} + k_{n−2} − k_{n−3}

⋯; ⋯; 1 2  n  \begin{aligned}& & … \\ & & … \\ 1 & 2 & & n \end{aligned}

Figure 1: A (2 × n)-board and a pruned (2 × n)-board.

for n ≥ 3, where k_{n} is the number of such tilings (see Cipra’s comment on (\underline{A030186}) in OEIS [7]). In following, Katz and Stenson [5] investigated the tilings of a (2 × n)-board by colored squares and dominoes. They [5] obtained the recurrence relation

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} (n ≥ 3)

with the initial values k_{0}^{a,b} = 1, k_{1}^{a,b} = a^{2} + b and k_{2}^{a,b} = a^{4} + 4a^{2}b + 2b^{2}, where k_{n}^{a,b} is the number of tilings of a (2 × n)-board by a colors of squares and b colors of dominoes. Clearly, k_{n} = k_{n}^{1,1}. Moreover, they showed that the generating function of k_{n}^{a,b} is

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

(see (\underline{A253265}) in OEIS [7] for a comment) and proved the following combinatorial identities:

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

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

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

Since k_{n}^{0,1} = f_{n}, these identities in the special case give us the Fibonacci identities [5].

In this paper, we explore the tilings of a (2 × n)-board by colored squares and dominoes and obtain some new combinatorial identities according to the style of Benjamin and Quinn [2]. Moreover, we show that they are generalization of some famous Fibonacci identities.

2 Some combinatorial identities

Consider once again a (2 × n)-board and, with a scissor, cut out only a square in the last column of the top row (see Figure 1). Let l_{n}^{a,b} count the tilings of such board using a colors of squares and b colors of dominoes. Clearly, l_{1}^{a,b} = a and l_{2}^{a,b} = a^{3} + 2ab. Also, l_{n}^{0,b} = 0. There are two cases for the tilings of a pruned (2 × n)-board, those ending with a horizontal … …

1 2  ···  n

\begin{aligned}& & … \\ & & … \\ 1 & 2 & ··· & n \end{aligned}  \begin{aligned}& & … \\ & & … \\ 1 & 2 & ··· & n \end{aligned}

\begin{aligned}& & … \\ & & … \\ 1 & 2 & ··· & n \end{aligned}  \begin{aligned}& & … \\ & & … \\ 1 & 2 & ··· & n \end{aligned}

Figure 2: The endings for obtaining a recurrence relation for l_{n}^{a,b}.

\begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & i \end{aligned}  \begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & i \end{aligned}

\begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & i \end{aligned}  \begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & i \end{aligned}

Figure 3: To prove Identity 2, condition on the location of the last domino.

domino in the bottom row and those ending with a square in the bottom row. This implies that

l_{n}^{a,b} = bl_{n−1}^{a,b} + ak_{n−1}^{a,b}  (1)

for n ≥ 2. Replacing n by 1 in (1), we have l_{0}^{a,b} = 0. Moreover, (1) shows that the tilings of a pruned (2 × n)-board which end with a square in the bottom row are counted by l_{n}^{a,b} − bl_{n−1}^{a,b}. Now we can obtain a recurrence relation for l_{n}^{a,b}.

Theorem 1. For n ≥ 3, l_{n}^{a,b} = (a^{2} + 2b)l_{n−1}^{a,b} + a^{2}bl_{n−2}^{a,b} − b^{3}l_{n−3}^{a,b}.

Proof. By definition, there are l_{n}^{a,b} tilings for a pruned (2 × n)-board. On the other hand, we have five cases for the endings of these tilings:

(i) There is a domino in the ending of the bottom row. Clearly, they are counted by bl_{n−1}^{a,b}.

(ii) There are a square in column n and a vertical domino in column n − 1. By removing column n − 1, it is seen that these tilings correspond to the tilings of a pruned (2 × (n − 1))- board which end with a square in the bottom row. According to the above note, we have b(l_{n−1}^{a,b} − bl_{n−2}^{a,b}) such tilings.

⋯

⋯

no square

\begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & i \end{aligned}  \begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & i \end{aligned}

\begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & i \end{aligned}  \begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & i \end{aligned}

⋯  ⋯
⋯  ⋯
i

Figure 4: To prove Identity 3, condition on the location of the last square.

(iii) There are two squares in the ending of the bottom row. The number of these tilings is a^{2}l_{n−1}^{a,b}.

(iv) Two horizontal dominoes are in columns n − 2 and n − 1 and a square is in column n. If we remove these horizontal dominoes then it is seen that they are corresponded to b^{2}(l_{n−2}^{a,b} − bl_{n−3}^{a,b}) tilings of a pruned (2 × (n − 2))-board which end with a square in the bottom row.

(v) The top row ends with a square and the bottom row ends with a horizontal domino followed by a square. Here, the number of tilings is a^{2}bl_{n−2}^{a,b}.

Now by summing over all cases, we get the right-side of the recurrence relation. See

\begin{matrix}⋯ & ⋯ \\ ⋯ & ⋯ \\ 1 & m \\  &  \end{matrix}\begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & m \end{aligned}

\begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & m \end{aligned}  \begin{aligned}⋯ & & ⋯ \\ ⋯ & & ⋯ \\ & m \end{aligned}

Figure 5: To see Identity 4, count the (m + n)-tilings based on breakability at cell m.

⋯  ⋯  ⋯  ⋯
⋯  ⋯  ⋯  ⋯
x_{0}  x_{1}  ···  x_{i}

Figure 6: To see Identity 5, consider all of the vertical dominoes.

Figure 2.

It is easy to find that the generating function for l_{n}^{a,b} is

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

The following proofs, as we shall see, are based on the double counting principle such that one of the ways of counting breaks the problem into disjoint cases.

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

Proof. Consider the tilings of a (2 × n)-board with at least one domino. There are k_{n}^{a,b} − a^{2n} such tilings. On the other hand, there are four cases for the location of the last domino as shown in Figure 3:

(i) The last domino is vertical. If the last domino occupies column i (1 ≤ i ≤ n) then cells 1 through i − 1 in the both rows can be tiled in k_{i−1}^{a,b} ways, column i must be covered by one of the b colored dominoes and remainder cells must be covered in a^{2(n−i)} ways. Thus, the number of tilings in this case is ∑_{i=1}^{n} ba^{2(n−i)}k_{i−1}^{a,b}.

(ii) The last domino is horizontal in the first row. If the last domino covers cells i − 1 and i in the first row, where 2 ≤ i ≤ n, then cell i in the second row must be covered by a square. So, cells 1 through i − 2 in the first row and cells 1 through i − 1 in the second row can be together tiled in l_{i−1}^{a,b} ways and remainder cells must be covered by squares in a^{2(n−i)} ways. So, the number is ∑_{i=2}^{n} baa^{2(n−i)}l_{i−1}^{a,b}.

(iii) The last domino is horizontal in the second row. This is similar to (ii).

(iv) The last domino is horizontal in the both rows. If cells i − 1 and i in the both rows coverd by two horizontal dominoes (2 ≤ i ≤ n) then cells 1 through i − 2 can be covered in k_{i−2}^{a,b} ways and cells i + 1 through n in the both rows must be tiled by squares. So, there are ∑_{i=2}^{n} b^{2}a^{2(n−i)}k_{i−2}^{a,b} such tilings.

Now we sum over all cases to get the identity.

Identity 3. k_{n}^{a,b} = k_{n}^{0,b} + 2ab ∑_{i=2}^{n} l_{i−1}^{a,b}k_{n−i}^{0,b} + a^{2} ∑_{i=1}^{n} k_{i−1}^{a,b}k_{n−i}^{0,b}.

Proof. The left-hand side of this identity counts the tilings of a (2 × n)-board. On the other hand, we obtain the right-hand side by conditioning on the location of the last square. There are four cases as shown in Figure 4:

(i) There is no square in the tiling. Obviously, we have k_{n}^{0,b} of these.

(ii) The last square is in the first row. If the last square covers column i then we have two subcases for the second row: either cells i − 1 and i tiled by a domino (2 ≤ i ≤ n) or cells i and i + 1 tiled by a domino (1 ≤ i ≤ n − 1). In the first subcase, cells 1 through i − 1 in the first row and cells 1 through i − 2 in the second row can be together covered in l_{i−1}^{a,b} ways and moreover, cells i + 1 through n in the both rows must be tiled in k_{n−i}^{0,b} ways. Thus, there is ∑_{i=2}^{n} abl_{i−1}^{a,b}k_{n−i}^{0,b} such tilings. In the second subcase, the pruned board in columns i + 1 to n must be tiled in l_{n−i}^{0,b} ways. But l_{n−i}^{0,b} = 0 and this subcase will not occur.

(iii) The last square is in the second row. This is similar to (ii).

(iv) The last square is in the both rows. If the last square is in column i of the both rows (1 ≤ i ≤ n) then we have no restriction in the left-hand side of column i and cells i+1 through n in the both rows must be together tiled only by dominoes. So, there are ∑_{i=1}^{n} a^{2}k_{i−1}^{a,b}k_{n−i}^{0,b} of these tilings.

Now, by summing over all cases, we get the identity.

Identity 4, as illustrated below, depends on the notion of breakability. A tiling of a (2 × n)-board is breakable at column i if we can decompose the tiling into two tilings, one covering columns 1 through i and the other covering columns i + 1 through n. Otherwise, we call the tiling unbreakable.

Identity 4. k_{m+n}^{a,b} = k_{m}^{a,b}k_{n}^{a,b} + 2bl_{m}^{a,b}l_{n}^{a,b} + b^{2}k_{m−1}^{a,b}k_{n−1}^{a,b}.

Proof. We know that there are k_{m+n}^{a,b} tilings for a (2 × (m + n))-board. This gives us the left-side hand of the identity. On the other hand, let us condition on breakability at column m. There are four cases as shown in Figure 5:

(i) An (m + n)-tiling is breakable at column m. There are k_{m}^{a,b}k_{n}^{a,b} of these.

(ii) Only the first row causes the tiling be unbreakable. Thus, cells m and m + 1 in the first row are covered by a domino. Here, we have two pruned boards, the first in columns 1 through m and the second in columns m + 1 through m + n. So, there are bl_{m}^{a,b}l_{n}^{a,b} tilings.

(iii) Only the second row causes the tiling be unbreakable. This is similar to (ii).

(iv) The both rows cause the tiling be unbreakable. Thus, there are two horizontal dominoes covering columns m and m + 1. Therefore, cells 1 through m − 1 and cells m + 2 through m + n in the both rows can be tiled arbitary and we have b^{2}k_{m−1}^{a,b}k_{n−1}^{a,b} tilings.

Now we obtain the identity by summing over all cases.

Let J_{n}^{a,b} be the number of tilings of a (1 × n)-board by a colors of squares and b colors of dominoes. It is clear that J_{n}^{1,1} = f_{n} and

J_{n}^{0,1} = \begin{cases}0, & if n is odd; \\ 1, & if n is even. \end{cases}

Identity 5. k_{n}^{a,b} = ∑_{i=0}^{n} ∑_{x_{0}+x_{1}+···+x_{i}=n−i} b^{i} (J_{x_{0}}^{a,b})^{2} (J_{x_{1}}^{a,b})^{2} ⋯ (J_{x_{i}}^{a,b})^{2}.

Proof. There are k_{n}^{a,b} tilings for a (2×n)-board. On the other hand, condition on the number of vertical dominoes. Suppose that we have i vertical dominoes (0 ≤ i ≤ n) such that there are x_{0} columns to the left of the first vertical domino, x_{1} columns between the first and the second vertical dominoes, …, and finally, x_{i} columns to the right of the last vertical domino (see Figure 6). Thus, x_{0} + x_{1} + ⋯ + x_{i} = n − i and each (2 × x_{j})-subboard, where 0 ≤ j ≤ i, must be tiled by horizontal dominoes and squares. Since the rows in these subboards are sepapately tiled, there are b^{i}(J_{x_{0}}^{a,b})^{2}(J_{x_{1}}^{a,b})^{2} ⋯ (J_{x_{i}}^{a,b})^{2} ways to tile the (2 × n)-board. Now the assertion is implied by summing over all cases.

In the special case (a, b) = (0, 1), Identity 2 and Identity 4 reduce to the well-known formulas

f_{n} = f_{n−1} + f_{n−2}

and

f_{m+n} = f_{m−1}f_{n−1} + f_{m}f_{n},

respectively. Moreover, in the special cases (a, b) = (0, 1) and (a, b) = (1, 1), Identity 5 gives us the formulas

f_{n} = ∑_{i=0}^{n} A_{i,n}  (2)

and

k_{n} = ∑_{i=0}^{n} ∑_{x_{0}+x_{1}+···+x_{i}=n−i} f_{x_{0}}^{2}f_{x_{1}}^{2} ⋯ f_{x_{i}}^{2},  (3)

respectively, where A_{i,n} is the number of nonnegative even integer solutions to the equation x_{0} +x_{1} +⋯+x_{i} = n−i. By taking x_{i} = 2y_{i}, we can consider A_{i,n} as the nonnegative integer solutions to the equation y_{0} + y_{1} + ⋯ + y_{i} = (n − i)/2. Notice that n − i must be even since each x_{i} is even. Therefore, we get A_{i,n} = \binom{\frac{n+i}{2}}{i} by using a standard argument [3, 4], and (2) becomes

f_{n} = ∑_{i=0}^{n} \binom{\frac{n+i}{2}}{i}.  (4)

Depending on the parity of n, (4) gives the following known formulas:

f_{2n} = ∑_{k=0}^{n} \binom{n + k}{2k} and f_{2n−1} = ∑_{k=0}^{n−1} \binom{n + k}{2k + 1}

for n ≥ 0 and n ≥ 1, respectively [2, Identities 165–166]. Moreover, we can obtain (3) by repeated application of

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

which is due to Cipra [5, Identity 5(i)].

3 Concluding remarks

In this paper, we have considered a (2 × n)-board, examined its tilings by colored squares and dominoes and proved four identities. Our proofs are respectively based on these ideas: location of the last domino, location of the last square, breakability at a column and the number of vertical dominoes. Benjamin and Quinn [2, Chap. 1] have used more ideas on a (1 × n)-board and proved several identities. This suggests that further results on the tilings can be obtained if we can use the ideas discussed in [2] on a (2 × n)-board.

4 Acknowledgments

The author is partially supported by the University of Kashan under grant number 364996/2. The author would like to thank the anonymous referees for carefully reading the paper and specially for providing useful comments on identities 2–4 and equations (2) and (3) which have much improved the quality of this paper.

References

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

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

[3] R. A. Brualdi, Introductory Combinatorics, 5th edition, Pearson Prentice Hall, 2009.

[4] R. P. Grimaldi, Discrete and Combinatorial Mathematics, 5th edition, Addison Wesley, 2004.

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

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

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 05A15, 05B45, 11B39. Keywords: domino, tiling, Fibonacci number, combinatorial identity.

(Concerned with sequences \underline{A000045}, \underline{A000129}, and \underline{A030186}.)

Received May 17 2016; revised versions received October 14 2016; October 19 2016; March 28 2017. Published in Journal of Integer Sequences, April 8 2017.

Return to Journal of Integer Sequences home page.