×

On two families of generalizations of Pascal’s triangle. (English) Zbl 1500.11017

Summary: 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) \times 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, \ldots, 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 \times 1)\)-boards to be a Riordan array.

MSC:

11B65 Binomial coefficients; factorials; \(q\)-identities
11B39 Fibonacci and Lucas numbers and polynomials and generalizations
05A19 Combinatorial identities, bijective combinatorics
05A15 Exact enumeration problems, generating functions

Software:

OEIS

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 athttps://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 athttps://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. · Zbl 1044.11001
[5] I. Dababneh, M. Elmer, and R. McCulloch, A golden Penney game,J. Integer Sequences 24(2021),Article 21.6.2. · Zbl 1466.91065
[6] K. Edwards, A Pascal-like triangle related to the tribonacci numbers,Fibonacci Quart. 46/47(2008/2009), 18-25. · Zbl 1190.11009
[7] K. Edwards and M. A. Allen, Strongly restricted permutations and tiling with fences, Discrete Appl. Math.187(2015), 82-90. · Zbl 1315.05020
[8] K. Edwards and M. A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared,Fibonacci Quart.57(5) (2019), 48-53. · Zbl 1437.05043
[9] K. Edwards and M. A. Allen, A new combinatorial interpretation of the Fibonacci numbers cubed,Fibonacci Quart.58(5) (2020), 128-134. · Zbl 1467.05030
[10] K. Edwards and M. A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared. Part II.,Fibonacci Quart.58(2020), 169-177. · Zbl 1467.05020
[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 Sequences24(2021),Article 21.3.8. · Zbl 1460.11022
[12] I. Kaplansky, Solution of the “probl‘eme des m´enages”,Bull. Am. Math. Soc.49(1943), 784-785. · Zbl 0060.02904
[13] J. Konvalina and Y.-H. Liu, Subsets withoutq-separation and binomial products of Fibonacci numbers,J. Combin. Theor. A57(1991), 306-310. · Zbl 0735.05007
[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. · Zbl 0886.05013
[15] H. Prodinger, On the number of combinations without a fixed distance,J. Combin. Theor. A35(1983), 362-365. · Zbl 0522.05006
[16] D. G. Rogers, Pascal triangles, Catalan numbers and renewal arrays,Discrete Math.22 (1978), 301-310. · Zbl 0398.05007
[17] L. W. Shapiro, S. Getu, W.-J. Woan, and L. C. Woodson, The Riordan group,Discrete Appl. Math.34(1991), 229-239. · Zbl 0754.05010
[18] N. J. A. Sloane,The On-Line Encyclopedia of Integer Sequences, published electronically, 2010. Available athttps://oeis.org. · Zbl 1044.11108
[19] R. Sprugnoli, Riordan arrays and combinatorial sums,Discrete Math.132(1994), 267- 290 · Zbl 0814.05003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.