The Number of permutations of [n] such that $|\pi(i)-i|\leq 2$

Question

Let $a_n$ be a number of permutations of the set $[n]$ such that $$ |\pi(i)-i|\leq 2$$.

I can obtaine the GFs of these restriction permutations. It is equal

$$F(z)=\frac{1-z}{1-2z-3z^3+z^5}$$

I know That $a_n$ satisfies in the following recurrence relation

$$a_n=2a_{n-1}+3a_{n-3}-a_{n-5}$$

How can get this recurrence relation?

Is it combinatorial interpretation for it?

Is it close formula for positive integer $k$ such that
$$|\pi(i)-i|\leq k$$.

Answer 1

Here is a direct derivation of the recurrence.

Let $P_n$ be the set of $\pi:[n]\to[n]$ such that $|\pi(i)-i|\le 2$ for each $i\in[n]$, so that $a_n=|P_n|$.

Let $b_n$ be the number of injections $f:[n]\to[n-1]\cup\{n+1\}$ such that $|f(i)-i|\le 2$ for each $i\in[n]$, and let $c_n$ be the number of injections $f:[n]\to[n-2]\cup\{n,n+1\}$ such that $|f(i)-i|\le 2$ for each $i\in[n]$. If $\pi\in P_n$, then $\pi(n)$ is $n$, $n-1$, or $n-2$.

• If $\pi(n)=n$, then $\pi\upharpoonright[n-1]\in P_{n-1}$; there are $a_{n-1}$ such $\pi\in P_n$.
• If $\pi(n)=n-1$, then $\pi\upharpoonright[n-1]$ is an injection to $[n-2]\cup\{n\}$; there are $b_{n-1}$ such $\pi\in P_n$.
• If $\pi(n)=n-2$, then $\pi\upharpoonright[n-1]$ is an injection to $[n-3]\cup\{n-1,n\}$; there are $c_{n-1}$ of these.

Thus, $a_n=a_{n-1}+b_{n-1}+c_{n-1}$.

Next, suppose that $f:[n]\to[n-1]\cup\{n+1\}$ is an injection such that $|f(i)-i|\le 2$ for each $i\in[n]$; then $f(n)=n+1$, or $f(n-1)=n+1$.

• If $f(n)=n+1$, then $f\upharpoonright[n-1]\in P_{n-1}$; there are $a_{n-1}$ such $f$.
• If $f(n-1)=n+1$, then $f^{-1}\upharpoonright[n-1]$ is an injection to $[n-2]\cup\{n\}$; there are $b_{n-1}$ of these.

Thus, $b_n=a_{n-1}+b_{n-1}$.

Now suppose that $f:[n]\to[n-2]\cup\{n,n+1\}$ is an injection such that $|f(i)-i|\le 2$ for each $i\in[n]$; then $f(n)=n+1$, or $f(n-1)=n+1$.

• If $f(n)=n+1$, then $f\upharpoonright[n-1]$ is an injection to $[n-2]\cup\{n\}$; there are $b_{n-1}$ of these.
• If $f(n-1)=n+1$, then $f\upharpoonright[n-2]\cup\{n\}$ is a permutation of $[n-2]\cup\{n\}$. Either $f(n)=n$, or $f(n)=n-2$ and $f(n-2)=n$. In the first case $f\upharpoonright[n-2]\in P_{n-2}$, and in the second case $f\upharpoonright[n-3]$, so there are altogether $a_{n-2}+a_{n-3}$ of these.

Thus, $c_n=b_{n-1}+a_{n-2}+a_{n-3}$.

We can now reduce the system of recurrences to a single recurrence:

$$\begin{align*} a_n&=a_{n-1}+\color{red}{b_{n-1}}+\color{blue}{c_{n-1}}\\ &=a_{n-1}+\color{red}{a_{n-2}+b_{n-2}}+\color{blue}{b_{n-2}+a_{n-3}+a_{n-4}}\\ &=a_{n-1}+a_{n-2}+2b_{n-2}+a_{n-3}+a_{n-4}\\ &=a_{n-1}+\color{green}{(a_{n-2}+b_{n-2}+c_{n-2})}+b_{n-2}+a_{n-3}+a_{n-4}\color{brown}{-c_{n-2}}\\ &=a_{n-1}+\color{green}{a_{n-1}}+\color{purple}{b_{n-2}}+a_{n-3}+a_{n-4}\color{brown}{-b_{n-3}-a_{n-4}-a_{n-5}}\\ &=2a_{n-1}+\color{purple}{(a_{n-3}+b_{n-3})}+a_{n-3}-b_{n-3}-a_{n-5}\\ &=2a_{n-1}+2a_{n-3}-a_{n-5} \end{align*}$$