New Combinatorial Interpretations of the Fibonacci Numbers Squared, Golden

Rectangle Numbers, and Jacobsthal Numbers Using Two Types of Tile

Kenneth Edwards and Michael A. Allen^{1} Physics Department Faculty of Science Mahidol University Rama 6 Road Bangkok 10400 Thailand

               kenneth.edw@mahidol.ac.th
                   maa5652@gmail.com

Abstract

We consider the tiling of an n-board (a board of size n × 1) with squares of unit width and (1, 1)-fence tiles. A (1, 1)-fence tile is composed of two unit-width square sub-tiles separated by a gap of unit width. We show that the number of ways to tile an n-board using unit-width squares and (1, 1)-fence tiles is equal to a Fibonacci number squared when n is even and a golden rectangle number (the product of two consecutive Fibonacci numbers) when n is odd. We also show that the number of tilings of boards using n such square and fence tiles is a Jacobsthal number. Using combinatorial techniques we prove new identities involving golden rectangle and Jacobsthal numbers. Two of the identities involve entries in two Pascal-like triangles. One is a known triangle (with alternating ones and zeros along one side) whose (n, k)th entry is the number of tilings using n tiles of which k are fence tiles. There is a simple relation between this triangle and the other which is the analogous triangle for tilings of an n-board. These triangles are related to Riordan arrays and we give a general procedure for finding which Riordan array(s) a triangle is related to. The resulting combinatorial interpretation of the Riordan arrays allows one to derive properties of them via combinatorial proof.

1Corresponding author.

1 Introduction

The (n+1)th Fibonacci number (\underline{A000045} in the On-Line Encyclopedia of Integer Sequences), defined by F_{n+1} = δ_{n,1} + F_{n} + F_{n−1}, F_{n<1} = 0, where δ_{i,j} is 1 if i = j and zero otherwise, can be interpreted as the number of ways to tile an n-board (a board of size n × 1 composed of 1 × 1 cells) with 1 × 1 squares (henceforth referred to simply as squares) and 2 × 1 dominoes [5, 4]. More generally, the number of ways to tile an n-board with all the r × 1 r-ominoes from r = 1 up to r = k is the k-step (or k-generalized) Fibonacci number F_{n+1}^{(k)} = δ_{n,1} + F_{n}^{(k)} + F_{n−1}^{(k)} + ⋯ + F_{n−k+1}^{(k)}, with F_{n<1}^{(k)} = 0 [4].

Edwards [6] showed that it is possible to obtain a combinatorial interpretation of the tribonacci numbers (the 3-step Fibonacci numbers, \underline{A000073}) as the number of tilings of an n-board using just two types of tile, namely, squares and (\frac{1}{2}, 1)-fence tiles. A (w, g)-fence tile is composed of two sub-tiles (called posts) of size w × 1 separated by a gap of size g × 1. We presented a bijection between the Fibonacci numbers squared (\underline{A007598}) and the tilings of an n-board with half-squares (i.e., \frac{1}{2} × 1 tiles always oriented so that the shorter side is horizontal) and (\frac{1}{2}, \frac{1}{2})-fence tiles [8] and this was used to formulate combinatorial proofs of various identities [8, 10]. Using two types of tile allows one to generate a Pascal-like triangle based on the tiling in a natural way [6], and one such triangle has been shown to be a row-reversed Riordan array [10].

Here we show that the number of ways to tile an n-board using square and (1, 1)-fence tiles is a Fibonacci number squared if n is even and a golden rectangle number (the product of two successive Fibonacci numbers, \underline{A001654}) if n is odd.

We also consider the number of ways to tile boards using a total of n of these tiles and refer to this as an n-tiling. We show that enumerating n-tilings yields the Jacobsthal numbers J_{n≥0} = 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, … (\underline{A001045}) where the nth Jacobsthal number is defined via

J_{n} = δ_{n,1} + J_{n−1} + 2J_{n−2}, J_{n<1} = 0.  (1)

We use both types of tiling to formulate straightforward combinatorial proofs of new identities involving the golden rectangle and Jacobsthal numbers, two of which involve entries in Riordan arrays. These arrays are shown to be related to two Pascal-like triangles (one for n-tilings, the other for tilings of an n-board) whose entries are the number of tilings with squares and (1, 1)-fences which use a given number of fences. This enables one to obtain straightforward combinatorial proofs of a number of properties of the arrays.

We begin by showing how to determine which row-reversed Riordan array corresponds to a given Pascal-like triangle derived from tiling with squares and fences.

2 Riordan arrays and tiling-derived Pascal-like triangles

A (p(x), q(x)) Riordan array, where p(x) = p_{0} + p_{1}x + p_{2}x^{2} + ⋯ and q(x) = q_{1}x + q_{2}x^{2} + ⋯, is an infinite lower triangular matrix whose (n, k)th entry, which we will denote by R(n, k), is given by R(n, k) = [x^{n}]p(x){q(x)}^{k}, where [x^{n}]g(x) is the coefficient of x^{n} in the series for g(x) [11]. Notice that the entries of the k = 0 column are given by R(n, 0) = p_{n}.

The entry T (n, k) of a Pascal-like triangle T associated with tiling with squares and fences gives the number of tilings containing k fences where n is either the length of the board or, when considering n-tilings, the number of tiles. We have found that the rowreversed triangle (or every other row of it) can coincide with a Riordan array [10]. The generating function of the leading diagonal of T is then the same as that of p(x). To find q, we first row reverse the recursion relation defining T. This is done by replacing term T (n−m, k −l) by R(n−m, n−m−k +l) and then replacing n−k by k. We then substitute in the result R(n − a, k − b) = [x^{n−a}]pq^{k−b} = [x^{n}]x^{a}pq^{k−b} and solve for q.

