# the number of permutations with no successions

Could you help me to calculate the number of permutations $\pi\in S_n$ such that for all $1\leq i\leq n-1$ we have $\pi(i+1)\neq\pi(i)+1$, please?

-
Have you tried counting $n!$ minus the number of permutations such that there exists $i$ between $1$ and $n-1$ with $\pi(i+1) = \pi(i) + 1$? –  Patrick Da Silva Nov 12 '11 at 8:54
I've tried myself a little and this question doesn't seem trivial... +1! –  Patrick Da Silva Nov 12 '11 at 9:02

Consider the uniform distribution on $S_n$. For every $i$ in $\{1,2,\ldots,n-1\}$, let $A_i$ denote the event that $\pi(i+1)=\pi(i)+1$. Let $A$ denote the union of the events $A_i$. One asks for the cardinal of $S_n\setminus A$.

By the inclusion-exclusion principle, $$\mathrm P(A)=\sum\limits_I(-1)^{|I|+1}\mathrm P(A_I),$$ where the sum runs over every nonempty subset $I$ of $\{1,2,\ldots,n-1\}$ and $A_I$ denotes the intersection of the events $A_i$ for $i\in I$.

The set $A_I$ of permutations such that $\pi(i+1)=\pi(i)+1$ for every $i\in I$ is in bijection(1) with $S_{n-|I|}$ hence $P(A_I)=(n-|I|)!/n!$. There are ${n-1\choose k}$ subsets $I$ of $\{1,2,\ldots,n-1\}$ of size $k$ hence $$\mathrm P(A)=\sum\limits_{k=1}^{n-1}(-1)^{k+1}\frac{(n-k)!}{n!}{n-1\choose k}=\sum\limits_{k=1}^{n-1}(-1)^{k+1}\frac{n-k}{n}\frac1{k!}.$$ Finally, $$|S_n\setminus A|=n!\cdot \mathrm P(S_n\setminus A)=n!-(n-1)!\cdot\sum\limits_{k=1}^{n-1}(-1)^{k+1}\frac{n-k}{k!},$$ that is, $$|S_n\setminus A|=(n-1)!\cdot\sum\limits_{k=0}^{n-1}(-1)^{k}\frac{n-k}{k!}.$$ Note

(1) To see this, fix $I$ and consider a permutation $\pi'$ in $S_{n-|I|}$. Let $I'=\{i\in\{1,2,\ldots,n\}\mid i-1\notin I\}$. For every $i\in I'$, let $$\pi(i)=\pi'(i)+|\{j\leqslant i-1\mid j\in I\}|.$$ To complete the definition of $\pi$, use recursively the property $\pi(i+1)=\pi(i)+1$ for every $i\in I$. Then the function $\pi'\mapsto\pi$ is a bijection from $S_{n-|I|}$ to $A_I$.

-
I'm confused. The final sum you gave is the number of degragements of $[n]$. Clearly we can find derangements for which this condition doesn't hold, no? What's wrong here? –  Alex Youcis Nov 12 '11 at 9:07
@Alex Youcis, Thanks, see edit. –  Did Nov 12 '11 at 9:57

If, for some permutation $\pi$, $\pi(i+1) = \pi(i)+1$ for exactly $k$ values of $i$, then let's say that $\pi$ has $k$ successions. Let $S_{n,k}$ denote the number of permutations on $[n]$ with $k$ successions. The OP is asking for the value of $S_{n,0}$, which, for simplicity's sake, let's call $S_n$. Didier's answer gives an exact formula for $S_n$. Here is a nice recurrence that may be of interest.

$S_n = (n-1)S_{n-1} + (n-2) S_{n-2}, \text{ } n \geq 3.\tag{1}$

Proof: You can get this from Didier's formula, but let's do it combinatorially. Every permutation with no successions on $[n]$ can be formed either by (a) inserting $n$ into a permutation with no successions on $[n-1]$ anywhere other than after element $n-1$, or (b) inserting $n$ into a permutation with one succession on $[n-1]$ between the successive elements. Since the former can be done in $n-1$ ways and the latter in one way, this yields $S_n = (n-1)S_{n-1} + S_{n-1,1}$.

Now we need to prove that $S_{n,1} = (n-1)S_{n-1}$. Suppose we have a permutation $\pi$ with no successions on $[n-1]$. We can construct $n-1$ permutations with one succession on $[n]$ in the following manner: First, select one of the $n-1$ elements in $\pi$. Call this element $k$. Using one-line notation for $\pi$, for each $j \geq k$, let $j = j+1$. Then insert element $k$ before the new element $k+1$. This gives us the succession $(k,k+1)$. There are no successions $(j,j+1)$ for any $j > k$ or for any $j < k-2$ because the process above preserves (in the former case) or increases (in the latter case) the difference between two consecutive elements in a permutation that already had no successions. We also do not have the succession $(k-1,k)$. Either the element before $k$ in $\pi$ was larger than $k$, in which case it increased by one, or it was smaller than $k$, in which case it stayed the same (and so didn't produce a succession because $\pi$ has no successions).

For example, this process, applied to the permutation $15243$ (no successions) yields, by selecting 1, 2, 3, 4, and 5 in turn, the permutations $\color{red}{12}6354, 16\color{red}{23}54, 1625\color{red}{34}, 162\color{red}{45}3, 1\color{red}{56}243,$ each of which has exactly one succession.

Since the process is reversible, we have $S_{n,1} = (n-1)S_{n-1}$, and thus $S_n = (n-1)S_{n-1} + (n-2)S_{n-2}$.

The $S_{n,k}$ numbers are the subject of section 5.4 in Charalambides's Enumerative Combinatorics. He gives the formula in Didier's answer (via the same argument Didier uses), the one I prove above (by manipulating the formula in Didier's answer), and the following two as well:

$$nS_n = (n^2-1)S_{n-1} - (-1)^n, \text{ }n \geq 2,$$ $$S_n = D_n + D_{n-1}, \text{ }n \geq 1,$$ where $D_n$ is the number of derangements on $[n]$.

He also gives the following two expressions for $S_{n,k}$: $$S_{n,k} = \frac{(n-1)!}{k!} \sum_{j=0}^{n-k-1} (-1)^j \frac{n-k-j}{j!} = \binom{n-1}{k} S_{n-k},$$ the first of which is obtained via the inclusion-exclusion argument applied to $S_{n,k}$ rather than $S_n$.

-
I've added some more thoughts about this, including a combinatorial proof of $S_n = D_n + D_{n-1}$, on my blog. –  Mike Spivey Nov 14 '11 at 19:40