On a two-parameter family of generalizations of Pascal's triangle

Michael A. Allen*
open access article published in Journal of Integer Sequences 25(9), 22.9.8 (2022)

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.

Background
The (n,k)-th entry of Pascal's triangle is ⁿC_k, the number of ways of choosing k objects from n. It is also is the number of square-and-t-omino tilings of N-boards (which are linear arrays N unit square cells) that use n tiles in total of which k are t-ominoes (tiles with dimensions 1×t) and therefore n−k are unit squares. This is easily seen since there are ⁿC_k ways to choose which k of the n tiles are t-ominoes.

What triangles do we get if we instead tile using squares and `split t-ominoes'? A split t-omino is separated into t squares each separated from the next by a gap of width m−1 and is known as a (1,m−1;t)-comb. It is these triangles that we investigate in this work which follows on from [1] in which the second family of one-parameter generalizations of Pascal's triangle considered corresponds to tiling with squares and (1,m−1;2)-combs (also known as (1,m−1)-fences).

A question which we show can be answered in terms of tilings with squares and k (1,m−1;t)-combs is how many subsets with k elements can be chosen from the numbers 1,...,n such that no two elements in the subset differ by a multiple of m up to (t−1)m. E.g., if m=2 and t=5, so that no two elements in the subset differ by 2, 4, 6, or 8, then the possible subsets of {1,2,3,4,5} are {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,4}, {2,3}, {2,5}, {3,4}, and {4,5}. The numbers of subsets are entries in the tiling-derived family of triangles we consider. E.g., the 13th (1,4)-antidiagonal of the m=2, t=5 triangle is 1,5,6 which are the numbers of subsets of {1,2,3,4,5} obeying the given restrictions of sizes 0, 1, and 2, respectively.

To obtain results concerning the triangles we need to consider the metatiles involved in the tiling. A metatile is a grouping of tiles that exactly covers an integer number of cells with no gaps and cannot be split into smaller metatiles. Simple examples of metatiles are a single square (S), a comb (C) with all the gaps filled with squares (which we denote by CS^{(m−1)(t−1)} since m−1 squares fit in each of the t−1 gaps of the comb), and m interlocking combs (C^m). All tilings of N-boards are concatenations of one or more metatiles.

We need to find a recursion relation for the number of tilings of N-boards that contain n tiles of which k are combs. This is done with the help of a metatile-generating digraph. Each path beginning and ending on the 0 node without visiting it in between corresponds to a metatile. The 0 node represents the empty board or the completed metatile. Each of the other nodes gives the state of the yet-to-be-completed metatile with 0 (1) representing an empty (filled) cell. The arcs in the digraph correspond to the addition of a tile. The first step in deriving the recursion relation is to count the number of paths of length n that start and finish at the 0 node without visiting it in between; this is the number of metatiles containing n tiles.

Key results
• Expression for each entry in the triangles in terms of the coefficient of the products of powers of two consecutive generalized Fibonacci polynomials.
• Expression for sums of elements of the triangles along particular rays as products of powers of two consecutive generalized Fibonacci numbers.
• Bijection between the k-subsets of {1,…,n} such that all pairs of elements taken from a subset do not differ by a multiple of m up to (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. The number of such subsets is the (n+(t−1)(m−k),k)-th entry of the triangle.
• 9 identities and 1 theorem concerning the tiling triangles in general.
• 12 additional identities concerning particular instances of the triangles.
• Recursion relation for 3-inner cycle digraphs with a pseudo-common node (an example of which is shown in the figure).

Related resources
[1] Allen MA, Edwards K (2022) On a two-parameter family of generalizations of Pascal's triangle. J Integer Sequences 25, 22.7.1.
[2] Allen MA, Edwards K (2022) Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices. Linear Multilinear Algebra, https://doi.org/10.1080/03081087.2022.2107979, https://arxiv.org/abs/2107.02589.
[3] Edwards K, Allen MA (2015) Strongly restricted permutations and tiling with fences. Discrete Appl. Math. 187, 82–90.
[4] Sloane NJA (2022) The On-Line Encyclopedia of Integer Sequences, oeis.org.