On Two Families of Generalizations of Pascal’s Triangle

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

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

Abstract

We consider two families of Pascal-like triangles that have all ones on the left side and ones separated by m − 1 zeros on the right side. The m = 1 cases are Pascal’s triangle and the two families also coincide when m = 2. Members of the first family obey Pascal’s recurrence everywhere inside the triangle. We show that the m-th triangle can also be obtained by reversing the elements up to and including the main diagonal in each row of the (1/(1 − x^{m}), x/(1 − x)) Riordan array. Properties of this family of triangles can be obtained quickly as a result. The (n, k)-th entry in the m-th member of the second family of triangles is the number of tilings of an (n + k) × 1 board that use k (1, m − 1)-fences and n − k unit squares. A (1, g)-fence is composed of two unit square sub-tiles separated by a gap of width g. We show that the entries in the antidiagonals of these triangles are coefficients of products of powers of two consecutive Fibonacci polynomials and give a bijective proof that these coefficients give the number of k-subsets of {1, 2, …, n − m} such that no two elements of a subset differ by m. Other properties of the second family of triangles are also obtained via a combinatorial approach. Finally, we give necessary and sufficient conditions for any Pascal-like triangle (or its row-reversed version) derived from tiling (n × 1)-boards to be a Riordan array.

1Corresponding author.

1 Introduction

Pascal’s triangle, whose entries \binom{n}{k} satisfy Pascal’s recurrence,

\binom{n}{k} = \binom{n − 1}{k} + \binom{n − 1}{k − 1},

is also the (1/(1 − x), x/(1 − x)) Riordan array. 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 (where n ≥ 0, k ≥ 0) is denoted and defined by (p(x), q(x))_{n,k} = [x^{n}]p(x)(q(x))^{k}, where the coefficient operator [x^{n}] gives the coefficient of x^{n} in the series expansion of the term it precedes [17, 3]. We define the row-reversed (p, q) Riordan array as the lower triangular matrix obtained by reversing the elements of each row up to and including the main diagonal of the (p, q) Riordan array, i.e., the (n, k)-th element of the row-reversed (p, q) Riordan array is (p(x), q(x))_{n,n−k} for 0 ≤ k ≤ n and 0 for k > n. Notice that whereas the definition of a (p, q) Riordan array implies that the zeroth column of the array gives the coefficients of the generating function of p(x), it is the main diagonal of the row-reversed Riordan array where these coefficients appear. Owing to the symmetry of its rows, Pascal’s triangle is also the row-reversed (1/(1 − x), x/(1 − x)) Riordan array. Note, however, that in general, a row-reversed Riordan array is not necessarily a Riordan array.

Pascal’s triangle also has tiling interpretations. The (n, k)-th entry (when written as a lower triangular matrix with the first 1 taken as the (0, 0)-th entry) is the number of squareand-domino tilings of N-boards for any N (where an N-board is a linear array of N unit square cells) that use n tiles in total of which k are dominoes (and therefore n−k are squares). This is easily seen since there are \binom{n}{k} ways to choose which k of the n tiles are dominoes. As there are 2^{n} different possible square-and-domino n-tile tilings, one immediately has a combinatorial proof that ∑_{k=0}^{n} \binom{n}{k} = 2^{n} [4]. Also, the k-th entry in the n-th antidiagonal (i.e., \binom{n−k}{k}) is the number of tilings of an n-board that use k dominoes and n − 2k squares. The number of ways to tile an n-board using squares and dominoes is the Fibonacci number f_{n} given by f_{n} = f_{n−1} +f_{n−2} when n > 0, f_{0} = 1, f_{n<0} = 0 (\underline{A000045} in the OEIS [18]). This is one way to show that the sum of elements of the n-th antidiagonal of Pascal’s triangle is f_{n} [4].

A (w, g)-fence is a tile composed of two sub-tiles (called posts) of dimensions w ×1 which are separated by a gap of width g. Fences have been used to give tiling interpretations of various sequences [6, 8, 9, 11]. They have also been employed in combinatorial proofs relating to strongly restricted permutations [7] and a probability problem [5].

A (1, m − 1)-fence for m = 2, 3, … can be regarded as a generalization of a domino since the m = 1 case is effectively a domino. If one creates a Pascal-like triangle by specifying that the (n, k)-th entry is the number of n-tile tilings of boards that use k (1, 1)-fences and n − k squares one arrives at the triangle \underline{A059259} whose entries satisfy Pascal’s recurrence [11] (Fig. 1). The triangle is also the row-reversed (1/(1−x^{2}), x/(1−x)) Riordan array. One naturally asks whether the triangle generated by tiling boards with (1, m − 1)-fences and

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 1: The start of a Pascal-like triangle (\underline{A059259}) whose (n, k)-th entry, \binom{n}{k}_{2} = ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{2}, is the (n, k)-th element of the row-reversed (1/(1 − x^{2}), x/(1 − x)) Riordan array and also the number of n-tile tilings using k (1, 1)-fences (and n − k squares). Entries in bold font (and those in bold font in Figs. 4 and 5) are covered by identities in §7.

squares for a given fixed m is the row-reversed (1/(1 − x^{m}), x/(1 − x)) array. The answer for m > 2, as we will show here, is no, and so we obtain two separate families of triangles which only coincide for the m = 1, 2 cases. However, one feature that the families have in common is their sides: the left sides are all ones and the right side of the m-th member of each family is the repetition of 1 followed by m − 1 zeros.

Our main concern here are triangles generated from tiling with squares and (1, m − 1)- fences. However, for completeness, in §2 we look at triangles with the sides specified above that obey Pascal’s recurrence everywhere in the interior. These turn out to be the same as the row-reversed (1/(1 − x^{m}), x/(1 − x)) Riordan arrays. The start of the section also serves as an introduction to §8 where we discuss in general which tiling-derived triangles can be Riordan arrays or their row-reversed versions, and the remainder of §2 gives us the opportunity to illustrate how to obtain generating functions for sums of antidiagonals and bivariate generating functions for row-reversed Riordan arrays which does not seem to have been addressed elsewhere in the literature. In §3 we introduce the tiling-derived family of triangles along with a closely related family which is helpful in proving some of the properties of the triangles; the rows of the latter family are the antidiagonals of the former. The tiling-derived triangles are shown to be related to Fibonacci polynomials and restricted combinations in §4 and §5, respectively. In §6 we give general results on tiling with squares and (1, m − 1)-fences which are used in the proofs of identities in §7.

n \ k  0 1 2 3 4 5 6 7 8 9 10 11 12
0  1
1  1 0
2  1 1 0
3  1 2 1 1
4  1 3 3 2 0
5  1 4 6 5 2 0
6  1 5 10 11 7 2 1
7  1 6 15 21 18 9 3 0
8  1 7 21 36 39 27 12 3 0
9  1 8 28 57 75 66 39 15 3 1
10  1 9 36 85 132 141 105 54 18 4 0
11  1 10 45 121 217 273 246 159 72 22 4 0
12  1 11 55 166 338 490 519 405 231 94 26 4 1
Figure 2: The start of a Pascal-like triangle (\underline{A118923}) with entries \binom{n}{k}_{3}.

