Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 4 down vote accepted

This is OEIS A038718 at the On-Line Encyclopedia of Integer Sequences. The entry gives the generating function


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*}$$


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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.