Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 7 down vote accepted

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

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

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

Your Answer

 
discard

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.