2 Triangles obtained from Pascal’s recurrence

We denote the (n, k)-th entry of the m-th member of our first family of generalizations of Pascal’s triangle by \binom{n}{k}_{m}. By definition, we require that for n ≥ 0, \binom{n}{0}_{m} = 1 and \binom{n}{n}_{m} = 1 if n is a multiple of m and 0 otherwise, and that inside the triangle we have

\binom{n}{k}_{m} = \binom{n − 1}{k}_{m} + \binom{n − 1}{k − 1}_{m}, 0 < k < n.  (1)

For m = 1, …, 5 the triangles are Pascal’s triangle (\underline{A007318}), \underline{A059259}, \underline{A118923}, \underline{A349839}, and \underline{A349841}, respectively. The starts of the m = 2, 3, 4 triangles are displayed in Figs. 1, 2, and 3, respectively.

In the following theorem we link this family of triangles to Riordan arrays. To do so we need the result that if

(p, q)_{n,k} = A_{0}(p, q)_{n−1,k−1} + A_{1}(p, q)_{n−1,k} + ⋯ + A_{j}(p, q)_{n−1,k−1+j} + ⋯,  (2)

where A_{0}, A_{1}, A_{2}, … form the so-called A-sequence [16] and are the coefficients of the generating function A(x), then q(x) = xA(q(x)) [19, Theorem 1.3].

Theorem 1. For m ≥ 1, the triangle whose entries are \binom{n}{k}_{m} as defined above is the rowreversed (1/(1 − x^{m}), x/(1 − x)) Riordan array.

Proof. Row-reversing the elements of the triangle gives a lower triangular matrix whose zeroth column is the repetition of 1 followed by m − 1 zeros, i.e., the coefficients of the series expansion of 1/(1 − x^{m}). Hence if the triangle is a row-reversed (p, q) Riordan array then p = 1/(1 − x^{m}). Rewriting the recursion relation (1) in terms of the elements of the

n \ k  0 1 2 3 4 5 6 7 8 9 10 11 12
0  1
1  1 0
2  1 1 0
3  1 2 1 0
4  1 3 3 1 1
5  1 4 6 4 2 0
6  1 5 10 10 6 2 0
7  1 6 15 20 16 8 2 0
8  1 7 21 35 36 24 10 2 1
9  1 8 28 56 71 60 34 12 3 0
10  1 9 36 84 127 131 94 46 15 3 0
11  1 10 45 120 211 258 225 140 61 18 3 0
12  1 11 55 165 331 469 483 365 201 79 21 3 1
Figure 3: The start of a Pascal-like triangle (\underline{A349839}) with entries \binom{n}{k}_{4}.

row-reversed array gives (p, q)_{n,n−k} = (p, q)_{n−1,n−1−k} + (p, q)_{n−1,n−k} which on replacing n − k by k gives

(p, q)_{n,k} = (p, q)_{n−1,k−1} + (p, q)_{n−1,k}.

Hence A(x) = 1 + x and so q = xA(q) = x(1 + q) from which q = x/(1 − x).

A number of properties of the triangles can then be obtained easily. The first of these follows immediately from the definition of a Riordan array.

Corollary 2. For m ≥ 1 and 0 ≤ k ≤ n,

\binom{n}{k}_{m} = [x^{n}]\frac{1}{1 − x^{m}} (\frac{x}{1 − x})^{n−k} .  (3)

The next result is a more explicit expression for the (n, k)-th entry in the triangles.

Corollary 3. For m ≥ 1 and 0 ≤ k < n,

\binom{n}{k}_{m} = ∑_{j=0}^{⌊k/m⌋} \binom{n − mj − 1}{n − k − 1}.  (4)

Proof. We start with the definition of the (n, k)-th element of the Riordan array which for k > 0 gives

(\frac{1}{1 − x^{m}} , \frac{x}{1 − x})_{n,k} = [x^{n}]\frac{1}{1 − x^{m}} \frac{x^{k}}{(1 − x)^{k}} = [x^{n−k}]\frac{1}{1 − x^{m}} \frac{1}{(1 − x)^{k}}

= [x^{n−k}] ∑_{j=0}^{∞} x^{mj} ∑_{r=0}^{∞} \binom{k + r − 1}{r}x^{r}.

To obtain the coefficient of x^{n−k} we only require the r = n − k − mj term in the sum over r, and as r cannot be negative, j cannot exceed (n − k)/m. This leaves

(\frac{1}{1 − x^{m}} , \frac{x}{1 − x})_{n,k} = ∑_{j=0}^{⌊(n−k)/m⌋} \binom{n − mj − 1}{n − k − mj} = ∑_{j=0}^{⌊(n−k)/m⌋} \binom{n − mj − 1}{k − 1}.

The result then follows from Theorem 1.

The k-th column of a (p, q) Riordan array, whose generating function is pq^{k}, becomes the k-th subdiagonal (counting the main diagonal as the zeroth subdiagonal) of the row-reversed (p, q) Riordan array after removing the initial k zeros. Hence the corresponding generating function is p(x)(q(x)/x)^{k} and we have the following result.

Corollary 4. For m ≥ 1 and k ≥ 0 the generating function for the k-th subdiagonal of the m-th triangle is 1/((1 − x^{m})(1 − x)^{k}).

The next result follows from the fact that the generating function for the sums of the rows of a (p, q) Riordan array (and therefore also the corresponding row-reversed array) is p(x)/(1 − q(x)) [19].

Corollary 5. The generating function g_{r}(x) for the row sums of the m-th triangle (where m ≥ 1) is given by

g_{r}(x) = \frac{1 − x}{(1 − x^{m})(1 − 2x)} = \frac{1}{(1 + x + ⋯ + x^{m−1})(1 − 2x)}.  (5)

From (5), the recursion relation giving r_{n}, the sum of the n-th row, can be expressed as, for n > 1, r_{n} = 2r_{n−1} + r_{n−m} − 2r_{n−m−1} with r_{1} = 2 if m = 1 and r_{1} = 1 if m > 1, or as, for n > 0, r_{n} = r_{n−1} + ⋯ + r_{n−m+1} + 2r_{n−m}, where for both relations r_{0} = 1 and r_{n<0} = 0. For m = 1, …, 5 these correspond to the sequences \underline{A000079}, \underline{A001045}, \underline{A077947}, \underline{A115451}, and \underline{A349842}, respectively.

The remaining two corollaries require results that we prove in the appendix.

Corollary 6. For the m-th triangle (where m ≥ 1), the generating function g_{a} for the antidiagonal sums is given by

g_{a}(x) = \frac{1 − x^{2}}{(1 − x^{2m})(1 − x − x^{2})} = \frac{1}{(1 + x^{2} + ⋯ + x^{2(m−1)})(1 − x − x^{2})}.  (6)

Proof. The result follows from Lemma 38.

