Almost sorted permutation Say that a permutation $y_1, \ldots, y_n$ of the integers $1, \ldots, n$ is almost sorted if, for $1 \le i \le n$, $|y_i − i| \le 1$. Let $a_n$ be the number of almost sorted permutations of $1, \ldots, n$. Find a recurrence for $a_n$.
Okay, so this is an exercise problem that the professor posted that I am at a lost to tackle. What is the significance of almost sorted permutations, and what is the approach that one takes to solve this? Thanks for the help--super appreciate it!
 A: It's not a concept of any particular significance. Most likely it's just something the author of the exercise came up with such that you could have something to practice coming up with recurrences for concrete situations on.
My suggestion for a plan of attack would be something like:


*

*Come up with a few short almost-sorted permutations (say for $n=5$ or thereabouts) for yourself, to get a feel for how they look like.

*Notice a connection between where an element goes and where it neighbors go.

*Does this help you find a simple way to generate all almost-sorted permutations of a given length (other than going through all permuations and checking one by one if they qualify)?

*You may have been presented with examples of, how to write recurrences for the number of ways to pave a path of a given width and length with flagstones of particular dimensions. A variation of this principle will apply here.

*The resulting recurrence is famous.
A: Here is a  slightly different approach to augment and  enrich the post
that was first to appear, which  is the definitive answer that we will
use as  well (upvoted).  Consider  the factorization of  an admissible
permutation into  disjoint cycles.   What sorts  of cycle  lengths may
appear?   Fixed points  are clearly  admissible  as are  loops on  two
elements which are consecutive. Can there be cycles of length at least
three? Suppose $a$ is mapped to $a+1.$ This means that $a$ is preceded
by  $a-1$ on  the cycle  and $a+1$  is followed  by $a+2$  because the
values are  unique. The  process continues  inductively. We  can never
close  this cycle  however because  the endpoints  differ by  at least
two. The same  for an element $a$  that is mapped to  $a-1.$ Now write
down the elements  of the permutation in sequence,  coloring the loops
on two consecutive  elements with a unique color and  the fixed points
with another. This is evidently a  path of length $n$ being covered by
a sequence of tiles covering either one or two slots.  Finally look at
the rightmost tile, which covers either one or two slots.  Remove that
tile to obtain  an admissible tiling of length $n-1$  or length $n-2$,
giving the recurrence
$$a_n = a_{n-1} + a_{n-2}.$$