Example 1. Let T (n, k) be the number of tilings of an n-board using k (\frac{1}{2}, 1)-fences and n−k squares (\underline{A157897}). Then T (n, k) = δ_{n,0}δ_{k,0} +T (n−1, k)+T (n−2, k −1)+T (n−3, k −3) [6]. T (n, n) is 1 if n is a multiple of 3 and 0 otherwise. Hence p(x) = 1+x^{3}+x^{6}+⋯ = 1/(1−x^{3}). Row reversing the recursion relation gives

R(n, k) = δ_{n,0}δ_{k,0} + R(n − 1, k − 1) + R(n − 2, k − 1) + R(n − 3, k).

Substituting in the definition of R(n, k) and dividing by pq^{k−1} leaves q = x + x^{2} + x^{3}q, from which we get q = x(1 + x)/(1 − x^{3}).

3 Tiling boards with squares and fences

When tiling a board with fences, it is helpful to first determine the types of metatile, since any tiling of the board can be expressed as a tiling using metatiles [6]. A metatile is an arrangement of tiles that exactly covers an integral number of adjacent cells and cannot be split into smaller metatiles [6, 7]. When tiling with squares (S) and (1, 1)-fence tiles (henceforth referred to simply as fences or F), the simplest metatile is the square. To tile adjacent cells by starting with a single fence we must fill the gap with either a square or the post of another fence. These generate what we will refer to as the filled fence (F S) and bifence (F F) metatiles, respectively (Fig. 1). The filled fence and bifence have lengths of 3 and 4, respectively. A square which is not inside a filled fence (and is therefore a metatile) is called a free square.

Theorem 2. Let A_{n} be the number of ways to tile an n-board using squares and fences. Then

A_{n} = δ_{n,0} + A_{n−1} + A_{n−3} + A_{n−4}, A_{n<0} = 0.  (2)

Figure 1: An 8-board tiled with the three possible metatiles: a free square (cell 1), a filled fence (cells 2–4), and a bifence (cells 5–8). The symbolic representation of this tiling is SF SF F.

Proof. We condition on the last metatile [3, 7]. If the last metatile is of length l there will be A_{n−l} ways to tile the remaining n − l cells. The result (2) follows from the fact that there are three possible metatiles and these have lengths of 1, 3, and 4. If n = l there is exactly one tiling (which corresponds to that metatile filling the entire board) so we make A_{0} = 1. There is no way to tile an n-board if n < l and so A_{n<0} = 0.

A_{n≥0} = 1, 1, 1, 2, 4, 6, 9, 15, 25, 40, 64, 104, 169, 273, 441, 714, 1156, … is \underline{A006498}. As we will shortly prove combinatorially, the even (odd) terms of this sequence are the Fibonacci numbers squared \underline{A007598} (golden rectangle numbers \underline{A001654}).

Lemma 3. There is a bijection between the fence-square tilings of a 2n-board (a (2n + 1)- board) and the square-domino tilings of an ordered pair of n-boards (an (n + 1)-board and an n-board).

Proof. Tile an n-board (an (n+1)-board) with the contents of the odd-numbered cells of the given 2n-board ((2n + 1)-board) fence-square tiling and tile a second n-board (an n-board) with the contents of the even-numbered cells. The posts of any fence (which always lie on two consecutive odd or even cells) get mapped to a domino. The procedure is reversed by splicing the two square-domino tilings.

Theorem 4. For n ≥ 0,

A_{2n} = f_{n}^{2},  (3a)
A_{2n+1} = f_{n}f_{n+1},  (3b)

where f_{n} = F_{n+1}.

Proof. There are f_{n} ways to tile an n-board using squares and dominoes [4]. From Lemma 3, A_{2n} is the same as the number of ways to tile an ordered pair of n-boards using squares and dominoes which is f_{n}^{2}, and A_{2n+1} is the same as the number of ways to tile an n-board and (n + 1)-board using squares and dominoes which is f_{n}f_{n+1}.

As the result is used elsewhere [9], we now generalize Theorem 4 to the case of tiling an n-board with squares and (1, m − 1)-fences for some fixed m ∈ {2, 3, …}.

Theorem 5. If A_{n}^{(m)} is the number of ways to tile an n-board using squares and (1, m − 1)- fences then for n ≥ 0,

A_{mn+r}^{(m)} = f_{n}^{m−r}f_{n+1}^{r}, r = 0, …, m − 1,

where f_{n} = F_{n+1}.

Proof. We identify the following bijection between the tilings of a (mn + r)-board using squares and (1, m − 1)-fences and the square-domino tilings of an ordered m-tuple of r (n + 1)-boards followed by m − r n-boards. For convenience we number the boards in this m-tuple from 0 to m−1 and the cells in the (mn+r)-board from 0 to mn+r −1. Tile board j in the m-tuple with the contents (taken in order) of the cells of the given (mn + r)-board fence-square tiling whose cell number modulo m is j. The posts of any (1, m−1)-fence (which will always lie on two consecutive cells with the same cell number modulo m) get mapped to a domino in board j. The procedure is reversed by splicing the square-domino tilings of the m-tuple of boards, hence establishing the bijection. The number of square-domino tilings of the m-tuple of boards is f_{n+1}^{r}f_{n}^{m−r} and the result follows.

Theorem 6. If B_{n} is the number of n-tilings using squares and fences then

B_{n} = J_{n+1}.  (4)

Proof. As in the proof of Theorem 2, we condition on the last metatile. If the last metatile contains m tiles, there are B_{n−m} possible (n − m)-tilings. As the three possible metatiles contain 1, 2, and 2 tiles we have

B_{n} = δ_{n,0} + B_{n−1} + 2B_{n−2}, B_{n<0} = 0.  (5)

