Number of permutations with no succession The question is to calculate the number of permutations $\pi\in S_n$ such that $\pi(i+1)\neq\pi(i)+1$ for all $1\leq i\leq n-1$.
 A: 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$.
A: 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$.
