Identities relating permanents of some classes of (0,1) Toeplitz matrices to generalized Fibonacci numbers

Michael A. Allen*, Kenneth Edwards
Article published in Fibonacci Quarterly 63(2), 163–177 (2025)

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 (½,w)-fences, where w is a nonnegative integer. A (½,w)-fence is a tile composed of two ½×1 rectangular sub-tiles aligned horizontally and separated by a gap of width w.

Background
The permanent of an n×n matrix M, whose (i,j)-th entry is denoted by M_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 M as detailing which permutations are allowed: if M_i,j=1, then i can get mapped to j (i.e., π(i)=j is allowed); otherwise, if M_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. M is then a Toeplitz matrix. This is a matrix with constant diagonals in the sense that M_i+1,j+1=M_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,w)-fences (denoted by F_w) for selected nonnegative integers w. The two sub-tiles of a fence are referred to as posts. As illustrated in the figure, an up fence has its left post in the left side of a cell on the board and corresponds to a positive π(i)−i; a down fence has its right post in the left side of a cell and corresponds to a negative π(i)−i. The π(i)=i case correponds to a fence with no gap (an F₀) aligned with a cell on the board. The combinatorial interpretation allows one to prove identities involving permanents using a combinatorial rather than algebraic approach by counting the number of possible tilings using the fences corresponding to the elements in D.

The Fibonacci numbers {f_n}_n≥0 are defined by f_n=f_n−1+f_n−2+δ_n,0, f_n<0=0, where δ_i,j is 1 if i=j and 0 otherwise. We refer to a sequence of numbers defined by an analogous recursion relation with arbitrarily many terms on the right-hand side but all with positive integer coefficients (the coefficients of the δ's can be integers of either sign; these define the boundary conditions) as generalized Fibonacci numbers.

Key results
• An expression relating permanents of odd dimension (0,1) Toeplitz matrices with D={−1,0,d₁,...,d_k} where the d_i are odd, positive, and distinct to permanents of even dimension Toeplitz matrices of the same type and generalized Fibonacci numbers.
• A theorem that can be used to generate identities relating permanents of (0,1) Toeplitz matrices to generalized Fibonacci numbers for 24 instances of D.
• 7 new identities relating permanents of n×n (0,1) Toeplitz matrices with a particular D to various types of generalized Fibonacci numbers.

Related resources
[1]  Allen MA (2024) Identities relating permanents of some classes of (0,1) Toeplitz matrices to generalized Fibonacci numbers talk www.youtube.com/watch?v=EAz28aafQJs.
[2]  Edwards K (2008/2009) A Pascal-like triangle related to the tribonacci numbers. Fibonacci Quart 46/47(1), 18–25.
[3]  Edwards K, Allen MA (2015) Strongly restricted permutations and tiling with fences. Discrete Appl Math 187, 82–90.
[4] Benjamin AT, Quinn JJ (2003) Proofs That Really Count: The Art of Combinatorial Proof, Mathematical Association of America.