where the δ_{n,0} is to ensure that B_{0} = 1 so that when an n-tiling is just one metatile we count precisely one tiling. Comparing (5) with (1) gives the result.

4 Combinatorial proofs of new identities involving the golden rectangle numbers

The proofs of Identities 7 and 9 (and of Identities 10, 12, and 13 in the next section) follow the techniques used in [2, 10]. As far as we know, all these identities are new.

Identity 7. For n ≥ 0,

f_{n}f_{n+1} = 1 + ⌊n/2⌋ + ∑_{j=1}^{n} jf_{n−j}f_{n−j+1}.

Proof. How many tilings of a (2n + 1)-board contain at least two squares?

Answer 1: A_{2n+1} − \frac{1}{2}n − 1 (A_{2n+1} − \frac{1}{2}(n + 1)) if n is even (odd) since the only possible tilings with less than 2 squares when n is even (odd) is one free square (filled fence) among n/2 (\frac{1}{2}(n − 1)) bifences and there are \frac{1}{2}n − 1 (\frac{1}{2}(n + 1)) such tilings.

Answer 2: condition on the location of the second square. The metatile containing this must end on an even cell, 2j. Written in terms of symbols (see the caption to Fig. 1), the tiling of the first 2j cells must end in S. This leaves one S that may be placed anywhere among the F symbols which number j − 1. The number of ways to tile the cells to the right of the 2jth cell is A_{2n+1−2j}. Summing over all possible j gives ∑_{j=1}^{n} jA_{2(n−j)+1}.

Equating this to Answer 1 and simplifying gives

A_{2n+1} − ⌊n/2⌋ − 1 = ∑_{j=1}^{n} jA_{2(n−j)+1}.

The identity follows from (3b).

Note that if we consider the tilings of a 2n-board that contain at least two squares we obtain Identity 2.1 of [10].

To generalize Identity 7 we first define C_{n}^{(r)} as the number of ways to tile a (2n+1)-board using 2r + 1 squares (and n − r fences).

Lemma 8. For n ≥ r ≥ 0,

C_{n}^{(r)} = C_{n−2}^{(r)} + \binom{n + r}{2r}, C_{n<0}^{(r)} = 0.  (6)

Proof. In symbolic form, a tiling can end in either S or F F. If S, the number of ways to place the remaining 2r squares and n − r fences is \binom{n+r}{2r}. If F F, there are C_{n−2}^{(r)} ways to place the remaining tiles. There are no tilings if n < 0.

As will be shown in Theorem 43, C_{n}^{(r)} is the (n, r)th element of the (1/[(1 − x)(1 − x^{2})], x/(1 − x)^{2}) Riordan array (\underline{A158909}).

Identity 9. For p > 0, n > 0,

f_{n}f_{n+1} = ∑_{r=0}^{p−1} C_{n}^{(r)} + ∑_{j=p}^{n} \binom{j + p − 1}{2p − 1}f_{n−j}f_{n+1−j}.

Proof. How many tilings of a (2n + 1)-board have at least 2p squares?

Answer 1: the total number of tilings minus the tilings that contain less than 2p squares, i.e., A_{2n+1} − ∑_{r=0}^{p−1} C_{n}^{(r)}.

Answer 2: we condition on the location of the 2pth square. If the metatile containing this lies on the 2jth cell, in the symbolic representation, there are 2p − 1 S and j − p F that precede the 2pth S and hence \binom{j+p−1}{2p−1} ways to arrange them. There are A_{2n+1−2j} ways to place the remaining tiles after the 2jth cell.

Summing over all possible j and equating the result to Answer 1 gives

A_{2n+1} − ∑_{r=0}^{p−1} C_{n}^{(r)} = ∑_{j=p}^{n} \binom{j + p − 1}{2p − 1}A_{2(n−j)+1},

and the identity follows from (3b).

5 Combinatorial proofs of new identities involving the Jacobsthal numbers

Identity 10. For n ≥ 0,

J_{n+1} = ⌈\frac{1}{2}(n + 1)⌉ + ∑_{j=1}^{n−1} jJ_{n−j}.

Proof. How many n-tilings have at least two squares?

Answer 1: B_{n} − \frac{1}{2}(n + 1) (B_{n} − \frac{1}{2}n − 1) when n is odd (even) since the possible tilings with one square when n is odd (even) are one filled fence (free square) placed among \frac{1}{2}(n−1) (\frac{1}{2}(n − 2)) bifences and there are \frac{1}{2}(n + 1) (n/2) such tilings, and the only possible tiling with no squares is the all-bifence tiling which only occurs when n is even.

Answer 2: condition on the second metatile containing an S. The symbolic representation of the tiling up to and including this must end in an S. If this S is the jth tile, there are j − 1 ways to order the symbols preceding it and thus (j − 1)B_{n−j} n-tilings.

Summing over all possible j, equating to Answer 1, and simplifying gives

B_{n} − ⌈\frac{1}{2}(n + 1)⌉ = ∑_{j=2}^{n}(j − 1)B_{n−j}.

The identity is obtained on replacing j by j + 1 and using Theorem 6.

As before, we can generalize Identity 10. We need the following definition and lemma. Let D_{n}^{(r)} be the number of n-tilings that contain exactly r squares. As the only tilings with no squares are the all-bifence tilings, for n > 0, D_{n}^{(0)} is 1 (0) when n is even (odd). For convenience we make D^{(0)}(0) = 1.

Lemma 11. For n ≥ r > 0,

D_{n}^{(r)} = D_{n−2}^{(r)} + \binom{n − 1}{r − 1}.  (7)