Thus the recursion relation for a_{n}, the sum of the n-th antidiagonal, can be written, for n ≠ 0, 2, as a_{n} = a_{n−1} +a_{n−2} +a_{n−2m} −a_{n−2m−1} −a_{n−2m−2} with a_{2} = 3 if m = 1 and a_{2} = 2 if m > 1, or, for n > 0, as a_{n} = a_{n−1} + a_{n−3} + ⋯ + a_{n−2m+1} + a_{n−2m}, where for both relations, a_{0} = 1 and a_{n<0} = 0. For m = 1, …, 5 these correspond to the sequences \underline{A000045}, \underline{A006498}, \underline{A079962}, \underline{A349840}, and \underline{A349843}, respectively.

n \ k  0  1  2  3  4  5  6  7  8  9 10 11 12 13
0  1
1  1  0
2  1  0  0
3  1  1  1  1
4  1  2  3  2  0
5  1  3  5  4  0  0
6  1  4  8  8  4  2  1
7  1  5 12 16 13  9  3  0
8  1  6 17 28 30 22  9  0  0
9  1  7 23 45 58 51 27  9  3  1
10  1  8 30 68 103 108 78 40 18  4  0
11  1  9 38 98 171 211 187 123 58 16  0  0
12  1 10 47 136 269 382 399 310 176 64 16  4  1
13  1 11 57 183 405 651 781 708 480 240 90 30  5  0
Figure 4: The start of a Pascal-like triangle (\underline{A350110}) with entries ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{3}.

Corollary 7. The bivariate generating function for the m-th triangle (where m ≥ 1) is given by

g_{m}(x, y) = \frac{1 − xy}{(1 − (xy)^{m})(1 − x − xy)} = \frac{1}{(1 + xy + ⋯ + (xy)^{m−1})(1 − x − xy)}. (7)

Proof. The result follows from Lemma 39.

Note that it is a generating function in the sense that \binom{n}{k}_{m} = [x^{n}y^{k}]g_{m}(x, y).

3 Triangles derived from tiling

For m = 1, 2, …, let ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m} denote the number of n-tile tilings that use k (1, m − 1)-fences (and n − k squares). We choose to make ⟨ \begin{matrix}0 \\ 0 \end{matrix} ⟩_{m} = 1 and for k < 0 or k > n, ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m} = 0. The starts of the m = 2, 3, 4 triangles are shown in Figs. 1, 4, and 5. The triangles m = 1, …, 5 are sequences \underline{A007318}, \underline{A059259}, \underline{A350110}, \underline{A350111}, and \underline{A350112}, respectively.

We can also create a triangle of [ \begin{matrix}n \\ k \end{matrix}]_{m} where this denotes the number of tilings of an n-board that use k (1, m − 1)-fences (and n − 2k squares). We also make [ \begin{matrix}0 \\ 0 \end{matrix} ]_{m} = 1. The two triangles are related via the following identity.

Identity 8. For m ≥ 1 and n ≥ k ≥ 0,

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

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

n \ k  0  1  2  3  4  5  6  7  8  9 10 11 12 13
0  1
1  1  0
2  1  0  0
3  1  0  0  0
4  1  1  1  1  1
5  1  2  3  4  2  0
6  1  3  6  7  4  0  0
7  1  4  9 12  8  0  0  0
8  1  5 13 20 16  8  4  2  1
9  1  6 18 32 36 28 19 12  3  0
10  1  7 24 50 69 69 58 31  9  0  0
11  1  8 31 74 120 144 127 78 27  0  0  0
12  1  9 39 105 195 264 265 189 81 27  9  3  1
13  1 10 48 144 300 458 522 432 270 132 58 24  4  0
Figure 5: The start of a Pascal-like triangle (\underline{A350111}) with entries ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{4}.

As a consequence of Identity 8, the antidiagonals of the ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m} triangle are the rows of the [ \begin{matrix}n \\ k \end{matrix}]_{m} triangle. In the rest of the paper we therefore only give identities for one of the two families of tiling triangles and choose ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m} as it is more ‘compact’ in the sense that its rows contain fewer trailing zeros. Some of the identities, however, are more straightforward to prove by considering the tiling of an n-board. The following bijection (which is established in the proof of Theorem 5 in [11]) will be used in such proofs. Note that for convenience in some of the proofs, we have extended the result to include r = m. This is clearly valid as it is equivalent to changing r to zero and increasing j by 1.

Lemma 9. For j ≥ 0 and r = 0, …, m, where m ≥ 1, there is a bijection between the tilings of an (mj + r)-board using k (1, m − 1)-fences and mj + r − 2k squares and the tilings of an ordered m-tuple of r (j + 1)-boards followed by m − r j-boards using k dominoes and mj + r − 2k squares.

Since a (1, 0)-fence is just a domino, ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{1} = \binom{n}{k} and so the corresponding triangle is Pascal’s triangle (\underline{A007318}), and [ \begin{matrix}n \\ k \end{matrix}]_{1} are the entries of the triangle \underline{A011973}.

4 Relation of tiling triangles to polynomials

Before examining the connection between the tiling triangles we consider here and polynomials, we give a general result connecting polynomials to triangles derived from arbitrary-length tilings when the set of possible metatiles is finite. A metatile is a grouping of tiles that completely covers an integer number of cells and cannot be split into smaller metatiles, and so any tiling of an integer-length board can be expressed as a tiling using metatiles [6]. For example, when tiling with squares and (1, 1)-fences (the m = 2 case), there are three types of metatile: the square tile on its own (a free square), a fence whose gap is filled by a square (a filled fence), and two interlocking fences (a bifence) [11].

We consider arbitrary-length tilings of boards that in general use at least two types of tile, some but not all of which are regarded as being special, and where the set of all possible metatiles is of finite size M. We then define the following polynomial:

p_{n}(x) = ∑_{i=1}^{M} x^{s_{i}}p_{n−l_{i}}(x) when n > 0, p_{0}(x) = 1, p_{n<0}(x) = 0,  (8)

where s_{i} is the number of special tiles in the i-th metatile, and l_{i} is the length of the i-th metatile. The following theorem (which is a generalization of Combinatorial Theorem 12 in the book by Benjamin and Quinn [4]) relates the coefficients of p_{n}(x) to the n-th row of the triangle whose (n, k)-th entry is the number of tilings of an n-board that use k special tiles.

Theorem 10. Let p(n, k) = [x^{k}]p_{n}(x) and let t(n, k) be the number of tilings of an n-board that use exactly k special tiles. Then p(n, k) = t(n, k) for all n and k.

Proof. Substituting p_{n}(x) = ∑_{k=0}^{∞} p(n, k)x^{k} into (8) gives

p_{n}(x) = δ_{n,0} + ∑_{i=1}^{M} ∑_{k=0}^{∞} p(n − l_{i}, k)x^{k+s_{i}} = δ_{n,0} + ∑_{i=1}^{M} ∑_{k=s_{i}}^{∞} p(n − l_{i}, k − s_{i})x^{k},

where δ_{i,j} is 1 if i = j and zero otherwise. Since p(n, k) = 0 if k < 0, the sum over k can instead start from zero. Then equating coefficients of x^{k} gives

