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 in Richard Stanley's Enumerative Combinatorics, Volume I.