Proof. The symbolic representation of a tiling must end in either S or F F. If S, we are free to place the remaining n − 1 tiles (of which r − 1 are squares) in any order; this gives \binom{n−1}{r−1} possibilities. If F F, there are D_{n−2}^{(r)} ways to place the remaining tiles.

As will be shown in Theorem 28, D_{n}^{(r)} is the (1/(1 − x^{2}), x/(1 − x)) Riordan array (\underline{A059260}).

Identity 12. For p > 0, n > 0,

J_{n+1} = ∑_{r=0}^{p−1} D_{n}^{(r)} + ∑_{k=p}^{n} \binom{k − 1}{p − 1}J_{n+1−k}.

Proof. How many n-tilings have at least p squares?

Answer 1: the total number of tilings minus the tilings that contain less than p squares, i.e., B_{n} − ∑_{r=0}^{p−1} D_{n}^{(r)}.

Answer 2: we condition on the location of the pth square. If it is the kth tile, there are \binom{k−1}{p−1} ways to place the first k tiles and B_{n−k} ways to place the remaining tiles.

Summing over all possible k and equating the result to Answer 1 gives

B_{n} − ∑_{r=0}^{p−1} D_{n}^{(r)} = ∑_{k=p}^{n} \binom{k − 1}{p − 1}B_{n−k},

and the identity follows from Theorem 6.

Identity 13. For n > 0,

J_{n+1} = n + J_{n−1} + ∑_{k=3}^{n}(2k − 5)J_{n+1−k}.

Proof. For n > 0, how many n-tilings have at least two fences?

Answer 1: B_{n} − 1 − (n − 2 + 1) since only the all-square tiling and tilings with 1 filled fence among n − 2 squares have less than two fences.

Answer 2: condition on the location of the second fence. If it is the kth tile (k = 3, …, n − 1) and part of a filled fence or the first tile in a bifence, the first fence is part of a filled fence among k − 3 squares and hence there are 2(k − 2)B_{n−(k+1)} tilings for these cases. If the second fence is the end of a bifence and is the kth tile (k = 2, …, n), the tiles before the bifence are all squares and hence there are B_{n−k} tilings in this case.

Summing over all possible k, changing k to k − 1 in the first sum, and equating to Answer 1 gives

B_{n} − n = 2 ∑_{k=4}^{n}(k − 3)B_{n−k} + ∑_{k=2}^{n} B_{n−k} = B_{n−2} + ∑_{k=3}^{n}(2k − 5)B_{n−k}.

The identity then follows from Theorem 6.

Although perhaps not particularly novel, we include this final identity involving Jacobsthal numbers as it connects them with the Fibonacci numbers and is quick to prove.

Identity 14. For n ≥ 0,

J_{n+1} = F_{n+1} + ∑_{j=2}^{n} J_{j−1}F_{n+1−j}.

Proof. First note that the number of n-tilings with no bifences is given by S_{n} = δ_{0,n} +S_{n−1} + S_{n−2} and hence S_{n} = F_{n+1}. How many n-tilings have at least one bifence?

Answer 1: B_{n} − S_{n}.

Answer 2: condition on the last bifence. When the second fence it contains is the jth tile (j = 2, …, n) then the number of tilings is B_{j−2}S_{n−j}.

Summing over all possible j and equating this to Answer 1 gives

B_{n} − S_{n} = ∑_{j=2}^{n} B_{j−2}S_{n−j}.

The identity follows from applying S_{n} = F_{n+1} and Theorem 6.

6 A Pascal-like triangle giving the number of n-tilings using k fences

We define ⟨ \begin{matrix}n \\ k \end{matrix} ⟩ as the number of n-tilings which contain exactly k fences. We define ⟨ \begin{matrix}0 \\ 0 \end{matrix} ⟩ = 1 so that the result

B_{n} = ∑_{k=0}^{n} ⟨\begin{matrix}n \\ k \end{matrix}⟩  (8)

is valid for n ≥ 0. We also choose to make ⟨ \begin{matrix}n \\ k \end{matrix} ⟩ = 0 when k < 0 or n < k. The first 12 rows of the triangle whose entries are ⟨ \begin{matrix}n \\ k \end{matrix} ⟩ are shown in Figure 2. As will be shown later via its connection with a Riordan array, the triangle is sequence \underline{A059259}.

Identities 15–21 are easy to prove by enumerating the possible arrangements of metatiles in the available metatile positions and so we only show one proof by way of illustration.

Identity 15. For n ≥ 0, ⟨ \begin{matrix}n \\ 0 \end{matrix} ⟩ = 1.

Identity 16. For n ≥ 1, ⟨ \begin{matrix}n \\ 1 \end{matrix} ⟩ = n − 1.

The following two identities describe, respectively, the entries in the first and second diagonal of the triangle.

Identity 17. For n ≥ 0, ⟨ \begin{matrix}n \\ n \end{matrix} ⟩ is 1 if n is even and 0 otherwise.

Identity 18. For m > 0,

⟨\begin{matrix}2m − 1 \\ 2m − 2 \end{matrix}⟩ = ⟨\begin{matrix}2m \\ 2m − 1 \end{matrix}⟩ = m.

The following identity shows that the third diagonal of the triangle is \underline{A002620}.

n \ k  0 1 2 3 4 5 6 7 8 9 10 11 12
0  1
1  1 0
2  1 1 1
3  1 2 2 0
4  1 3 4 2 1
5  1 4 7 6 3 0
6  1 5 11 13 9 3 1
7  1 6 16 24 22 12 4 0
8  1 7 22 40 46 34 16 4 1
9  1 8 29 62 86 80 50 20 5 0
10  1 9 37 91 148 166 130 70 25 5 1
11  1 10 46 128 239 314 296 200 95 30 6 0
12  1 11 56 174 367 553 610 496 295 125 36 6 1
Figure 2: A Pascal-like triangle with entries ⟨ \begin{matrix}n \\ k \end{matrix} ⟩ (\underline{A059259}).

