On a Two-Parameter Family of Generalizations of Pascal’s Triangle

Michael A. Allen Physics Department Faculty of Science Mahidol University Rama 6 Road Bangkok 10400 Thailand

                   maa5652@gmail.com

Abstract

We consider a two-parameter family of triangles whose (n, k)-th entry (counting the initial entry as the (0, 0)-th entry) is the number of tilings of N-boards (which are linear arrays of N unit square cells for any nonnegative integer N) with unit squares and (1, m − 1; t)-combs for some fixed m = 1, 2, … and t = 2, 3, … that use n tiles in total of which k are combs. A (1, m − 1; t)-comb is a tile composed of t unit square sub-tiles (referred to as teeth) placed so that each tooth is separated from the next by a gap of width m − 1. We show that the entries in the triangle are coefficients of the product of two consecutive generalized Fibonacci polynomials each raised to some nonnegative integer power. We also present a bijection between the tiling of an (n + (t − 1)m)-board with k (1, m − 1; t)-combs with the remaining cells filled with squares and the k-subsets of {1, …, n} such that no two elements of the subset differ by a multiple of m up to (t − 1)m. We can therefore give a combinatorial proof of how the number of such k-subsets is related to the coefficient of a polynomial. We also derive a recursion relation for the number of closed walks from a particular node on a class of directed pseudographs and apply it obtain an identity concerning the m = 2, t = 5 instance of the family of triangles. Further identities of the triangles are also established mostly via combinatorial proof.

1 Introduction

In a recent paper [?], that we will henceforth refer to as AE22, we considered two oneparameter families of generalizations of Pascal’s triangle. Regarding the triangles as lower triangular matrices, the members of both families have ones in the leftmost column and the repetition of 1 followed by m − 1 zeros along the leading diagonal, where m is a positive integer. In the case of the first family, the rest of the entries are obtained using Pascal’s recurrence, i.e., \binom{n}{k}_{m} = \binom{n−1}{k}_{m} + \binom{n−1}{k−1}_{m}, where \binom{n}{k}_{m} is the (n, k)-th entry (counting the first entry as being in row n = 0 and column k = 0) of the m-th triangle of the family. We showed that this is equivalent to the triangles being row-reversed (1/(1 − x^{m}), x/(1 − x)) Riordan arrays. 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 is the coefficient of x^{n} in the series expansion of p(x)(q(x))^{k} [?, ?]. The row-reversed version of a Riordan array has the entries up to and including the leading diagonal in each row placed in reverse order [?].

The main focus of AE22 was on a second family of triangles whose (n, k)-th entry (denoted by ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m}) is the number of ways to tile N-boards (which are linear arrays of N ≥ 0 unit square cells) using k (1, m − 1)-fences and n − k squares (and thus n tiles in total). A (1, m − 1)-fence is a tile composed to two unit-square sub-tiles separated by a gap of width m − 1 [?, ?]. The two families of triangles coincide for m = 1, 2 and the m = 1 case is Pascal’s triangle, i.e., \binom{n}{k}_{1} = ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{1} = \binom{n}{k} and \binom{n}{k}_{2} = ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{2} for all n and k. We showed that for j ≥ 0, k ≥ 0, m ≥ 1, and r = 0, …, m − 1, the entry ⟨ \begin{matrix}mj+r−k \\ k \end{matrix} ⟩_{m} is the coefficient of x^{k} in f_{j}^{m−r}(x)f_{j+1}^{r}(x), where in this instance the Fibonacci polynomial f_{n}(x) is defined by f_{n}(x) = f_{n−1}(x)+xf_{n−2}(x)+δ_{n,0}, f_{n<0}(x) = 0, where δ_{i,j} is 1 if i = j and zero otherwise. By first identifying a bijection between the tilings of an (n + m)-board with k (1, m − 1)-fences and n + m − 2k squares and the subsets of ℕ_{n} = {1, …, n} containing k elements none of which differ from another element in the subset by m, we showed that the number of such subsets, S^{(m)}(n, k) = ⟨ \begin{matrix}n+m−k \\ k \end{matrix} ⟩_{m}. We thus arrived at a combinatorial proof of the relation between S^{(m)}(n, k) and the coefficient of x^{k} in the product of nonnegative integer powers of two successive Fibonacci polynomials.

Here we generalize the second family of triangles by considering the analogous n-tile tilings of N-boards with (1, m−1; t)-combs and squares for positive integer m and t = 2, 3, . . .. A (w, g; t)-comb contains t sub-tiles of dimensions w ×1 (referred to as teeth) separated from one another by gaps of width g [?]. A (1, m − 1; 2)-comb is evidently a (1, m − 1)-fence and so the t = 2 instances of the triangles we introduce here coincide with the second family of triangles in AE22. Our choice of this particular way to generalize the second family stems from the result that the additional combinatorial interpretation of entries in the triangle as numbers of k-subsets of ℕ_{n} satisfying rules on disallowed differences also applies in case of the generalized triangles.

