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