Counting the number of injective and surjective functions from a set to itself I have a question about counting the number of injective (one-to-one) and surjective (onto) functions from $\{1,2,...,n\}$ to itself that satisfy $|f(i)-i| \leq 1, \forall i\in \{1,2,...,n\}$. I appreciate any help.
Thanks in advance and happy new year to you all 
 A: If $f$ is a function from a finite set to itself and it is surjective, then it is necessarily also injective.
If $f$ is a function from a finite set to itself and it is injective, then it is necessarily also surjective.
See Rigorous proof that surjectivity implies injectivity for finite sets
Both questions are then the same and we are asked to count the number of bijections from $\{1,2,\dots,n\}$ to itself.
Now... note that the only choice for $f(1)$ is $1$ or $2$.
In the case that $f(1)=2$, since $f$ must be a bijection, $f(2)\neq 2$.  This leaves $f(2)=1$ or $f(2)=3$.  Note, however, that if $f(2)=3$, then $f(n)=1$ for some $n\geq 3$ which is a contradiction since that would imply $|f(n)-n|=|1-n|\geq 2$.  Thus, if $f(1)=2$ then $f(2)=1$.
Continue via a recurrence relation using the previous observation.
Letting $a_n=$#of bijective functions from $\{1,2,\dots,n\}$ to itself, from the earlier observation we have the recurrence  $a_n=a_{n-1}+a_{n-2}$ with initial conditions $a_1=1$ and $a_2=2$.
You should then recognize this as being the fibonacci sequence and can find the closed form using traditional methods if you so choose.
