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

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 (Formula presented.) (where (Formula presented.), (Formula presented.), (Formula presented.), where (Formula presented.) and (Formula presented.) are positive integers and (Formula presented.)) each raised to an arbitrary non-negative integer power. A (Formula presented.) -comb is a tile composed of m rectangular sub-tiles of dimensions (Formula presented.) separated by gaps of width g. The interpretation is used to give combinatorial proof of new convolution-type identities relating (Formula presented.) for the cases q = 2, (Formula presented.), (Formula presented.), (Formula presented.) for M = 0, m to the permanent of a (0,1) Toeplitz matrix with 3 nonzero diagonals which are (Formula presented.), M−1, and m above the leading diagonal. When m = 1, these identities reduce to ones connecting the Padovan and Narayana's cows numbers.