Identity 19. For m > 0,

⟨\begin{matrix}2m \\ 2m − 2 \end{matrix}⟩ = m^{2}; ⟨\begin{matrix}2m + 1 \\ 2m − 1 \end{matrix}⟩ = m(m + 1).

Proof. When 2 out of 2m tiles are squares there must be either m − 1 bifences and 2 free squares (totalling m + 1 metatile positions) or m − 2 bifences and 2 filled fences (giving m metatile positions). There are \binom{m+1}{2} places to put the squares in the first case and \binom{m}{2} ways to place the filled fences in the second. The total number of tilings is thus \binom{m}{2}+\binom{m+1}{2} = m^{2}. When 2 out of 2m + 1 tiles are squares, there must be m − 1 bifences, 1 filled fence, and 1 free square, and thus m + 1 metatile positions. There are therefore 2\binom{m+1}{2} = m(m + 1) ways to place the free square and filled fence.

The following two identities show that the third and fourth columns of the triangle are \underline{A000124} and \underline{A003600}, respectively.

Identity 20. For n ≥ 2, ⟨ \begin{matrix}n \\ 2 \end{matrix} ⟩ = \binom{n−2}{2} + n − 1.

Identity 21. For n ≥ 3, ⟨ \begin{matrix}n \\ 3 \end{matrix} ⟩ = \binom{n−3}{3} + 2\binom{n−2}{2}.

We now turn to obtaining a direct expression for an arbitrary entry in the triangle. If b, f, and s are, respectively, the numbers of bifences, filled fences, and free squares in an n-tiling using k fences then it is easily seen that

n = 2b + 2f + s,  (9a)
k = 2b + f.  (9b)

Identity 22. For n ≥ k ≥ 0,

⟨\begin{matrix}n \\ k \end{matrix}⟩ = \begin{cases}∑_{b=b_{min}}^{b_{max}} \binom{n − k + b}{k − b}\binom{k − b}{b}, & b_{min} ≤ b_{max}; \\ 0, & b_{min} > b_{max}, \end{cases}  (10)

where b_{min} = max(0, ⌈k − n/2⌉) and b_{max} = ⌊k/2⌋.

Proof. For given values of n and k we sum the number of tilings for all possible values of b. The maximum number of bifences b_{max} is obtained from (9b) when f is 0 or 1 depending on whether k is even or odd, respectively. Eliminating f from (9) gives b = \frac{1}{2}(2k − n + s). If 2k − n is negative, the minimum possible value of b is zero. Otherwise b_{min} is obtained when s is 0 or 1 when 2k − n is even or odd, respectively. From (9) we have that the total number of metatiles, b + f + s = n − k + b. The number of ways of tiling using b bifences, f filled fences, and s free squares is the multinomial coefficient \binom{b+f+s}{b, f, s} which may be re-expressed as a product of binomial coefficients written in terms of b, n, and k. There will be no possible values of b and therefore no tilings if b_{min} > b_{max}.

We can use the result to expand the Jacobsthal numbers as double sums of products of two binomial coefficients.

Corollary 23. For n ≥ 0,

J_{n+1} = ∑_{k=0}^{n} ∑_{b=max(0,⌈k−n/2⌉)}^{⌊k/2⌋} \binom{n − k + b}{k − b}\binom{k − b}{b}.

Proof. The result follows from (8), Theorem 6, and Identity 22.

The next two identities show in what sense the triangle is ‘Pascal-like’. Both have bijective proofs.

Identity 24. For n ≥ k > 0,

\binom{n}{k} = ⟨\begin{matrix}n \\ k \end{matrix}⟩ + ⟨\begin{matrix}n − 1 \\ k − 1 \end{matrix}⟩ .  (11)

Proof. Interpret \binom{n}{k} as the tilings of an (n+k)-board with k dominoes (D) and n−k squares (S). Proceeding from left to right along the board, replace DD by a bifence, DS by a filled fence, and then leave any of the remaining S as they are. Except for the case of a ‘left over’ single D at the right end of the board, this generates all possible n-tilings using k fences. If the (n + k)-board ends in an isolated D, ignore it and hence obtain a (n − 1)-tiling with k − 1 fences. In both cases the scheme is reversible.

Identity 25. For n > k > 0,

⟨\begin{matrix}n \\ k \end{matrix}⟩ = ⟨\begin{matrix}n − 1 \\ k \end{matrix}⟩ + ⟨\begin{matrix}n − 1 \\ k − 1 \end{matrix}⟩ .  (12)

Proof. An n-tiling such that n > k must contain a free square or filled fence. Construct a bijection between n-tilings using k fences and (n−1)-tilings using k or k−1 fences as follows. In the n-tiling find the final square. If it is free, remove it to obtain an (n − 1)-tiling with k fences. If the square is part of a filled fence, remove the fence to obtain an (n − 1)-tiling with k − 1 fences.

We now turn to the connection between the triangle and a Riordan array. We first need the following two identities.

Identity 26. For n ≥ r ≥ 0, ⟨ \begin{matrix}n \\ n−r \end{matrix} ⟩ = D_{n}^{(r)}.

Proof. The result follows from the definition of D_{n}^{(r)} since ⟨ \begin{matrix}n \\ n−r \end{matrix} ⟩ is also the number of n-tilings containing r squares.

Identity 27. For all n, k ∈ ℤ,

⟨\begin{matrix}n \\ k \end{matrix}⟩ = δ_{n,0}δ_{k,0} + ⟨\begin{matrix}n − 1 \\ k \end{matrix}⟩ + ⟨\begin{matrix}n − 2 \\ k − 1 \end{matrix}⟩ + ⟨\begin{matrix}n − 2 \\ k − 2 \end{matrix}⟩ .  (13)

