We will show that the amount of permutations of $\{1,2,\dots, n\}$ such that no two adjecent numbers exceed $n+1$ is $2^{\lfloor \frac{n}{2} \rfloor }$. We'll proceed by induction, where the base cases $n=1,2$ are trivial. Now, we will show $n\implies n+2$. Assume $n$ is true. For $n+2$ we must have $n+2$ next to $1$ on the leftmost or rightmost. Now take the $n$ other numbers and substract $1$ from each. They satisfy the condition for $n$. So the case $n+2$ is exactly the case $n$ but with an $(n+2)-1$ at its left, or $1-(n+2)$ at its right, which ends the problem.