growth of the permanent of some band matrix

Question

Consider such special band matrix of dimension $n$. It is a $0-1$ matrix, and only the first few diagonals are nonzero. Specifically,

$$ H_{ij} = 1 $$

if and only if $|i-j| \leq 2$.

How does the permanent grow with $n$?

Answer 1

The permanent of this matrix is the number of perfect matchings of the graph $G_n$ that consists of vertices $\{(a,b):a\in\{ 1,...,n\},b\in\{0,1\}\}$ and the only edges are between $(i,0)$ and $(j,1)$ where $|i-j|\leq 2$.

Given a matching on the graph $G_n$, we define a sequence of graphs $G_{n-1},...,G_1$: $G_{k-1}$ is formed by removing from $G_k$ the vertex with the lexicographically smallest label and its neighbour in the matching.

The map from a matching to the sequence is injective, so the number of such sequences is the number of matchings in $G_n$.

If we start from $G_n$, then there are only five types of graphs in the sequence ${G_{n-1},...,G_1}$. They are shown in the figure as vertex sets (as all these graphs are induced subgraphs of $G_n$), above the long line. Call them $A_k$, $B_k$, $C_k$, $D_k$ and $E_k$, respectively, where the $k$s are the length of the lines above the patterns.

The graphs below the long line shows the possibilities of $G_{k-1}$ if $G_k$ is isomorphic to one of the graphs shown above.

Take the first column as an example. The graph above the long line is $A_k$, and the graphs below are $A_{n-1}$, $B_{k-2}$ and $C_{k-3}$. It means if $G_k$ is an $A_k$, then $G_{k-1}$ is an $A_{k-1}$, a $B_{k-2}$ or a $C_{k-3}$.

By doing substitutions, or in terms of the graph sequence, compressing consecutive $G_k$s into a single step, we obtain the following substitutions.

The equations are

$$A_k=A_{k-1}+B_{k-2}+B_{k-3}+A_{k-3}+A_{k-4}$$

$$B_k=A_k+B_{k-1}$$

or $$\left[\begin{matrix}A_k \\ A_{k-1} \\ B_{k-1} \\ A_{k-2} \\ B_{k-2} \\ A_{k-3}\end{matrix}\right]=\left[ \begin{matrix} 1 && 0 && 1 && 1 && 1 && 1 \\ 1 && 0 && 0 && 0 && 0 && 0 \\ 1 && 0 && 1 && 0 && 0 && 0 \\ 0 && 1 && 0 && 0 && 0 && 0 \\ 0 && 0 && 1 && 0 && 0 && 0 \\ 0 && 0 && 0 && 1 && 0 && 0 \end{matrix} \right] \left[\begin{matrix}A_{k-1} \\ A_{k-2} \\ B_{k-2} \\ A_{k-3} \\ B_{k-3} \\ A_{k-4}\end{matrix}\right]$$

where $A_k$ and $B_k$ both denote the graphs and the number of perfect matchings in them.

The characteristic polynomial of the matrix is $x^6 - 2x^5 - 2x^3 + x$, with largest root approximately $2.333554225170094$, so the permanent grows like $c*2.333554225170094^n$ for some constant $c$.

Answer 2

Another way of looking at this permanent is that it is the number of permutations $\pi$ of $\{1,2,\dots,n\}$ satisfying $|\pi(i)-i|\le 2$ for all $i$. The generating function for these permutations is $$\frac{1-x}{1-2x-2x^3+x^5},$$ which is consistent with LeechLattice's answer. The sequence of coefficients is A002524 in the OEIS.

A nice combinatorial derivation of this generating function can be found in Example 4.7.18 (pages 514–515) in Richard Stanley's Enumerative Combinatorics, Volume I, second edition. (It's Example 4.7.16, pages 252–253, in the first edition.)