Proof. We count ⟨ \begin{matrix}n \\ k \end{matrix} ⟩ by conditioning on the last metatile on the board. If the metatile contains m tiles of which j are fences, for the remaining tiles the number of (n − m)-tilings is ⟨ \begin{matrix}n−m \\ k−j \end{matrix} ⟩. Summing these for the three types of metatile gives the result.

Theorem 28. If R(n, k) is the (n, k)th entry of the (1/(1 − x^{2}), x/(1 − x)) Riordan array then

⟨\begin{matrix}n \\ k \end{matrix}⟩ = R(n, n − k).  (14)

Proof. We use the method explained in Section 2. From Identity 17, p = 1 + x^{2} + x^{4} + ⋯ = 1/(1 − x^{2}). Row-reversing (13) gives R(n, k) = δ_{n,0}δ_{k,0} + R(n − 1, k − 1) + R(n − 2, k − 1) + R(n − 2, k). Using R(n, k) = [x^{n}]pq^{k} and dividing by pq^{k−1} leaves q = x + x^{2} + x^{2}q, from which we get q = x/(1 − x).

From Identity 26, R(n, k) = D_{n}^{(k)}. In other words, a combinatorial interpretation of R(n, k) is the number of n-tilings that use k squares (and n − k (1, 1)-fences). Then from Lemma 11 we have for n ≥ k ≥ 0,

R(n, k) = R(n − 2, k) + \binom{n − 1}{k − 1}.  (15)

This allows us to prove a conjecture given in the OEIS entry for \underline{A059259} concerning \underline{A071921} which is the square array a(n, m) given by a(0, m ≥ 0) = 1,

a(n, m) = ∑_{r=0}^{m−1} \binom{n − 1 + 2r}{n − 1}.  (16)

Using our notation, the conjecture is as follows.

Identity 29. For m, n ≥ 0,

⟨\begin{matrix}n + 2m \\ 2m \end{matrix}⟩ = a(n, m + 1).

Proof. From Theorem 28, ⟨ \begin{matrix}n+2m \\ 2m \end{matrix} ⟩ = R(n + 2m, n). Repeatedly applying (7) gives

R(n + 2m, m) = \binom{n − 1 + 2m}{n − 1} + \binom{n − 1 + 2(m − 1)}{n − 1} + ⋯ + \binom{n − 1 + 2}{n − 1} + R(n, n).

Using the fact that R(n, n) = 1 the result follows from (16).

The (n, k)th entry, which we will denote here by [ \begin{matrix}n \\ k \end{matrix}]_{1/2}, of the Pascal-like triangle \underline{A123521} is the number of ways to tile an n-board using k (\frac{1}{2}, \frac{1}{2})-fences and 2(n−k) half-squares (with the shorter sides always horizontal) [10]. This triangle was also shown to be related to a Riordan array [10]. We now show that the [ \begin{matrix}n \\ k \end{matrix}]_{1/2} triangle can be obtained from the ⟨ \begin{matrix}n \\ k \end{matrix} ⟩ triangle by removing the odd downward diagonals of the latter which is equivalent to the following identity.

Identity 30. For n ≥ k ≥ 0,

[\begin{matrix}n \\ k \end{matrix}]_{1/2} = ⟨\begin{matrix}2n − k \\ k \end{matrix}⟩ .

Proof. The total post length of a (\frac{1}{2}, \frac{1}{2})-fence is 1. The entry [ \begin{matrix}n \\ k \end{matrix}]_{1/2} can also be viewed as counting the number of tilings that use k (\frac{1}{2}, \frac{1}{2})-fences and 2(n − k) half-squares since the total length occupied by the n tiles is k + 2(n − k)\frac{1}{2} = n. The entry ⟨ \begin{matrix}2n−k \\ k \end{matrix} ⟩ counts the number of tilings using k (1, 1)-fences and 2(n − k) squares. This latter tiling differs from the former only in that the tiles are twice the length.

7 A Pascal-like triangle giving the number of tilings of an n-board using k fences

We define [ \begin{matrix}n \\ k \end{matrix}] as the number of tilings of an n-board which contain exactly k fences (Fig. 3). We define [ \begin{matrix}0 \\ 0 \end{matrix} ] = 1 so that the result

A_{n} = ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}]  (17)

n \ k  0 1 2 3 4 5 6 7 8 9 10 11 12
0  1
1  1 0
2  1 0 0
3  1 1 0 0
4  1 2 1 0 0
5  1 3 2 0 0 0
6  1 4 4 0 0 0 0
7  1 5 7 2 0 0 0 0
8  1 6 11 6 1 0 0 0 0
9  1 7 16 13 3 0 0 0 0 0
10  1 8 22 24 9 0 0 0 0 0 0
11  1 9 29 40 22 3 0 0 0 0 0 0
12  1 10 37 62 46 12 1 0 0 0 0 0 0
Figure 3: A Pascal-like triangle with entries [ \begin{matrix}n \\ k \end{matrix}] (\underline{A335964}).

is valid for n ≥ 0. We also make [ \begin{matrix}n \\ k \end{matrix}] = 0 when k < 0 or n < k.

As a result of the following identity, the upward diagonals of the ⟨ \begin{matrix}n \\ k \end{matrix} ⟩ triangle are the rows of the [ \begin{matrix}n \\ k \end{matrix}] triangle. Equivalently, column k of the [ \begin{matrix}n \\ k \end{matrix}] triangle is obtained by displacing column k of the ⟨ \begin{matrix}n \\ k \end{matrix} ⟩ triangle downwards by k (and filling the entries above with zeros). Thus we again obtain sequences \underline{A000124} and \underline{A003600} for the k = 2 and k = 3 columns, respectively (Identities 35 and 36).

