Count permutations. Hi I have a compinatorial exercise:
Let $s \in S_n$. Count the permutations such that
$$s(1)=1$$ and
$$|s(i+1)-s(i)|\leq 2 \,\, \mathrm{for} \, \, i\in\{1,2, \ldots , n-1 \}$$
Thank you!
 A: This is OEIS A038718 at the On-Line Encyclopedia of Integer Sequences. The entry gives the generating function 
$$g(x)=\frac{x^2-x+1}{x^4-x^3+x^2-2x+1}$$
and the recurrence $a(n) = a(n-1) + a(n-3) + 1$, where clearly we must have initial values $a(0)=0$ and $a(1)=a(2)=1$.
Added: I got this by calculating $a(1)$ through $a(6)$ by hand and then looking at OEIS. For completeness, here’s a brief justification for the recurrence. Start with any of the $a(n-1)$ permutations of $[n-1]$. Add $1$ to each element of the permutation, and prepend a $1$; the result is an acceptable permutation of $[n]$ beginning $12$, and every such permutation of $[n]$ is uniquely obtained in this way. Now take each of the $a(n-3)$ permutations of $[n-3]$, add $3$ to each entry, and prepend $132$; the result is an acceptable permutation of $[n]$ beginning $132$, and each such permutations is uniquely obtained in this way. The only remaining acceptable permutation of $[n]$ is the unique single-peaked permutation: $13542$ and $135642$ are typical examples for odd and even $n$ respectively.
From here we can easily get the generating function. I’ll write $a_n$ for $a(n)$. Assuming that $a_n=0$ for $n<0$, we have $a_n=a_{n-1}+a_{n-3}+1-[n=0]-[n=2]$ for all $n\ge 0$, where the last two terms are Iverson brackets. Multiply by $x^n$ and sum over $n\ge 0$:
$$\begin{align*}
g(x)&=\sum_{n\ge 0}a_nx^n\\
&=\sum_{n\ge 0}a_{n-1}x^n+\sum_{n\ge 0}a_{n-3}x^n+\sum_{n\ge 0}x^n-1-x^2\\
&=xg(x)+x^3g(x)+\frac1{1-x}-1-x^2\;,
\end{align*}$$
so
$$\begin{align*}g(x)&=\frac{1-(1-x)-x^2(1-x)}{(1-x)(1-x-x^3)}\\
&=\frac{x-x^2+x^3}{1-2x+x^2-x^3+x^4}\;.
\end{align*}$$
This is $x$ times the generating function given in the OEIS entry; that one is offset so that $a(0)=a(1)=1$, and in general its $a(n)$ is the number of acceptable permutations of $[n+1]$; my $a_n$ is the number of acceptable permutations of $[n]$. (I didn’t notice this until I actually worked out the generating function myself.)
