How many $n$-permutations have no substrings of the type $(j,j+1)$?

Question

How many $n$-permutations have no substrings of the type $(j,j+1)$? $$1\leq j\leq n-1 \text{ and } n\geq 2$$

For example, let $n$ be 5:

[3 2 1 5 4] is one of the permutations we have to count.

[4 5 3 1 2] or [1 2 3 5 4] are permutations that we don't have to count.

---

I reckon this could be a PIE-solvable problem but I really can't figure how to work it out...

Answer 1

If we let $A_j$ be the set of n-permutations which do have the substring $(j,j+1)$ for $1\le j\le n-1$ and let $S$ be the set of all n-permutations,

$\displaystyle\lvert \overline{A}_1\cap\cdots\cap\overline{A}_{n-1}\rvert=\lvert S\rvert-\sum_{i}\lvert A_i\rvert+\sum_{i<j}\lvert A_i\cap A_j\rvert-\sum_{i<j<k}\lvert A_i\cap A_j\cap A_k\rvert+\cdots$

$\hspace{.3 in }\displaystyle=n!-\binom{n-1}{1}(n-1)!+\binom{n-1}{2}(n-2)!-\binom{n-1}{3}(n-3)!+\cdots+(-1)^{n-1}\binom{n-1}{n-1}1!$

$\hspace{.3 in }\displaystyle=(n-1)!\left[n-\frac{n-1}{1!}+\frac{n-2}{2!}-\frac{n-3}{3!}+\cdots+(-1)^{n-1}\frac{1}{(n-1)!}\right]=D_n+D_{n-1}$

Answer 2

For the record, a combinatorial approach is possible. Say that a permutation is good if it satisfies the condition in the question. Let $a_n$ be the number of such permutations of $[n]=\{1,\ldots,n\}$.

Each good permutation of $[n]$ can be extended to $n$ different good permutations of $[n+1]$: the $n+1$ can be inserted into the permutation at the beginning, or after any term except $n$. The only good permutations of $[n+1]$ that are not produced in this way are those that have substrings of the form $k,n+1,k+1$ for some $k\le n-1$. Removing the $n+1$ leaves a permutation of $[n]$ that is bad in exactly one place: it contains the substring $k,k+1$, but no other such pair. Removing $k+1$ from the permutation and replacing each $\ell\in\{k+2,\ldots,n\}$ by $\ell-1$ produces a good permutation of $[n-1]$. Conversely, one can start with a good permutation of $[n-1]$, replace any term $k$ by $k,k+1$, and then replace each $\ell\in\{k+1,\ldots,n-1\}$ by $\ell+1$ to get a permutation of $[n]$ that is bad in exactly one place. Thus,

$$a_{n+1}=na_n+(n-1)a_{n-1}\;,$$

and we clearly have the initial conditions $a_1=1=a_2$.

This suggests that we should look at the numbers $na_n$.

$$\begin{array}{rcc} n:&1&2&3&4&5\\ a_n:&1&1&3&11&53\\ na_n:&1&2&9&44&265 \end{array}$$

The numbers $na_n$ may not be immediately familiar, but it turns out that they are the derangement numbers $D_n$. This empirical observation is easily proved by induction using the recurrence

$$D_{n+1}=n(D_n+D_{n-1})\;.$$

Thus, $na_n=D_n$, and

$$a_n=\frac{D_n}n\;.$$

Any of the formulae for $D_n$ can now be substituted, e.g.,

$$a_n=(n-1)!\sum_{k=0}^n\frac{(-1)^k}{k!}=\frac1n\left\lfloor\frac{n!}e+\frac12\right\rfloor\;,$$

that last being computationally very handy.