Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices

Michael A. Allen*, Kenneth Edwards
Article published in Linear and Multilinear Algebra 72(13), 2091–2103 (2024)

Abstract
By considering the tiling of an N-board (a linear array of N square cells of unit width) with new types of tile that we refer to as combs, we give a combinatorial interpretation of the product of two consecutive generalized Fibonacci numbers s(n) (where s(n)=∑_i=1^qv_is(n−m_i), s(0)=1, s(n<0)=0, where v_i and m_i are positive integers and m₁<…<m_q) each raised to an arbitrary non-negative integer power. A (w,g;m)-comb is a tile composed of m rectangular sub-tiles of dimensions w×1 separated by gaps of width g. The interpretation is used to give combinatorial proof of new convolution-type identities relating s²(n) for the cases q=2, v_i=1, m₁=M+1, m₂=m+2 for M=0,m to the permanent of a (0,1) Toeplitz matrix with 3 nonzero diagonals which are −2, M−1, and m above the leading diagonal. When m=1 these identities reduce to ones connecting the Padovan and Narayana's cows numbers.

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 F_n+1 where F_n=F_n−1+F_n−2+δ_n,1, F_n<1=0, and δ_i,j is 1 if i=j and 0 otherwise. Such combinatorial interpretations of integer sequences can be used to give quick intuitive proofs of identities rather than by using algebra.

A tiling which includes fractional length tiles and/or tiles with gaps, such as combs, can be reduced to a tiling using metatiles. A metatile is a grouping of tiles that exactly covers an integer number of cells and cannot be split into smaller metatiles. Evaluating the number of metatiles of a given length is the key to obtaining convolution-type identities via this class of combinatorial interpretation.

The permanent of an n×n matrix A, whose (i,j)-th entry is denoted by A_i,j, is the same as the determinant but with all plus signs. Permanents of (0,1) n×n matrices (i.e., n×n matrices whose elements are 0 or 1) give the number of permutations π(i) of i∈ℕ_n={1,2,…,n}. We can view the entries in A as detailing which permutations are allowed: if A_i,j=1, then i can get mapped to j (i.e., π(i)=j is allowed); otherwise, if A_i,j=0, then π(i) cannot equal j. Here we consider restricted permutations where the only allowed permutations are such that π(i)−i∈D, where D is a finite set. A is then a Toeplitz matrix. This is a matrix with constant diagonals in the sense that A_i+1,j+1=A_i,j for all allowed i and j. Permanents of such matrices also have a combinatorial interpretation in terms of a class of tilings of an n-board with (1/2,g;2)-combs for selected nonnegative integers g.

A metatile is said to be mixed if it contains more than one type of comb. The only metatiles which are not mixed are h², c², and C². We therefore just need to count the mixed metatiles. We show, using the combinatorial interpretation of permanents, that in two classes of cases, there is a simple expression for the number of mixed metatiles in terms of the permanent of a (0,1) Toeplitz matrix. To make this connection, we need to ignore the tiles that always occur at the beginning and/or the end of a mixed metatile and only consider the remaining tiles which we refer to as interior tiles.

Key results
• A new combinatorial interpretation of products of powers of consecutive generalized Fibonacci numbers.
• 6 new general identities relating some classes of generalized Fibonacci number squared to permanents of some class of (0,1) Toeplitz matrices. Particular instances of each of these identities give identities relating the Narayana's cows numbers (given by c_n=c_n−1+c_n−3+δ_n,0, c_n<0=0) to the Padovan numbers (given by p_n=p_n−2+p_n−3+δ_n,0, p_n<0=0). For example, we show for nonnegative integers n that c_n²=δ_n,0+c_n−1²+c_n−3²+2∑_l=3ⁿp_l−1c_n−l² and p_n²=δ_n,0+p_n−2²+p_n−3²+2∑_l=5ⁿc_l−5p_n−l².

Related resources
[1] Benjamin AT, Quinn JJ (2003) Proofs That Really Count: The Art of Combinatorial Proof, Mathematical Association of America.
[2]  Allen MA, Edwards K (2023) Identities involving the tribonacci numbers squared via tiling with combs. Fibonacci Quart 61, 21–27.
[3]  Edwards K, Allen MA (2015) Strongly restricted permutations and tiling with fences. Discrete Appl Math 187, 82–90.