p(n, k) = δ_{n,0}δ_{k,0} + ∑_{i=1}^{M} p(n − l_{i}, k − s_{i}).

For a tiling of an n-board containing k special tiles, if the final metatile has length l and contains s special tiles then there are t(n − l, k − s) ways to tile the rest of the board. Hence, summing over all possible metatiles,

t(n, k) = δ_{n,0}δ_{k,0} + ∑_{i=1}^{M} t(n − l_{i}, k − s_{i}),

where we regard there as being one way to tile a 0-board with no special tiles. Since there are no ways to tile an n-board with with k dominoes if k < 0, we also have t(n, k) = 0 if k < 0.

Example 11. When tiling an n-board with squares and (\frac{1}{2}, 1)-fences there are M = 3 types of metatile, namely, a square by itself, a fence with its gap filled by a square, and three interlocking fences [6]. If we regard the fence as the special tile, in this case we have l_{1} = 1, l_{2} = 2, l_{3} = 3, s_{1} = 0, s_{2} = 1, and s_{3} = 3. Hence row n in the triangle whose (n, k)-th entry is the number of tilings of an n-board that use k (\frac{1}{2}, 1)-fences (\underline{A157897}) gives the coefficients of one form of tribonacci polynomial t_{n}(x) which is given by

t_{n}(x) = t_{n−1}(x) + xt_{n−2} + x^{3}t_{n−3} when n > 0, t_{0}(x) = 1, t_{n<0}(x) = 0.

Remark 12. One can of course obtain an analogous polynomial to (8) and an analogous result to Theorem 10 by instead considering n-tile tilings of boards in which case l_{i} is then the number of tiles that the i-th metatile contains.

We define the Fibonacci polynomials f_{n}(x) by

f_{n}(x) = f_{n−1}(x) + xf_{n−2}(x) when n > 0, f_{0}(x) = 1, f_{n<0}(x) = 0.  (9)

Note that Fibonacci polynomials are often instead defined as f̄_{n}(x) = xf̄_{n−1}(x) + f̄_{n−2}(x) when n > 0, f̄_{0} = 1, f̄_{n<0}(x) = 0, which leads to a different family of polynomials [4, p. 141]. The definition we use here gives f_{0}(x) = f_{1}(x) = 1, f_{2}(x) = 1 + x, f_{3}(x) = 1 + 2x, f_{4}(x) = 1 + 3x + x^{2}, f_{5}(x) = 1 + 4x + 3x^{2}, etc. It is clear from the definition that deg f_{n}(x) = ⌊n/2⌋. Notice also that putting x = 1 gives the sum of the coefficients and hence for both definitions, the sum of the coefficients is the Fibonacci number f_{n}.

The following Lemma (which is analogous to Combinatorial Theorem 12 concerning f̄_{n}(x) in the book by Benjamin and Quinn [4]) relates tilings of an n-board using squares and dominoes to the coefficients of f_{n}(x).

Lemma 13. Let f(n, k) = [x^{k}]f_{n}(x) and let t(n, k) be the number of tilings of an n-board with squares and dominoes that use exactly k dominoes. Then f(n, k) = t(n, k) for all n and k.

Proof. This and the corresponding polynomial (9) is a particular case of Theorem 10 and (8) where the metatiles are the square and domino and the special tile is the domino.

Note that when tiling an n-board with exactly k dominoes there will be n − k tiles in total. Counting the ways to place the k dominoes gives f(n, k) = \binom{n−k}{k} which is \underline{A011973}, and coefficients of ascending powers of x in f_{n}(x) therefore give the n-th antidiagonal of Pascal’s triangle (\underline{A007318}), counting the initial 1 in the triangle as the zeroth antidiagonal. The following theorem is a generalization of this result.

Theorem 14. For j ≥ 0, k ≥ 0, m ≥ 1, and r = 0, …, m − 1,

⟨\begin{matrix}mj + r − k \\ k \end{matrix}⟩_{m} = [x^{k}]f_{j}^{m−r}(x)f_{j+1}^{r}(x).  (10)

Proof. From Identity 8, [ \begin{matrix}mj+r \\ k \end{matrix}]_{m} = ⟨ \begin{matrix}mj+r−k \\ k \end{matrix} ⟩_{m}. From Lemma 9, [ \begin{matrix}mj+r \\ k \end{matrix}]_{m} equals the number of ways to tile an ordered m-tuple of r (j + 1)-boards followed by m − r j-boards using k dominoes (and mj + r − 2k squares). The number of such tilings of the m-tuple of boards is

∑_{\begin{matrix}k_{1}≥0, k_{2}≥0, ..., k_{m}≥0, \\ k_{1}+k_{2}+···+k_{m}=k \end{matrix}}(∏_{i=1}^{r} t(j + 1, k_{i}))( ∏_{i=r+1}^{m} t(j, k_{i}))

in which the first product is omitted when r = 0. The coefficient of x^{k} in f_{j+1}^{r}(x)f_{j}^{m−r}(x) is

[x^{k}](∏_{i=1}^{r} ∑_{k_{i}=0}^{⌊(j+1)/2⌋} f(j + 1, k_{i})x^{k_{i}})( ∏_{i=r+1}^{m} ∑_{k_{i}=0}^{⌊j/2⌋} f(j, k_{i})x^{k_{i}})

= [x^{k}] ∑_{k_{1}≥0,k_{2}≥0,...,k_{m}≥0}(∏_{i=1}^{r} f(j + 1, k_{i}))( ∏_{i=r+1}^{m} f(j, k_{i}))x^{k_{1}+k_{2}+···+k_{m}}

= ∑_{\begin{matrix}k_{1}≥0, k_{2}≥0, ..., k_{m}≥0, \\ k_{1}+k_{2}+···+k_{m}=k \end{matrix}}(∏_{i=1}^{r} f(j + 1, k_{i}))(∏_{i=1}^{r} f(j, k_{i})).

The result then follows from Lemma 13.

Our first identity, which gives the sums of the antidiagonals, follows immediately from Theorem 14.

Identity 15. For j ≥ 0, m ≥ 1, r = 0, …, m − 1,

∑_{k=0}^{⌊(mj+r)/2⌋} ⟨\begin{matrix}mj + r − k \\ k \end{matrix}⟩_{m} = f_{j}^{m−r}f_{j+1}^{r}.

5 Tiling and restricted combinations

We now turn to the problem of determining an expression for S^{(m)}(n, k), the number of subsets of ℕ_{n} = {1, …, n} of size k such that the difference of any two elements of the subset does not equal m. For example, S^{(1)}(3, 0) = S^{(1)}(3, 2) = 1 and S^{(1)}(3, 1) = 3 since the possible subsets of {1, 2, 3} satisfying the m = 1 restriction are {}, {1}, {2}, {3}, and {1, 3}. It has been established that S^{(1)}(n, k) = \binom{n+1−k}{k} [12], and there is a formula for S^{(m)}(n, k) in terms of sums of products of binomial coefficients [15] along with one in terms of products of powers of consecutive Fibonacci numbers for the number of subsets of ℕ_{n} of all sizes for a given m [13]. Here we will show that S^{(m)}(n, k) = ⟨ \begin{matrix}n+m−k \\ k \end{matrix} ⟩_{m} and hence obtain the latter of these previous results via combinatorial proof. We first establish the following bijection.

