On two families of generalizations of Pascal's triangle

Michael A. Allen*, Kenneth Edwards
open access article published in Journal of Integer Sequences 25(7), 22.7.1 (2022)

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.

Background
Pascal's triangle is familiar to most people; written as an infinite lower triangular matrix, we fill the leftmost vertical column and the leading diagonal with ones and then use `Pascal's recurrence' (an entry equals the sum of the entry above and the entry above and to the left) to fill in the rest. Pascal's triangle has many interesting properties and a myriad of applications in combinatorics.

What happens if we replace the leading diagonal by the periodic pattern of 1 followed by m−1 zeros for m=1,2,… while still using Pascal's recurrence to fill in the other entries? The paper shows that the family of triangles obtained are also a family of row-reversed Riordan arrays. A (p(x),q(x)) Riordan array is an infinite lower triangular matrix whose (n,k)-th entry (with row number n and column number k both starting at zero) is the coefficient of xⁿ in the series expansion of p(x)(q(x))^k. For example, Pascal's triangle is the (1/(1−x),x/(1−x)) Riordan array. Riordan arrays have numerous applications in combinatorics such as counting walks on lattices. Generating functions for various sums of entries in a Riordan array can be obtained quickly in terms of p and q.

The (n,k)-th entry of Pascal's triangle can be obtained in other ways: it is ⁿC_k, the number of ways of choosing k objects from n. It is also is the number of square-and-domino tilings of N-boards (which are linear arrays N unit square cells) that use n tiles in total of which k are (2×1) dominoes (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 dominoes.

What triangles do we get if we instead tile using squares and `split dominoes'? A split domino has its two halves separated by a gap of width m−1 and is known as a (1,m−1)-fence. It turns out that the family of triangles so generated have the same boundaries as the other family of triangles we consider and the other entries are identical in the m=1 and m=2 cases.

A question which we show can be answered in terms of tilings with squares and k (1,m−1)-fences 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 m. E.g., if m=3, the possible subsets of {1,2,3,4,5} are {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,5}, {2,3}, {2,4}, {3,4}, {3,5}, {4,5}, {1,2,3}, {2,3,4}, {3,4,5}, and {1,3,5}. The numbers of subsets are entries in the tiling-derived family of triangles we consider. E.g., the 8th antidiagonal of the m=3 triangle is 1,5,8,4 which are the numbers of subsets of {1,2,3,4,5} of sizes 0, 1, 2, and 3, respectively.

Key results
• Expression for (n,k)-th entry in the Riordan array triangles as a sum of binomial coefficients.
• Generating functions for subdiagonals, row sums, antidiagonal sums, and for the whole triangle in the case of the Riordan array triangles.
• Relation between tiling triangles and certain classes of polynomials.
• Expression for entry in the tiling triangles in terms of the coefficient of the products of powers of two consecutive Fibonacci polynomials.
• Expression for antidiagonal sums of the tiling triangles as products of powers of two consecutive Fibonacci numbers.
• Bijection between the k-subsets of {1,…,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. The number of such subsets is the (n+m−k,k)-th entry of the m-th tiling triangle.
• 7 identities and 1 conjecture concerning the tiling triangles in general.
• 3 additional identities concerning the m=3 tiling triangle.
• Conditions for a tiling-derived Pascal-like triangle or its row-reversed version to be a Riordan array.
• Generating functions for row-reversed Riordan arrays and the sums of their antidiagonals.

Related resources
[1] Sloane NJA (2022) The On-Line Encyclopedia of Integer Sequences, oeis.org.
[2] Sprugnoli R (1994) Riordan arrays and combinatorial sums. Discrete Math 132, 267–290.
[3] Allen MA (2019) Riordan Arrays seminar www.youtube.com/watch?v=qMhSxcwlHvM.
[4] Edwards K, Allen MA (2021) New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile. J Integer Sequences 24, 21.3.8.
[5] Allen MA (2022) On a two-parameter family of generalizations of Pascal's triangle. J Integer Sequences 25, 22.9.8.