# How many permutations $\pi$ of $\{1,2,…,n\}$ are there such that $|\pi (i) - i|\le 1$?

How many permutations $\pi$ of $\{1,2,...,n\}$ are there such that $|\pi (i) - i|\le 1$?

How would I go about solving this with a proof and teaching it to a non-math major student?

-
for a fixed $i$, or did you mean to sum over $i$ from 1 to $n$? – Sasha Feb 20 '13 at 22:21

Let $f(n)$ denote tha number of such permutations. Let $\pi$ be such a permutation. Either $\pi(n)=n$ and the restriction to $\{1,\ldots,n-1\}$ is one of $f(n-1)$ smaller permutations of this kind. Or $\pi(n)=n-1$, necessarily $\pi(n-1)=n$ and the restriction to $\{1,\ldots,n-2\}$ is one of $f(n-2)$ smaller such permutations. We obtain the recursion $$f(n) = f(n-1)+f(n-2).$$ We check $f(1)=1$, $f(2)=2$ and therefore conclude that $f(n)$ is the $n$th Fibonacci number.

-