After introducing the two-parameter family of triangles (along with a less compact version of the triangles which is used in some proofs) in §2, we show how entries of the triangles are related to some generalized Fibonacci polynomials in §3. Then, in §4, we give a bijection between the tilings of an (n+(t−1)m)-board with k (1, m−1; t)-combs and n+(t−1)m−kt squares and the k-subsets of ℕ_{n} such that no two elements of the subset differ by any element of the set {m, 2m, …, (t − 1)m}. This enables us to relate the number of such subsets to coefficients of products of powers of two successive generalized Fibonacci polynomials. The remainder of the paper concerns finding identities satisfied by entries in the triangle. Most of the identities are obtained via the enumeration of metatiles with a certain length or number of tiles, which can be problematic if the metatiles contain an arbitrary number of tiles. A metatile is a gapless grouping of tiles that completely covers a whole number of cells and cannot be split into smaller metatiles. In most cases, there are infinitely many possible metatiles and there have been various approaches to the enumeration problem: obtaining the symbolic representation all the families of metatiles [?], obtaining a recursion relation for the number of metatiles of a certain length and thus expressing the number in terms of a known sequence [?], identifying a bijection between the metatiles and a set of objects whose number is known [?], and constructing a directed pseudograph (that we refer to as a digraph) to represent the placing of tiles [?]. We will use the first and last of these approaches and these are described further in §5. Recursion relations for numbers of tilings corresponding to a particular class of digraph are derived in the appendix and these are used to obtain identities for the m = 2, t = 5 triangle in §6 where further identities concerning the triangles are also derived, mostly via combinatorial proof.

2 The two-parameter family of triangles

For m = 1, 2, … and t = 2, 3, …, let ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m,t} denote the number of n-tile tilings of N-boards that use k (1, m − 1; t)-combs (and n − k squares). We choose that ⟨ \begin{matrix}0 \\ 0 \end{matrix} ⟩_{m,t} = 1 and that ⟨ \begin{matrix}n \\ k<0 \end{matrix} ⟩_{m,t} = ⟨ \begin{matrix}n \\ k>n \end{matrix} ⟩_{m,t} = 0. As a (1, 0; t)-comb is just a t-omino and the number of n-tile tilings using n t-ominoes and n − k squares is simply \binom{n}{k} for any t, we have ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{1,t≥2} = \binom{n}{k}, which is Pascal’s triangle (\underline{A007318}). The triangles corresponding to m = 2, 3, 4, 5 with t = 2 are \underline{A059259}, \underline{A350110}, \underline{A350111}, and \underline{A350112}, respectively [?]. We show examples of the starts of triangles for combs with at least 3 teeth in Figs. 1–4.

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

Identity 1. For m ≥ 1, t ≥ 2, and n ≥ k ≥ 0 we have

[\begin{matrix}n \\ k \end{matrix}]_{m,t} = ⟨\begin{matrix}n − (t − 1)k \\ k \end{matrix}⟩_{m,t} .

Proof. If a tiling contains n − (t − 1)k tiles of which k are (1, m − 1; t)-combs (and so n − kt are squares), the total length is n − kt + kt = n.

We will refer to the ray of entries given by ⟨ \begin{matrix}n−μk \\ k \end{matrix} ⟩_{m,t} for k = 0, …, ⌊n/(μ+1)⌋ as the n-th (1, μ)-antidiagonal. A (1, 1)-antidiagonal is therefore what is normally referred to simply as

n \ k  0  1  2  3  4  5  6  7  8  9 10 11 12 13
0  1
1  1  0
2  1  0  1
3  1  1  2  0
4  1  2  4  0  1
5  1  3  6  3  3  0
6  1  4  9  8  9  0  1
7  1  5 13 17 18  6  4  0
8  1  6 18 30 36 20 16  0  1
9  1  7 24 48 66 55 40 10  5  0
10  1  8 31 72 114 120 100 40 25  0  1
11  1  9 39 103 186 234 221 135 75 15  6  0
12  1 10 48 142 289 420 456 350 225 70 36  0  1
13  1 11 58 190 431 709 876 805 581 280 126 21  7  0

Figure 1: The start of a Pascal-like triangle (\underline{A354665} in the OEIS [?]) whose (n, k)-th entry, ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{2,3}, is the number of n-tile tilings using k (1, 1; 3)-combs (and n − k squares). Entries in bold font (and those in bold font in Figs. 2–4) are covered by identities in §6.

