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

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.