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 $s_n$ (where $s_n={\sum }_{i=1}^q{v}_i{s}_{n-m_i}$, $s_0=1$, $s_{n<0}=0$, where $v_i$ and $m_i$ are positive integers and $m_1<\cdots <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\times 1$ separated by gaps of width $g$. The interpretation is used to give combinatorial proof of new convolution-type identities relating $s_n^2$ for the cases $q=2$, $v_i=1$, $m_1=M$, $m_2=m+1$ 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.

10 pages, 5 figures

References in corpus (1)

• New Combinatorial Interpretations of the Fibonacci Numbers Squared, Golden Rectangle Numbers, and Jacobsthal Numbers Using Two Types of Tile

Cited by in corpus (1)

• Jamming and metastability in one dimension: from the kinetically constrained Ising chain to the Riviera model