Lemma 16. For m, n ≥ 1 and k ≥ 0, there is a bijection between the k-subsets of ℕ_{n} such that all pairs of elements taken from a subset do not differ by m, and the tilings of an (n + m)-board with k (1, m − 1)-fences and n + m − 2k squares.

Proof. We label the cells of the (n+m)-board from 1 to n+m. If a k-subset contains element i then we place a fence so that its left post occupies cell i. Notice that if i = n then the right post occupies the final cell on the board. After placing fences corresponding to each element of the subset, the rest of the board is filled with squares of which there must be n + m − 2k. In reverse, the tiling of any (n + m)-board tiled with k fences will generate a k-subset where no two elements differ by m since the right post of a fence starting at cell i is on cell i + m which means it cannot be occupied by the left post of another fence.

Corollary 17. For m, n ≥ 1 and k ≥ 0, S^{(m)}(n, k) = ⟨ \begin{matrix}n+m−k \\ k \end{matrix} ⟩_{m}.

Proof. From Lemma 16, S^{(m)}(n, k) = [ \begin{matrix}n+m \\ k \end{matrix}]_{m}. Identity 8 then gives the result.

The next two corollaries follow from Theorem 14 and Identity 15, respectively.

Corollary 18. For j, k ≥ 0, m ≥ 1, r = 0, …, m−1, S^{(m)}(mj +r, k) = [x^{k}]f_{j+1}^{m−r}(x)f_{j+2}^{r}(x).

Corollary 19. For j ≥ 0, m ≥ 1, r = 0, …, m − 1, the number of subsets of ℕ_{mj+r} each of which lack pairs of elements that differ by m is f_{j+1}^{m−r}f_{j+2}^{r}.

6 Metatiles when tiling with squares and fences

The simplest metatiles are the free square (S), m interlocking fences with no gaps (F^{m}) which we will refer to as an m-fence (since the m = 2 and m = 3 cases have already been referred to as bifences [8, 11] and trifences [6, 9], respectively), and, for m > 1 and r = 1, …, m − 1, the filled r-fence (F^{r}S^{m−r}) which is r interlocking fences with the remaining gap filled with squares. We refer to a filled 1-fence (F S^{m−1}) simply as a filled fence. Note that a 1-fence is just a domino, and that S and F^{m−1}S are the only metatiles that contain a single square.

Figure 6: A 30-board tiled with all metatiles containing less than 6 tiles in the m = 3 case. Dashed lines show boundaries between metatiles. The symbolic representation is above each metatile.

When m = 1, the only metatiles are the two individual tiles themselves: a square and a domino. When m = 2, the metatiles are S, F S, and F^{2} [11]. For m > 2, in each case there are an infinite number of metatiles. However, when m = 3 (Fig. 6), aside from the simplest metatiles (S, F^{3}, F^{2}S, and F S^{2}) there is just one infinite sequence of metatiles, namely, F SF^{j−1}S for j > 1. To see this, notice that F S has a single remaining slot of unit width. This can be either filled with an S, which then completes the metatile, or with an F which again results in a unit-width slot at the end of the yet-to-be-completed metatile.

7 Further identities concerning entries in the n-tile tilings triangles

These first three identities follow immediately by considering properties of the simplest metatiles.

Identity 20. For n ≥ 0 and m ≥ 1, ⟨ \begin{matrix}n \\ 0 \end{matrix} ⟩_{m} = 1.

Proof. There is only one way to create an n-tile tiling without using any (1, m − 1)-fences: the all-square tiling.

Identity 21. For n ≥ 1 and m ≥ 1,

⟨\begin{matrix}n \\ 1 \end{matrix}⟩_{m} = \begin{cases}0, & if n < m; \\ n − m + 1, & if n ≥ m. \end{cases}

Proof. Any n-tile tiling using exactly 1 fence must have a filled fence which itself contains m tiles. Thus there can be no n-tile tilings using 1 fence that use less than m tiles. If n ≥ m, the tiling consists of a filled fence and n − m free squares which gives a total of n − m + 1 metatile positions in which the filled fence can be placed.

Identity 22. For n ≥ 0 and m ≥ 1, ⟨ \begin{matrix}n \\ n \end{matrix} ⟩_{m} = 1 if n is a multiple of m and 0 otherwise.

Proof. The only way to tile without squares is the all m-fence tiling which can only occur if the number of tiles is a multiple of m.

The pattern of zeros seen in the triangles is a result of the following identity.

Identity 23. For j ≥ 1, m ≥ 2, p = 1, …, m − 1, and r = 1, …, p,

⟨\begin{matrix}mj − r \\ mj − p \end{matrix}⟩_{m} = 0.

Proof. We first derive an expression for K, the maximum number of fences that can be used in the tiling of an (mJ + R)-board where R = 0, …, m − 1. From Lemma 9, K is also the maximum number of dominoes that can be used in the tiling of R (J + 1)-boards and m − R J-boards. Then it is easily seen that

K = \begin{cases}\frac{1}{2}mJ, & if J even; \\ \frac{1}{2}m(J − 1) + R, & if J odd. \end{cases}

From Identity 8,

⟨\begin{matrix}mj − r \\ mj − p \end{matrix}⟩_{m} = [\begin{matrix}2mj − r − p \\ mj − p \end{matrix}]_{m} .

If r + p > m, then 2mj − r − p = mJ + R where J = 2(j − 1) and R = 2m − r − p. Then K = m(j − 1) which is always less than mj − p. If r + p ≤ m then 2mj − r − p = mJ + R where J = 2j − 1 and R = m − r − p and so K = mj − p − r which is also always less than mj − p.

The following identity accounts for the rising and falling powers of ascending positive integers that form the right boundary of the nonzero parts of the triangles.

Identity 24. For j ≥ 1, m ≥ 1, and p = 0, …, m,

⟨\begin{matrix}m(j − 1) + p \\ m(j − 1) \end{matrix}⟩_{m} = ⟨\begin{matrix}mj \\ mj − p \end{matrix}⟩_{m} = j^{p}.

Proof. From Identity 8,

⟨\begin{matrix}m(j − 1) + p \\ m(j − 1) \end{matrix}⟩_{m} = [\begin{matrix}2m(j − 1) + p \\ m(j − 1) \end{matrix}]_{m} .

By Lemma 9, this is the number of ways to tile m − p boards of length 2(j − 1) and p boards of length 2(j − 1) + 1 with m(j − 1) dominoes and p squares. Putting j − 1 dominoes in each of the m boards leaves room for the remaining p squares in the set of p longer boards. On each of these boards there are j tiles and hence j ways to tile each of them leading to j^{p} ways to tile all the boards. From Identity 8 we have

⟨\begin{matrix}mj \\ mj − p \end{matrix}⟩_{m} = [\begin{matrix}2mj − p \\ mj − p \end{matrix}]_{m} = [\begin{matrix}m(2j − 1) + m − p \\ (m − p)j + p(j − 1) \end{matrix}]_{m} ,