Identity 31. For n ≥ k ≥ 0,

[\begin{matrix}n \\ k \end{matrix}] = ⟨\begin{matrix}n − k \\ k \end{matrix}⟩ .

Proof. If a tiling contains n − k tiles of which k are fences, the total length is n.

The even rows of the triangle [ \begin{matrix}n \\ k \end{matrix}] give the triangle [ \begin{matrix}n \\ k \end{matrix}]_{1/2} (defined just before Identity 30).

Identity 32. For n ≥ k ≥ 0,

[\begin{matrix}2n \\ k \end{matrix}] = [\begin{matrix}n \\ k \end{matrix}]_{1/2} .

Proof. The number of tilings of a 2n-board with squares and (1, 1)-fences is the same as the number of tilings of an n-board with tiles of half the length.

The proofs of Identities 33–37, as with Identities 15–21, involve a straightforward counting of arrangements of metatiles and are therefore omitted.

Identity 33. For n > 0, [ \begin{matrix}n \\ 0 \end{matrix} ] = 1.

Identity 34. For n > 2, [ \begin{matrix}n \\ 1 \end{matrix} ] = n − 2.

Identity 35. For n > 3, [ \begin{matrix}n \\ 2 \end{matrix} ] = \binom{n−4}{2} + n − 3.

Identity 36. For n > 5, [ \begin{matrix}n \\ 3 \end{matrix} ] = \binom{n−6}{3} + 2\binom{n−5}{2}.

Identity 37. For m > 0, [ \begin{matrix}4m−3 \\ 2m−2 \end{matrix} ] = [ \begin{matrix}4m−1 \\ 2m−1 \end{matrix} ] = m.

For the general term in the triangle, we can follow a similar method to that used to obtain Identity 22. However, a more elegant approach (which leads to different sums of products of two binomial coefficients) can be used to prove the following two identities.

Identity 38. For n ≥ k ≥ 0,

[\begin{matrix}2n + 1 \\ k \end{matrix}] = ∑_{j=k−m}^{m} \binom{n + 1 − j}{j}\binom{n − (k − j)}{k − j},

where m = min(⌊(n + 1)/2⌋, k).

Proof. From Lemma 3, [ \begin{matrix}2n+1 \\ k \end{matrix}] is also the number of square-domino tilings of an (n+1)-board and an n-board using k dominoes in total. The number of ways to tile an (n + 1)-board with j dominoes (and n + 1 − 2j squares) is \binom{n+1−j}{j}. If the (n + 1)-board has j dominoes then the n-board will have k − j dominoes (and n − 2(k − j) squares). Hence there are \binom{n+1−j}{j}\binom{n−(k−j)}{k−j} ways to tile the boards if the (n + 1)-board has j dominoes. Evidently j cannot exceed k or ⌊(n + 1)/2⌋ and so m ≥ j ≥ k − m. We then sum over all possible values of j.

Identity 39. For n ≥ k ≥ 0,

[\begin{matrix}2n \\ k \end{matrix}] = ∑_{j=k−m}^{m} \binom{n − j}{j}\binom{n − (k − j)}{k − j},

where m = min(⌊n/2⌋, k).

Proof. The proof is analogous to that of Identity 38.

Identity 39 is equivalent to Identity 3.2 in [10]. Evidently, summing Identities 38 and 39 over all possible k will, respectively, give ways of expressing f_{n}f_{n+1} and f_{n}^{2} as double sums of products of two binomial coefficients.

Before showing that the reversed odd rows of the triangle are a Riordan array we need the following two results. (Note that the even rows of the triangle have already been shown to be the row-reversed (1/(1 − x^{2}), x/(1 − x)^{2}) Riordan array [10].)

Identity 40. For n ≥ r ≥ 0, [ \begin{matrix}2n+1 \\ n−r \end{matrix}] = C_{n}^{(r)}.

Proof. The result follows from the definition of C_{n}^{(r)} since [ \begin{matrix}2n+1 \\ n−r \end{matrix}] is also the number of ways to tile a (2n + 1)-board using 2r + 1 squares.

Identity 41. For all n, k ∈ ℤ,

[\begin{matrix}n \\ k \end{matrix}] = [\begin{matrix}n − 1 \\ k \end{matrix}] + [\begin{matrix}n − 3 \\ k − 1 \end{matrix}] + [\begin{matrix}n − 4 \\ k − 2 \end{matrix}] + δ_{0,k}δ_{0,n}.  (18)

Proof. We count [ \begin{matrix}n \\ k \end{matrix}] by conditioning on the last metatile on the board. If the metatile is of length l and contains j fences, the number of ways to tile the remaining n − l cells with k − j fences is [ \begin{matrix}n−l \\ k−j \end{matrix}]. Summing these for the three types of metatile gives the result.

To show that C_{n}^{(r)} is a Riordan array we first need a recursion relation that involves only the odd rows of the triangle.

Identity 42. For all n, k ∈ ℤ,

[\begin{matrix}2n + 1 \\ k \end{matrix}] = [\begin{matrix}2n − 1 \\ k \end{matrix}] + [\begin{matrix}2n − 1 \\ k − 1 \end{matrix}] + [\begin{matrix}2n − 3 \\ k − 1 \end{matrix}] + [\begin{matrix}2n − 3 \\ k − 2 \end{matrix}] − [\begin{matrix}2n − 5 \\ k − 3 \end{matrix}] + δ_{0,k}δ_{0,n}. (19)

Proof. Let E(n, k) denote (18). Then E(2n + 1, k) + E(2n, k) − E(2n − 1, k − 1) gives the identity.

