Number of ways to arrange $n$ people in a line I came across this confusing question in Combinatorics.

Given $n \in \mathbb N$. We have $n$ people that are sitting in a row. We mark $a_n$ as the number of ways to rearrange them such that a person can stay in his seat or move one seat to the right or one seat to the left. Calculate $a_n$

This is one of the hardest combinatorics questions I have came across (I'm still mid-way through the course,) so if anyone can give me a direction I'll be grateful!

HINT: It’s a little more convenient to think of this in terms of permutations: $a_n$ is the number of permutations $p_1 p_2\dots p_n$ of $[n]=\{1,\dots,n\}$ such that $|p_k-k|\le 1$ for each $k\in[n]$. Call such permutations good.
Suppose that $p_1 p_2\dots p_n$ is such a permutation. Clearly one of $p_{n-1}$ and $p_n$ must be $n$. 


*

*If $p_n=n$, then $p_1 p_2\dots p_{n-1}$ is a good permutation of $[n-1]$. Moreover, any good permutation of $[n-1]$ can be extended to a good permutation of $[n]$ with $n$ at the end. Thus, there are $a_{n-1}$ good permutations of $[n]$ with $n$ as last element.

*If $p_{n-1}=n$, then $p_n$ must be $n-1$, so $p_1 p_2\dots p_{n-2}p_n$ is a good permutation of $[n-1]$ with $n-1$ as its last element. Conversely, if $q_1 q_2\dots q_{n-1}$ is a good permutation of $[n-1]$ with $q_{n-1}=n-1$, then $q_1 q_2\dots q_{n-2}nq_{n-1}$ is a good permutation of $[n]$ with $n$ as second-last element. How many good permutations of $[n-1]$ are there with $n-1$ as last element?

Alternatively, you could simply work out $a_k$ by hand for $k=0,\dots,4$, say, and see what turns up; you should recognize the numbers that you get.