which is also the number of ways to tile m − p 2j-boards and p boards of length 2j − 1 using (m − p)j + p(j − 1) dominoes and p squares. The 2j-boards are completely filled by j dominoes and the p (2j − 1)-boards each have j − 1 dominoes and one square which can be placed in j positions leading again to a total of j^{p} tilings for the set of boards.

Identity 25. For j ≥ 1 and m ≥ 1,

⟨\begin{matrix}mj + 1 \\ mj − 1 \end{matrix}⟩_{m} = mT_{j},

where T_{j} = j(j + 1)/2 is the j-th triangle number (\underline{A000217}).

Proof. From Identity 8, ⟨ \begin{matrix}mj+1 \\ mj−1 \end{matrix} ⟩_{m} = [ \begin{matrix}2mj \\ mj−1 \end{matrix} ]_{m}, which, from Lemma 9, is the number of ways to tile an m-tuple of 2j-boards with mj − 1 dominoes and 2 squares. As the boards are of even length, both squares must lie on the same board. On such a board there are j + 1 tiles in total which means there are \binom{j+1}{2} = j(j + 1)/2 possible ways to tile it. As there are m possible boards on which to place the two squares, the result follows.

Identity 26. For j ≥ 1 and m ≥ 2,

⟨\begin{matrix}mj + 2 \\ mj − 2 \end{matrix}⟩_{m} = \begin{cases}\binom{m}{2}, & if j = 1; \\ m\binom{j + 2}{4} + \binom{m}{2}\binom{j + 1}{2}^{2}, & if j > 1. \end{cases}

Proof. From Identity 8, ⟨ \begin{matrix}mj+2 \\ mj−2 \end{matrix} ⟩_{m} = [ \begin{matrix}2mj \\ mj−2 \end{matrix} ]_{m}, which, from Lemma 9, is the number of ways to tile an m-tuple of 2j-boards with mj −2 dominoes and 4 squares. If j > 1, all four squares can be on the same 2j-board which means there are j +2 tiles on that board and hence \binom{j+2}{4} tilings of it. With m boards to choose from, this gives the first term on the right-hand side of the identity for j > 1. The other possibility is that two of the boards have two squares each. There are \binom{j+1}{2} ways to tile each such board and \binom{m}{2} ways to choose the boards.

We find that ⟨ \begin{matrix}2n+2 \\ 2n−2 \end{matrix} ⟩_{2} is \underline{A006324}.

As the metatiles containing a given number of tiles are easily enumerated, it is straightforward to obtain recursion relations for the row sums and for the elements of the triangle in the m = 3 case, as shown in the proofs of the following two identities.

Identity 27. B_{n} = ∑_{k=0}^{n}⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{3}, the number of n-tile tilings using squares and (1, 2)-fences, satisfies

B_{n} = 2B_{n−1} − B_{n−2} + 3B_{n−3} − 2B_{n−4} when n > 1, B_{0} = B_{1} = 1, B_{n<0} = 0. (11)

Proof. We condition on the final metatile in the n-tile tiling. If it contains p tiles then there are B_{n−p} possibilities for the remaining tiles. The possible metatiles, namely, S, F^{3}, F^{2}S, F S^{2}, and F SF^{j−1}S for j > 1 contain 1, 3, 3, 3, and 2 + j tiles, respectively. Summing over these gives

B_{n} = δ_{n,0} + B_{n−1} + 3B_{n−3} + ∑_{p=4}^{n} B_{n−p},  (12)

where the δ_{n,0} is needed so that we obtain one tiling for each metatile with p tiles (putting n = p). Subtracting (12) with n replaced by n − 1 from (12) gives the identity.

Identity 28. For all n, k ∈ ℤ,

⟨\begin{matrix}n \\ k \end{matrix}⟩_{3} = δ_{n,0}δ_{k,0} − δ_{n,1}δ_{k,1} + ⟨\begin{matrix}n − 1 \\ k \end{matrix}⟩_{3} + ⟨\begin{matrix}n − 1 \\ k − 1 \end{matrix}⟩_{3} − ⟨\begin{matrix}n − 2 \\ k − 1 \end{matrix}⟩_{3} + ⟨\begin{matrix}n − 3 \\ k − 1 \end{matrix}⟩_{3} + ⟨\begin{matrix}n − 3 \\ k − 2 \end{matrix}⟩_{3}

+ ⟨\begin{matrix}n − 3 \\ k − 3 \end{matrix}⟩_{3} − ⟨\begin{matrix}n − 4 \\ k − 3 \end{matrix}⟩_{3} − ⟨\begin{matrix}n − 4 \\ k − 4 \end{matrix}⟩_{3} . (13)

Proof. We count ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{3} by conditioning on the last metatile on the board. If the metatile contains p tiles of which j are fences, for the remaining tiles the number of (n−p)-tile tilings is ⟨ \begin{matrix}n−p \\ k−j \end{matrix} ⟩_{3}. Summing over all possible metatiles gives

⟨\begin{matrix}n \\ k \end{matrix}⟩_{3} = δ_{n,0}δ_{k,0} + ⟨\begin{matrix}n − 1 \\ k \end{matrix}⟩_{3} + ⟨\begin{matrix}n − 3 \\ k − 3 \end{matrix}⟩_{3} + ⟨\begin{matrix}n − 3 \\ k − 1 \end{matrix}⟩_{3} + ⟨\begin{matrix}n − 3 \\ k − 2 \end{matrix}⟩_{3} + ∑_{p=4}^{n} ⟨\begin{matrix}n − p \\ k + 2 − p \end{matrix}⟩_{3} . (14)

Replacing n by n − 1 and k by k − 1 in (14) and then subtracting the resulting equation from (14) gives the identity.

Corollary 29. For n ≥ 2k + 1 when k ≥ 0,

⟨\begin{matrix}n \\ k \end{matrix}⟩_{3} = ⟨\begin{matrix}n − 1 \\ k \end{matrix}⟩_{3} + ⟨\begin{matrix}n − 1 \\ k − 1 \end{matrix}⟩_{3} .

Proof. We define what we might call a Pascal recurrence operator by

P (n, k) = ⟨\begin{matrix}n \\ k \end{matrix}⟩_{3} − ⟨\begin{matrix}n − 1 \\ k \end{matrix}⟩_{3} − ⟨\begin{matrix}n − 1 \\ k − 1 \end{matrix}⟩_{3} .

Notice that P (n, k) = 0 if the (n, k)-th entry of the triangle is the sum of the entry directly above it and the entry above and one place to the left. It can be seen that P (n, k < 0) = 0 and P (n > 0, 0) = 0. Rewriting (13) in terms of P (n, k) gives

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

and hence for k > 0 and r ≥ 0,

P (2k + 1 + r, k) = −P (2(k − 1) + 1 + r, k − 1) + P (2k − 2 + r, k − 3).

