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$.

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$.

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 substitution rule.

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]$$

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$.

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$.