n \ k  0  1  2  3  4  5  6  7  8  9 10 11 12 13
0  1
1  1  0
2  1  0  1
3  1  0  2  0
4  1  1  4  0  1
5  1  2  6  0  3  0
6  1  3  9  4  9  0  1
7  1  4 12 10 18  0  4  0
8  1  5 16 21 36 10 16  0  1
9  1  6 21 36 60 30 40  0  5  0
10  1  7 27 57 100 81 100 20 25  0  1
11  1  8 34 84 158 168 200 70 75  0  6  0
12  1  9 42 118 243 322 400 231 225 35 36  0  1
13  1 10 51 160 361 560 736 560 525 140 126 0  7  0
Figure 2: The start of a Pascal-like triangle (\underline{A354666}) with entries ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{2,4}.

n \ k  0  1  2  3  4  5  6  7  8  9 10 11 12 13
0  1
1  1  0
2  1  0  1
3  1  0  2  0
4  1  0  4  0  1
5  1  1  6  0  3  0
6  1  2  9  0  9  0  1
7  1  3 12  5 18  0  4  0
8  1  4 16 12 36  0 16  0  1
9  1  5 20 25 60 15 40  0  5  0
10  1  6 25 42 100 42 100 0 25  0  1
11  1  7 31 66 150 112 200 35 75  0  6  0
12  1  8 38 96 225 224 400 112 225 0 36  0  1
13  1  9 46 134 325 424 700 364 525 70 126 0  7  0

Figure 3: The start of a Pascal-like triangle (\underline{A354667}) with entries ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{2,5}.

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  1
4  1  0  1  2  0
5  1  1  3  4  0  0
6  1  2  5  8  0  0  1
7  1  3  8 12  0  3  3  0
8  1  4 12 18  9 12  9  0  0
9  1  5 16 27 25 29 27  0  0  1
10  1  6 21 42 51 66 54  0  6  4  0
11  1  7 27 62 95 135 108 36 30 16  0  0
12  1  8 34 88 160 234 216 126 95 64  0  0  1
13  1  9 42 122 252 396 432 321 280 160 0 10  5  0

Figure 4: The start of a Pascal-like triangle (\underline{A354668}) with entries ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{3,3}. an antidiagonal. As a consequence of Identity 1, the (1, t − 1)-antidiagonals of the ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m,t} triangle are the rows of the [ \begin{matrix}n \\ k \end{matrix}]_{m,t} triangle. In the rest of the paper we therefore only give identities for the ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m,t} triangle as it is more ‘compact’ in the sense that its rows contain fewer trailing zeros. However, as in AE22, some of the identities are more straightforward to prove by considering the tiling of an n-board, in which case we need to consider [ \begin{matrix}n \\ k \end{matrix}]_{m,t}. The following bijection (which is established in the proof of Theorem 2.1 in [?]) will be used in such proofs.

Lemma 2. For t ≥ 2, 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; t)-combs and mj + r − kt squares and the tilings of an ordered m-tuple of r (j + 1)-boards followed by m − r j-boards using k t-ominoes and mj + r − kt squares.

3 Relation of the triangles to polynomials

For t ≥ 2 we define a (1, t)-bonacci polynomial as follows:

f_{n}^{(t)}(x) = f_{n−1}^{(t)}(x) + xf_{n−t}^{(t)}(x) + δ_{n,0}, f_{n<0}^{(t)}(x) = 0.  (1)

The (1, 2)-bonacci polynomials f_{n}^{(2)}(x) are the Fibonacci polynomials used in AE22. We refer to the sequence defined by

f_{n}^{(t)} = f_{n−1}^{(t)} + f_{n−t}^{(t)} + δ_{n,0}, f_{n<0}^{(t)} = 0,  (2)

for t ≥ 2 as the (1, t)-bonacci numbers. The t = 2, …, 8 cases are, respectively, the Fibonacci numbers (\underline{A000045}), the Narayana’s cows sequence (\underline{A000930}) and sequences \underline{A003269}, \underline{A003520}, \underline{A005708}, \underline{A005709}, and \underline{A005710} in the OEIS.

Lemma 3. The sum of the coefficients of f_{n}^{(t)}(x) is f_{n}^{(t)}(1) = f_{n}^{(t)}.

Proof. The sum of the coefficients of f_{n}^{(t)}(x) can be expressed as f_{n}^{(t)}(1). Putting x = 1 into (1) gives (2) with f_{n}^{(t)} replaced by f_{n}^{(t)}(1).

In the next lemma and theorem (which are generalizations of Lemma 13 and Theorem 14 in AE22) we employ the coefficient operator [x^{k}], which denotes the coefficient of x^{k} in the term it precedes.

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

Proof. This follows from Theorem 10 of AE22. The metatiles are the square and t-omino.

Theorem 5. For j ≥ 0, k ≥ 0, m ≥ 1, t ≥ 2, and r = 0, …, m − 1 we have

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

