If a permutation $a_1,\ldots ,a_n$ of the set $\{1,2,\ldots ,n\}$ satisfies the condition $|{a_i}-{a_{i+1}}|\neq 1$ for all $i=1,2,\ldots ,n-1$, call it an $F_n$ type permutation. Let $f(n)$ is the total number of $F_n$ type permutations. Call a permutation $a_1,\ldots ,a_n$ of the set $\{1,2,\ldots ,n\}$ an $H_n$ type permutation, if it is an $F_n$ type permutation and there is at least one number between $1$ and $n$. Let $h(n)$ is the total number of $H_n$ type permutations. Call a permutation $a_1,\ldots ,a_n$ of the set $\{1,2,\ldots ,n\}$ a $G_n$ type permutation, if there is one and only one $i$,$1\leq i\leq {n-1}$, such that $|{a_i}-{a_{i+1}}|=1$. Let $g_{i,{i+1}}(n)$ is the total number of $G_n$ type permutations which there is no number between $i$ and $i+1$ in each of them. Let $f_i(n)$ is the total number of $F_n$ type permutations which each of them satisfies $a_1=i$. Let $h_i(n)$ is the total number of $H_n$ type permutations which each of them satisfies $a_1=i$. Let $f_{(x,y)}(n)$ is the total number of $F_n$ type permutations which there is no number between $x$ and $y$ in each of them. By symmetry, $h_1(n)=h_2(n)=h_3(n)=\ldots =h_n(n)=\frac {h(n)}{n}$ $(1. equation)$ $h(n)+f_{(n,1)}(n)=f(n)(2. equation)$ $h_1(n)=f(n-1)-f_1(n-1)-f_{n-1}(n-1)=f(n-1)-2f_1(n-1)(3. equation)$ (Because, if we remove the first element $a_1=1$ from each $H_n$ type permutations which each of them satisfies $a_1=1$, and decrease each remaining $a_i$ of each modified permutation by $1$, then we will get the set of $F_{n-1}$ type permutations which each of them satisfies $a_1\neq 1$ and $a_1\neq n-1$. And $f_1(n-1)=f_{n-1}(n-1)$ by symmetry) By the equations $(1)$ and $(3)$, $h(n)=n(f(n-1)-2f_1(n-1))(4. equation)$. By $(2)$ and $(4)$, $f(n)=n(f(n-1)-2f_1(n-1))+f_{(n,1)}(n) (5. equation)$. $f_1(n-1)=f(n-2)-f_1(n-2)=f(n-2)-(f(n-3)-f_1(n-3))=f(n-2)-(f(n-3)-(f(n-4)-f_1(n-4)))={(-1)^2}f(n-2)+{(-1)^3}f(n-3)+\ldots +{(-1)^{n-2}}f(n-(n-2))+{(-1)^{n-1}}f_1(n-(n-2)).$ So, $f_1(n-1)=\sum_{i=2}^{n-2}{(-1)^i}f(n-i) (6. equation) (note that f_1(2)=0)$. By $(5)$ and $(6)$, $f(n)=n(f(n-1)-2\sum_{i=2}^{n-2}{(-1)^i}f(n-i))+f_{(n,1)}(n)=f(n) (7. equation)$. $f_{(n,1)}(n)=g_{1,2}(n-1)+f_{(n-1,1)}(n-1)+2(f(n-1)-f_{(n-1,1)}(n-1))=g_{1,2}(n-1)+2f(n-1)-f_{(n-1,1)}(n-1)=(g_{1,2}(n-1)-g_{1,2}(n-2))+(2f(n-1)-2f(n-2))+f_{(n-2,1)}(n-2)= (g_{1,2}(n-1)-g_{1,2}(n-2)+\ldots +{(-1)^{(n-3)+1}}g_{1,2}(n-(n-3)))+2(f(n-1)-f(n-2)+\ldots +{(-1)^{(n-3)+1}}f(n-(n-3)))+{(-1)^{(n-3)}}f_{(n-(n-3),1)}(n-(n-3))=(\sum_{i=1}^{n-3}{(-1)^{i+1}}g_{1,2}(n-i))+(2\sum_{i=1}^{n-3}{(-1)^{i+1}}f(n-i))+{(-1)^{n-3}}f_{(3,1)}(3)=f_{(n,1)}(n) (8. equation)$. (Note that $f_{(3,1)}(3)=0$) $g_{1,2}(n-i)=2f(n-i-1)+g_{1,2}(n-i-1)=2f(n-i-1)+2f(n-i-2)+g_{1,2}(n-i-2)=2f(n-i-1)+2f(n-i-2)+\ldots +2f(3)+g_{1,2}(3)$ (note that $g_{1,2}(3)=2$). So $g_{1,2}(n-i)=2+2\sum_{j=3}^{n-i-1}f(j) (9. equation)$. By $(7),(8)$ and $(9)$, $f(n)=n(f(n-1)-2\sum_{i=2}^{n-2}{(-1)^i}f(n-i))+(\sum_{i=1}^{n-3}{(-1)^{i+1}}(2+2\sum_{j=3}^{n-i-1}f(j)))+(2\sum_{i=1}^{n-3}{(-1)^{i+1}}f(n-i))$ For $n=2$ and $n=3$ we can find manually $f(2)=f(3)=0$. for $n=4,5,6,$ by using $f(n)$, we will get $f(4)=2,f(5)=14,f(6)=90.$

The resulting sequence is A002464 in the OEIS; there's lots more information there. Here are some past places it's appeared on the forum: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=313852 http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=250073 http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=192170 http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=65890

.....By symmetry, $h_1(n)=h_2(n)=h_3(n)=\ldots =h_n(n)=\frac {h(n)}{n}$ $(1. equation)$ I don't think is symmetric because for $ 1,n $ we have that $ a_{i} $ can't have only one number and in general can't have two numbers like neighbors.