The following question is inspired from a Putnam question:
For $n\in\Bbb{N}$, count the number of permutations $\pi\in S_n$ such that $|i-j|\leq 1$ implies that $|\pi(i)-\pi(j)|\leq 2$
The Putnam question asked to prove that $P_{n+5}-P_{n+4}-P_{n+3}+P_n$ is independent of $n$. Here $P_n$ is the number of such permutations. The solution for this problem does not construct $P_n$ explicitly, but uses recursive relations. I attempted to construct $P_n$ explicitly.
My solution
Consider the arrangement $1, 2, 3, \dots, n$. Let us define a pivot point in the following way: let $i$ be a pivot point. Then the numbers $\{1,2,\dots,i\}$ lie in reverse order in between the numbers $\{i+1,i+2,\dots,n\}$. For example, let $i=2$. Then $\{1,2\}$ has to lie between $\{3,4,\dots,n\}$. It can do this in two ways as per the condition given in the question:
$\{3,2,4,1,5,\dots\}$ or $\{3,4,2,5,1,6,7,\dots\}$.
We have to select two pivot points in $\{1,2,\dots,n\}$, say $i,j$, such that all numbers from in $\{1,2,\dots,i\}$ lie between $\{i+1,\dots,n\}$, and all numbers $\{j,\dots,n\}$ lie between $\{1,2,\dots,j-1\}$. For each pair $(i,j)$, there are $2$ possibilities for each of $i,j$, as given in the example above. Hence, for each $i,j$, we have $4$ possibilities based on how we choose to pivot.
For the remaining elements after this pivoting (we have to assume that a non-negative number of elements remains), we can have some transpositions. If there are $k$ elements remaining, then $a_1=0, a_2=1, a_3=2$, and $a_n=a_{n-3}+a_{n-1}$.
Hence, adding all these possibilities gives us $\sum a_{n-(2i+1)-(2j+1)}+a_{n-(2i+1)-(2j+2)}+a_{n-(2i+2)-(2j+1)}+a_{n-(2i+2)-(2j+2)}$ for all $i,j$ any or all of the indices are $\geq 1$.
Is this correct? If not, what is the correct expression for $P_n$?