Proof. Identity 1 gives us ⟨ \begin{matrix}mj+r−(t−1)k \\ k \end{matrix} ⟩_{m,t} = [ \begin{matrix}mj+r \\ k \end{matrix}]_{m,t}. From Lemma 2, we have that [ \begin{matrix}mj+r \\ k \end{matrix}]_{m,t} equals the number of ways to tile an ordered m-tuple of r (j + 1)-boards followed by m − r j-boards using k t-ominoes (and mj + r − kt 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} b(t, j + 1, k_{i}))( ∏_{i=r+1}^{m} b(t, j, k_{i})),

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

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

= [x^{k}] ∑_{k_{1}≥0,k_{2}≥0,...,k_{m}≥0}(∏_{i=1}^{r} f(t, j + 1, k_{i}))( ∏_{i=r+1}^{m} f(t, 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(t, j + 1, k_{i}))(∏_{i=1}^{r} f(t, j, k_{i})).

The result then follows from Lemma 4.

The following identity gives the sums of the (1, t−1)-antidiagonals of the ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m,t} triangle. It is a generalization of Identity 15 in AE22. This, in turn, is a generalization of the wellknown result that the sum of the elements in the n-th antidiagonal of Pascal’s triangle is the Fibonacci number f_{n}^{(2)}, counting the initial 1 in the triangle as the zeroth antidiagonal.

Identity 6. For t ≥ 2, j ≥ 0, m ≥ 1, and r = 0, …, m − 1 we have

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

Proof. Summing (3) over all permitted k gives the sum of all coefficients of

F (x) = (f_{j}^{(t)}(x))^{m−r}(f_{j+1}^{(t)}(x))^{r},

which is F (1) and equals (f_{j}^{(t)})^{m−r}(f_{j+1}^{(t)})^{r} by Lemma 3.

4 Relation of the triangles to restricted combinations

We now look at S^{(m,t)}(n, k), the number of subsets of ℕ_{n} of size k such that the difference of any two elements of the subset does not equal any element in the set Q = {m, 2m, …, (t − 1)m}. For example, S^{(2,3)}(5, 0) = 1, S^{(2,3)}(5, 1) = 5, S^{(2,3)}(5, 2) = 6, and S^{(2,3)}(5, k > 2) = 0 since the possible subsets of ℕ_{5} such that no two elements in the subset differ by 2 or 4 are {}, {1}, {2}, {3}, {4}, {5}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {1, 4}, and {2, 5}. There is a formula for S^{(m,t)}(n, k) in terms of sums of products of binomial coefficients [?]. Here we will show that S^{(m,t)}(n, k) = ⟨ \begin{matrix}n+(t−1)(m−k) \\ k \end{matrix} ⟩_{m,t} and hence obtain an expression for the number of subsets in terms of coefficients of products of (1, t)-bonacci polynomials, which is a generalization of earlier results [?, ?]. We first establish the following bijection.

Lemma 7. For m, n ≥ 1, t ≥ 2, 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 an element from the set Q = {m, 2m, …, (t−1)m}, and the tilings of an (n+(t−1)m)-board with k (1, m−1; t)-combs and n + (t − 1)m − kt squares.

Proof. We label the cells of the (n + (t − 1)m)-board from 1 to n + (t − 1)m. If a k-subset contains element i then we place a comb so that its left tooth occupies cell i. Notice that if i = n then the rightmost tooth occupies the final cell on the board. After placing combs corresponding to each element of the subset, the rest of the board is filled with squares of which there must be n + (t − 1)m − kt. Conversely, the tiling of any (n + (t − 1)m)- board with k combs corresponds to a k-subset where no two elements differ by an element of Q since the remaining teeth of a comb whose leftmost tooth occupies cell i lie on cells i + m, i + 2m, …, i + (t − 1)m, which means none of these cells can be occupied by the leftmost tooth of another comb.

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

Proof. Lemma 7 gives us S^{(m,t)}(n, k) = [ \begin{matrix}n+(t−1)m \\ k \end{matrix}]_{m,t}. The result then follows from Identity 1.

Corollary 9. For m, n ≥ 1, t ≥ 2, the sum of the elements in the n-th (1, t−1)-antidiagonal of ⟨ \begin{matrix}n \\ k \end{matrix} ⟩_{m,t} is the number of subsets of ℕ_{n−(t−1)m} chosen so that no two elements of the subsets differ by any member of the set {m, …, (t − 1)m}.

Proof. The elements in the (1, t − 1)-antidiagonal are, for k ≥ 0,

⟨\begin{matrix}n − (t − 1)k \\ k \end{matrix}⟩_{m,t} = S^{(m,t)}(n − (t − 1)m, k)

by Corollary 8. Summing over all k then gives the result.

The next two corollaries follow from Theorem 5 and Identity 6, respectively.