# 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!

-
What have you tried? Can you do this for small values of $n$? – Qiaochu Yuan Aug 12 '12 at 18:25

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.)

-
Thank you, OEIS is far more powerful than I had thought! I see how to recurrence works, I am not really sure about the generating function though. – clark Aug 12 '12 at 18:33