Kenneth Edwards, Michael A. Allen*
open access article published in Journal of Integer Sequences 24(3), 21.3.8 (2021)
Abstract
We consider the tiling of an n-board (a board of size n×1) with squares of unit width and (1,1)-fence tiles. A (1,1)-fence tile is composed of two unit-width square sub-tiles separated by a gap of unit width. We show that the number of ways to tile an n-board using unit-width squares and (1,1)-fence tiles is equal to a Fibonacci number squared when n is even and a golden rectangle number (the product of two consecutive Fibonacci numbers) when n is odd. We also show that the number of tilings of boards using n such square and fence tiles is a Jacobsthal number. Using combinatorial techniques we prove new identities involving golden rectangle and Jacobsthal numbers. Two of the identities involve entries in two Pascal-like triangles. One is a known triangle (with alternating ones and zeros along one side) whose (n,k)th entry is the number of tilings using n tiles of which k are fence tiles. There is a simple relation between this triangle and the other which is the analogous triangle for tilings of an n-board. These triangles are related to Riordan arrays and we give a general procedure for finding which Riordan array(s) a triangle is related to. The resulting combinatorial interpretation of the Riordan arrays allows one to derive properties of them via combinatorial proof.
Background
Enumerating tilings of finite boards can give a physical picture of various integer sequences. For example, the number of ways to tile an n-board (a linear array of n square cells) with squares and dominoes is the Fibonacci number Fn+1, where Fn=Fn−1+Fn−2+δn,1, Fn<1=0; the number of ways to tile an n-board with squares of one colour and two different colours of domino is the Jacobsthal number Jn+1, where Jn=Jn−1+2Jn−2+δn,1, Jn<1=0. Combinatorial interpretations such as these can be used to give quick intuitive proofs of identities instead of using algebra.
A (p(x),q(x)) Riordan array, where p(x)=p0+p1x+p2x2+… and q(x)=q1x+q2x2+…, is an infinite lower triangular matrix whose (n,k)th entry is the coefficient of xn in the series for p(x){q(x)}k. E.g., Pascal's triangle is the (1/(1−x),x/(1−x)) Riordan array. Such arrays have many applications in combinatorics.
Key results
• A new combinatorial interpretation of Fnm−rFn+1r for r=0,…,m−1 and m=2,3,….
• A new combinatorial interpretation of the Jacobsthal numbers, Jn.
• 2 new identities concerning the golden rectangle numbers, FnFn+1.
• 4 new identities concerning Jn. E.g., Jn+1=⌈(n+1)/2⌉+∑j=1n−1jJn−j.
• A procedure for determining what type of Riordan array(s) a tiling-derived Pascal-like triangle corresponds to.
• Combinatorial proofs of properties of a known Pascal-like triangle which is also a row-reversed Riordan array. These include a proof of a conjecture about the array.
• Description and properties of a new Pascal-like triangle (A335964 in the OEIS).
Related resources
[1] Sloane NJA (2010) The Online Encyclopedia of Integer Sequences, oeis.org.
[2] Benjamin AT, Quinn JJ (2003) Proofs That Really Count: The Art of Combinatorial Proof, Mathematical Association of America.
[3] Sprugnoli R (1994) Riordan arrays and combinatorial sums. Discrete Math 132, 267–290.
[4] Allen MA (2019) Riordan Arrays seminar www.youtube.com/watch?v=qMhSxcwlHvM.
[5] Edwards K (2008/2009) A Pascal-like triangle related to the tribonacci numbers. Fibonacci Quart 46/47(1), 18–25.
[6] Edwards K, Allen MA (2020) A new combinatorial interpretation of the Fibonacci numbers squared. Part II. Fibonacci Quart 58(2), 169–177.
