IDENTITIES RELATING PERMANENTS OF SOME CLASSES OF (0,1) TOEPLITZ MATRICES TO GENERALIZED FIBONACCI NUMBERS

Abstract

We combinatorially prove identities relating the permanents of various classes of (0,1) Toeplitz matrices to some sequences generated from linear homogeneous finite order recursion relations with positive integer coefficients and integer-valued initial conditions. This is done using a previously obtained bijection between permanents of (0,1) Toeplitz matrices and the tilings of an n × 1 board with (Formula presented) -fences, where w is a nonnegative integer. (Formula presented) -fence is a tile composed of two (Formula presented) rectangular sub-tiles aligned horizontally and separated by a gap of width w.