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 |
Keywords:
combinatorial proof; combinatorial identity; \(n\)-tiling; Pascal-like triangle; Riordan array; Fibonacci polynomial; restricted combinationSoftware:
OEISOnline Encyclopedia of Integer Sequences:
Irregular triangle of numbers read by rows: {binomial(n-k, k), n >= 0, 0 <= k <= floor(n/2)}; or, triangle of coefficients of (one version of) Fibonacci polynomials.Triangle T(n,k) built by placing all ones on the left edge, [1,0,0,0] repeated on the right edge, and filling the body using the Pascal recurrence T(n,k) = T(n-1,k) + T(n-1,k-1).
Triangle T(n,k) built by placing all ones on the left edge, [1,0,0,0,0] repeated on the right edge, and filling the body using the Pascal recurrence T(n,k) = T(n-1,k) + T(n-1,k-1).
Triangle read by rows, T(n,k) = T(n-1,k) + T(n-1,k-1) - T(n-2,k-1) + T(n-3,k-1) + T(n-3,k-2) + T(n-3,k-3) - T(n-4,k-3) - T(n-4,k-4) + delta(n,0)*delta(k,0) - delta(n,1)*delta(k,1), T(n<k,k) = T(n,k<0) = 0.
Triangle read by rows: T(n,k) is the number of tilings of an (n+k)-board using k (1,3)-fences and n-k squares.
Triangle read by rows: T(n,k) is the number of tilings of an (n+k)-board using k (1,4)-fences and n-k squares.
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.