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][1] in the OEIS.

A nice combinatorial derivation of this generating function can be found in Example 4.7.18 in Richard Stanley's *Enumerative Combinatorics, Volume I*.


  [1]: https://oeis.org/A002524