Applying this recursively until the second argument of P is zero or negative in each case, we see that the first term on the right-hand side will eventually generate (−1)^{k}P (1+r, 0) and all other terms will be of the form σP (a, 0) for various a > 1 + r or σP (a, b) with b ∈ {−1, −2} where σ is 1 or −1. Hence P (2k + 1 + r, k) = 0 for k ≥ 0 which is equivalent to the result we wish to prove.

The following conjecture has been shown to be true for the cases m = 1, 2, 3.

Conjecture 30. For n ≥ (m − 1)k + 1 when k ≥ 0,

⟨\begin{matrix}n \\ k \end{matrix}⟩_{m} = ⟨\begin{matrix}n − 1 \\ k \end{matrix}⟩_{m} + ⟨\begin{matrix}n − 1 \\ k − 1 \end{matrix}⟩_{m} .

8 Tiling triangles and Riordan arrays

It is well known that an array is a Riordan array if and only if there is an A-sequence as given by (2) in the present paper [16]. The problem with such a recursion relation in tilingtriangle applications is that the expression for a given element is in terms of elements only in the row above whereas the most readily obtained recursion relations for tiling triangles tend to be higher than first order in the row number n. In such cases, the following more general characterization of Riordan arrays (using an ‘A-matrix’ rather than an A-sequence) is needed to show whether or not a triangle (or its row-reversed version) is a Riordan array.

Theorem 31 (Theorem 2.5 of [14]). A matrix {R_{n,k}}_{n,k∈ℕ}, where ℕ = {0, 1, …}, is a Riordan array if and only if there is another matrix {A_{i,j}}_{i,j∈ℕ} with A_{0,0} ≠ 0 such that every R_{n,k} for n, k ≥ 1 can be expressed as R_{n,k} = ∑_{i≥1} ∑_{j≥−1} A_{i,j}R_{n−i,k+j}.

Notice that the above theorem means that an element in a Riordan array can depend on any elements above it as long as they are not more than 1 column before it. Remark 32. As the recursion relation for elements T (n, k) of tiling triangles are constructed by conditioning on the final metatile (as in the proof of Identity 28), such recursion relations will only involve terms T (n − a, k − b) where a, b ∈ ℕ. Furthermore, the tiling triangle will only be a lower triangular matrix (and hence it or its row-reversed version a candidate for a Riordan array) if a ≥ b. Recursion relations with terms having b > a can occur if k counts tiles whose sub-tiles have a total length of less than 1.

Theorem 33. Suppose a triangle is constructed by letting the (n, k)-th entry be the number of ways to tile an n-board that use k special tiles. The triangle is a Riordan array if and only if there is a metatile of length 1 that contains exactly one special tile and there is no metatile that contains more than one special tile. The triangle is a row-reversed Riordan array if and only if there is a metatile of length 1 that lacks special tiles and for all metatiles l − s is 0 or 1, where l is the length of the metatile and s is the number of special tiles it contains.

Proof. If T (n, k) is the (n, k)-th entry, then conditioning on the final metatile gives

T (n, k) = δ_{n,0}δ_{k,0} + ∑_{i} T (n − l_{i}, k − s_{i}),  (15)

where l_{i} is the length of the i-th metatile and s_{i} is the number of special tiles it contains. In order that T (n, k) meets the condition to be a Riordan array, we require at least one i with l_{i} = s_{i} = 1 (so that A_{0,0} ≠ 0 in Theorem 31) and s_{i} cannot exceed 1. Let T̄(n, k) be the (n, k)-th entry in the row-reversed triangle (reversing entries in each row up to and including the main diagonal). Replacing T (a, b) by T̄(a, a − b) in (15) and then replacing n − k by k leaves

T̄(n, k) = δ_{n,0}δ_{k,0} + ∑_{i} T̄(n − l_{i}, k − (l_{i} − s_{i})).  (16)

The reversed triangle is a Riordan array if and only if there is an i such that l_{i} = 1 and s_{i} = 0 (i.e., there is a metatile of length 1 that lacks special tiles) and if l_{i} − s_{i} is 0 or 1 for all i (since l_{i} − s_{i} cannot exceed 1 by Theorem 31 and cannot be negative as discussed in Remark 32).

Example 34. When tiling an n-board with half-squares (i.e., \frac{1}{2} × 1 tiles always placed with the shorter sides horizontal) and (\frac{1}{2}, \frac{1}{2})-fences, all metatiles contain not more than 2 halfsquares [8]. If the fence is regarded as the special tile, the associated triangle (\underline{A123521}) is a row-reversed Riordan array since two half-squares make a metatile of length 1 and since, for this type of tiling, l_{i} − s_{i} equates to the total length of the half-squares in the i-th metatile, l_{i} −s_{i} is either 0 or 1. The triangle is in fact the row-reversed (1/(1−x^{2}), x/(1−x)^{2}) Riordan array [10].

Theorem 35. Suppose a triangle is constructed by letting the (n, k)-th entry be the number of n-tile tilings of boards that use k special tiles. The triangle is a Riordan array if and only if the special tiles are metatiles consisting of just one tile and there is no metatile that contains more than one special tile. The triangle is a row-reversed Riordan array if and only if there is a metatile consisting of a single tile which is not a special tile and no metatile contains more than one non-special tile.

Proof. If T (n, k) is the (n, k)-th entry, then conditioning on the final metatile gives

T (n, k) = δ_{n,0}δ_{k,0} + ∑_{i} T (n − p_{i}, k − s_{i}),  (17)

where p_{i} is the number of tiles contained in the i-th metatile and s_{i} is the number of special tiles it contains. For the triangle to be a Riordan array, we require at least one i with p_{i} = s_{i} = 1 (which means the special tiles are themselves metatiles) and s_{i} cannot exceed 1 (which means no metatile can contain more than one special tile). Let T̄(n, k) be the (n, k)-th entry in the row-reversed triangle. Then

T̄(n, k) = δ_{n,0}δ_{k,0} + ∑_{i} T̄(n − p_{i}, k − (p_{i} − s_{i})).  (18)

The reversed triangle is a Riordan array if and only if there is an i such that p_{i} = 1 and s_{i} = 0 (i.e., there is a metatile composed of a single non-special tile) and if p_{i} − s_{i} is 1 or 0 for all i (for reasons given in the proof of Theorem 33).

In some instances, every other row of a tiling triangle or its row-reversed version are Riordan arrays [11]. Analogous theorems can be applied to test for this.

Remark 36. If a tiling triangle or its row-reversed version is a (p, q) Riordan array, then determining the functions p and q is straightforward. If it turns out that the tiling triangle is a Riordan array (row-reversed Riordan array) then p is the generating function for tilings with no (with only) special tiles. To find q(x), each term T (n − a, k − b) (or T̄(n − a, k − b)) in the recursion relation is replaced by x^{a}pq^{k−b} [11]. As b is either 0 or 1, dividing by pq^{k−1} gives an equation which is linear in q.

We end by giving a corollary of Theorem 35 applied to the n-tile tiling family of triangles.

Corollary 37. The ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m} triangles for m > 2 are not row-reversed Riordan arrays.

Proof. When m > 2 there is at least one metatile containing 2 squares (namely, the filled fence F S^{m−1}).

9 Discussion