Theorem 43. If R̄(n, k) is the (n, k)th entry of the (1/[(1 − x)(1 − x^{2})], x/(1 − x)^{2}) Riordan array then

[\begin{matrix}2n + 1 \\ k \end{matrix}] = R̄(n, n − k).  (20)

Proof. From Identity 37, the leading diagonal of the odd rows of the triangle has the generating function p = 1 + x + 2x^{2} + 2x^{3} + ⋯ = 1/[(1 − x)(1 − x^{2})]. Row reversing (19) and making n label the odd rows gives R̄(n, k) = δ_{n,0}δ_{k,0} + R̄(n − 1, k − 1) + R̄(n − 1, k) + R̄(n − 2, k − 1) + R̄(n − 2, k) − R̄(n − 3, k). Substituting in R(n, k) = [x^{n}]pq^{k} and dividing by pq^{k−1} leaves q = x + xq + x^{2} + x^{2}q − x^{3}q, from which we get q = x/(1 − x)^{2}.

From Identity 40, R̄(n, k) = C_{n}^{(k)}. In other words, a combinatorial interpretation of R̄(n, k) is the number of tilings of a (2n + 1)-board that use 2k + 1 squares (and 2(n − k) (1, 1)-fences). Then from Lemma 8 we have for n ≥ k ≥ 0,

R̄(n, k) = R̄(n − 2, k) + \binom{n + k}{2k}.  (21)

8 Discussion

In Sections 4 and 5 we only presented identities that appear to be new. Some other known identities are easily obtained via techniques based on those given in the book by Benjamin and Quinn [4]. These include considering tilings that have at least one type of tile or metatile and then conditioning on the position of the final tile or metatile of that type.

Various generalizations of the tilings examined here can be made. The simplest of these is tiling an n-board with white squares, black squares, and (1, 1)-fences. This gives the Pell numbers squared (\underline{A079291}) when n is even and products of consecutive Pell numbers (\underline{A114620}) when n is odd; the overall sequence is \underline{A089928}. The number B_{n} of n-tilings in this case is given by B_{n} = δ_{n,0} + 2B_{n−1} + 3B_{n−2} (\underline{A015518}). Tiling with squares and (m − 1, 1)-fences when m > 2 (see Theorem 5) results in an infinite number of possible metatiles. Provided one can arrive at an expression for the numbers of metatiles of a given length, interesting identities can be obtained simply [9]. Note that although Theorem 5 tells us what sequence such a tiling of an n-board corresponds to, we do not have an equivalent theorem determining the sequence for the number of n-tilings using such tiles.

Another approach for obtaining p and q for a Riordan array is via the so-called A and Z sequences [12, 1]. This relies on having an expression for R(n, k) given in terms of entries of the (n − 1)-th row. This is not always available with tiling triangles; it is in the case of ⟨ \begin{matrix}n \\ k \end{matrix} ⟩ (see Identity 25) but not for [ \begin{matrix}n \\ k \end{matrix}]. The procedure described in Section 2 will not always yield a Riordan array corresponding to a row-reversed tiling triangle. It can only succeed if the generating function for the leading diagonal of the triangle can be found and an expression for q can obtained explicitly; if the recursion relation is of high order then this is unlikely. It is also necessary that q is of the form q = q_{1}x + q_{2}x^{2} + · · ·.

References

[1] P. Barry, Riordan Arrays: A Primer, lulu.com, 2017.

[2] A. T. Benjamin, J. Crouch, and J. A. Sellers, Unified tiling proofs of a family of Fibonacci identities, Fibonacci Quart. 57 (2019), 29–31.

[3] A. T. Benjamin, C. R. H. Hanusa, and F. E. Su, Linear recurrences through tilings and Markov chains, Utilitas Math. 64 (2003), 3–17.

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

[5] R. C. Brigham, R. M. Caron, P. Z. Chinn, and R. P. Grimaldi, A tiling scheme for the Fibonacci numbers, J. Recreational Math. 28 (1996), 10–16.

[6] K. Edwards, A Pascal-like triangle related to the tribonacci numbers, Fibonacci Quart. 46/47 (2008/2009), 18–25.

[7] K. Edwards and M. A. Allen, Strongly restricted permutations and tiling with fences, Discrete Appl. Math. 187 (2015), 82–90.

[8] K. Edwards and M. A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Fibonacci Quart. 57 (5) (2019), 48–53.

[9] K. Edwards and M. A. Allen, A new combinatorial interpretation of the Fibonacci numbers cubed, Fibonacci Quart. 58 (5) (2020), 128–134.

[10] K. Edwards and M. A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared. Part II, Fibonacci Quart. 58 (2020), 169–177.

[11] L. W. Shapiro, S. Getu, W.-J. Woan, and L. C. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991), 229–239.

[12] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 11B39. Keywords: Fibonacci identity, Jacobsthal identity, combinatorial proof, combinatorial identity, n-tiling, Pascal-like triangle, Riordan array.

(Concerned with sequences \underline{A000045}, \underline{A000073}, \underline{A000124}, \underline{A000930}, \underline{A001045}, \underline{A001654}, \underline{A002620}, \underline{A003269}, \underline{A003600}, \underline{A006498}, \underline{A007598}, \underline{A015518}, \underline{A017817}, \underline{A059259}, \underline{A059260}, \underline{A071921}, \underline{A079291}, \underline{A089928}, \underline{A114620}, \underline{A123521}, \underline{A157897}, \underline{A158909}, and \underline{A335964}.)

Received September 9 2020; revised version received September 12 2020; March 4 2021; March 5 2021. Published in Journal of Integer Sequences, March 10 2021.

Return to Journal of Integer Sequences home page.