Further generalizations of the tiling triangles presented here are possible if one tiles with squares and combs (which are generalizations of fences that can have more than two subtiles [1, 2]). This will be the subject of a future article.

Just as tiling an n-board with (\frac{1}{2}, g)-fences turned out to be a natural way to envisage permutations of {1, 2, …, n} [7], we have shown here that a natural representation of the subsets of {1, 2, …, n} where no two elements differ by m is the tilings of an (n + m)-board using squares and (1, m − 1)-fences. This representation can be extended to the case where there are multiple disallowed differences of the subset elements by tiling with squares and combs, but we will address this elsewhere.

We have given conditions for a tiling triangle or its row-reversed version to be a Riordan array. An open question is whether it is possible to find a tiling interpretation of an arbitrary (possibly row-reversed) Riordan array. We have been unable to do so for the first family of triangles we considered here for m > 2.

Sprugnoli derived an expression for the generating function giving sums of antidiagonals in a Riordan array [19, p. 270]. Lemma 38 gives the analogous generating function for a row-reversed Riordan array. This result, which is also the generating function for the sum of elements along a particular ray of elements in the original (unreversed) Riordan array, can be generalized to deal with sums over other rays. We will present this in another paper.

10 Appendix: Generating functions for row-reversed Riordan arrays and the sums of their antidiagonals

Lemma 38. The sum of the n-th antidiagonal of a row-reversed (p, q) Riordan array (counting the (0, 0)-th element as the zeroth antidiagonal) can be obtained from the generating function p(x^{2})/(1 − q(x^{2})/x).

Proof. The k-th term in the sum of the n-th antidiagonal of the row-reversed (p, q) Riordan array is the (n − k, k)-th entry in that array. Hence the required sum a_{n} is given by

a_{n} = ∑_{k=0}^{⌊n/2⌋}(p, q)_{n−k,n−2k} = ∑_{k=0}^{⌊n/2⌋}[x^{n−k}]pq^{n−2k} = [x^{n}]p ∑_{k=0}^{⌊n/2⌋} x^{k}q^{n−2k} = [x^{n}]pq^{n} ∑_{k=0}^{⌊n/2⌋}(\frac{x}{q^{2}} )^{k}

= [x^{n}]pq^{n} \frac{1 − (x/q^{2})^{⌊n/2⌋+1}}{1 − x/q^{2}} = [x^{n}]pq^{n} \frac{(x/q^{2})^{⌊n/2⌋} − q^{2}/x}{1 − q^{2}/x} = [x^{n}]pq^{n} \frac{(x/q^{2})^{⌊n/2⌋}}{1 − q^{2}/x} ,

where the final step of removing the q^{2}/x term from the numerator follows from the fact that q = q_{1}x + q_{2}x^{2} + ⋯ and so there can be no contribution from that term (when multiplied by pq^{n}) to the coefficient of x^{n} in the whole expression. Since ⌊n/2⌋ is n/2 ((n − 1)/2) when n is even (odd), on making the arguments of p and q explicit, we have

a_{n} = \begin{cases}[x^{n}]\frac{p(x)x^{n/2}}{1 − q^{2}(x)/x} = [x^{n/2}]\frac{p(x)}{1 − q^{2}(x)/x} = [x^{n}]\frac{p(x^{2})}{1 − q^{2}(x^{2})/x^{2}} , & if n even; \\ [x^{n}]\frac{p(x)q(x)x^{(n−1)/2}}{1 − q^{2}(x)/x} = [x^{(n+1)/2}]\frac{p(x)q(x)}{1 − q^{2}(x)/x} = [x^{n}]\frac{p(x^{2})q(x^{2})/x}{1 − q^{2}(x^{2})/x^{2}} , & if n odd. \end{cases}

We can now add the expressions after the coefficient operator for even and odd n (noticing that they are of opposite parity) to obtain

a_{n} = [x^{n}]\frac{p(x^{2})(1 + q(x^{2})/x)}{1 − q^{2}(x^{2})/x^{2}} = [x^{n}]\frac{p(x^{2})}{1 − q(x^{2})/x},

which gives us the generating function.

Lemma 39. The bivariate generating function for the row-reversed (p, q) Riordan array is p(xy)/(1 − q(xy)/y).

Proof. Let g(x, y) = p(xy)/(1 − q(xy)/y). Applying [x^{n}] to the expansion of g(x, y) gives

[x^{n}]g(x, y) = [x^{n}]p(xy) + [x^{n}]\frac{p(xy)q(xy)}{y} + ⋯ + [x^{n}]\frac{p(xy)q^{r}(xy)}{y^{r}} + ⋯

= y^{n}(p, q)_{n,0} + \frac{y^{n}}{y} (p, q)_{n,1} + ⋯ + \frac{y^{n}}{y^{r}} (p, q)_{n,r} + ⋯

by the definition of a (p, q) Riordan array. Then [x^{n}y^{k}]g(x, y) is (p, q)_{n,r} where n − r = k. Since (p, q)_{n,n−k} is the (n, k)-th entry in the row-reversed (p, q) Riordan array, g(x, y) is the bivariate generating function of the row-reversed array.

References

[1] M. A. Allen and K. Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, preprint, 2021. Available

    at https://arxiv.org/abs/2107.02589.

[2] M. A. Allen and K. Edwards, Identities involving the tribonacci numbers squared via tiling with combs, preprint, 2022. Available at https://arxiv.org/abs/2201.02285.

[3] P. Barry, Riordan Arrays: A Primer, Logic Press, Kilcock, 2016.

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

[5] I. Dababneh, M. Elmer, and R. McCulloch, A golden Penney game, J. Integer Sequences 24 (2021), Article 21.6.2.

[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] K. Edwards and M. A. Allen, New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile, J. Integer Sequences 24 (2021), Article 21.3.8.

[12] I. Kaplansky, Solution of the “problème des ménages”, Bull. Am. Math. Soc. 49 (1943), 784–785.

[13] J. Konvalina and Y.-H. Liu, Subsets without q-separation and binomial products of Fibonacci numbers, J. Combin. Theor. A 57 (1991), 306–310.

[14] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Can. J. Math. 49 (1997), 301–320.

[15] H. Prodinger, On the number of combinations without a fixed distance, J. Combin. Theor. A 35 (1983), 362–365.

[16] D. G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22 (1978), 301–310.

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

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

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

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

(Concerned with sequences \underline{A000045}, \underline{A000079}, \underline{A000217}, \underline{A001045}, \underline{A006324}, \underline{A006498}, \underline{A007318}, \underline{A011973}, \underline{A059259}, \underline{A077947}, \underline{A079962}, \underline{A115451}, \underline{A118923}, \underline{A123521}, \underline{A157897}, \underline{A335964}, \underline{A349839}, \underline{A349840}, \underline{A349841}, \underline{A349842}, \underline{A349843}, \underline{A350110}, \underline{A350111}, and \underline{A350112}.)

Received January 18 2022; revised versions received May 26 2022; June 21 2022. Published in Journal of Integer Sequences, July 29 2022.

Return to Journal of Integer Sequences home page.