How many permutations of $\{1, \ldots, n\}$ exist such that none of them contain $(i, i+1)$ (as a sequence) for $i \in {1,...,(n-1)}$?

How many permutations of $\{1, \ldots, n\}$ exist such that none of them contain $(i, i+1)$ (as a sequence of two consecutive entries) for $i \in \left\{1,...,(n-1)\right\}$?

First thing that comes to my mind is to find all that have $(i, i+1)$, then subtract that from all permutations. But then we can have $(i, i+1, i+2)$ which we subtracted twice, once in $(i, i+1)$ and once in $(i+1, i+2)$. And so on for $3$ and more. How do I calculate this?

Solution 1:

If we take such a permutation on $\{1,\ldots,n\}$ and delete $n$ we obtain either:

• a permutation of $\{1,\ldots,n-1\}$ without any $(i,i+1)$ subsequence, or

• a permutation of $\{1,\ldots,n-1\}$ with exactly one $(i,i+1)$ subsequence, which occurs when the original sequence had a $(i,n,i+1)$ subsequence.

  In this case, if we instead delete the $n$ and $i+1$ from this sequence and relabel elements $e \geq i+2$ with $e-1$, we obtain a a permutation of $\{1,\ldots,n-2\}$ without any $(i,i+1)$ subsequence. (Note that the element after $i+1$ in the sequence cannot be $i+2$, or the original sequence contained an $(i+1,i+2)$ subsequence.)

Conversely, we construct these in the following ways:

1. Given a permutation of $\{1,\ldots,n-1\}$ without any $(i,i+1)$ subsequence, we can insert $n$ except directly after $n-1$, giving $n$ possibilities.

2. Given a permutation of $\{1,\ldots,n-2\}$ without any $(i,i+1)$ subsequence, we choose an element $i$, increase the elements greater than $i$ by $1$, and insert $(n,i+1)$ after $i$; this gives $n-1$ possibilities.

Note that methods 1. and 2. above give distinct sequences.

Thus, the number $f(n)$ of such permutations satisfies the recurrence relation $$f(n)=nf(n-1)+(n-1)f(n-2)$$ and we observe $f(1)=1$ and $f(2)=1$.

This is Sloane's OEIS A000255, where many formulas are listed, and the sequence begins: $$ 1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, 190899411, 2467007773, \ldots $$

Solution 2:

Suppose there are $p_n$ permutations of the first $n$ integers without prohibited pairs

Then there are $(n-1)p_{n-1}$ permutations with exactly one prohibited pair as you have $n-1$ pairs of such integers and the rest of the permutation must not contain them

So when you get a new integer $n+1$ you can

• put it at the beginning of a permutation of the first $n$ integers without prohibited pairs: $p_n$ possibilities
• put it immediately after any of the integers other than $n$ in a permutation of the first $n$ integers without prohibited pairs: $(n-1)p_n$ possibilities
• put it in the middle of the prohibited pair of a permutation with exactly one prohibited pair: $(n-1)p_{n-1}$ possibilities

That gives you the recurrence

$$p_{n+1} = np_n+(n-1)p_{n-1}$$

and as Rebecca J. Stones says, this is OEIS A000255 offset

Solution 3:

Inclusion-exclusion immediately yields

$$\sum_{p=0}^{n-1} {n-1\choose p} (-1)^p (n-p)!$$

which gives the sequence

$$1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457,\ldots$$

The nodes of the poset here represent subsets $P$ of $[n-1]$ where an element $q\in P$ indicates that $[q,q+1]$ is present in the permutation. Hence $P$ corresponds to permutations where $[q,q+1]$ is present, with $q\in P$, plus possibly more adjacent pairs. Therefore only $P=\emptyset$ represents permutations with no consecutive adjacent elements. With the weight being $(-1)^{|P|}$ we get weight one for these. On the other hand a permutation with exactly $R\subseteq[n-1], R\ne\emptyset$ adjacent pairs is included in all nodes $P\subseteq R$, giving weight

$$\sum_{P\subseteq R} (-1)^{|P|} = \sum_{p=0}^{|R|} {|R|\choose p} (-1)^p = 0,$$

producing zero. It remains to compute the cardinality of the permutations represented by a node $P$ where $|P|=p.$ We list the pairs $[q,q+1]$ where $q\in P$ in order, fusing adjacent equal values (and removing the duplicate) to form blocks, say there are $m$ of them, with lengths $l_1, l_2, \ldots l_m.$ Here we observe that $1\le m\le p.$ We have by construction that

$$l_1-1+l_2-1+\cdots+l_m-1 = |P|=p.$$

The number of elements that we have removed from the $n$ available ones is

$$l_1+l_2+\cdots+l_m = p + m.$$ We put the $m$ blocks back in, getting

$$n-(p+m)+m = n - p$$

components that we may then permute, thus concluding PIE.

Remark. This problem appeared at the following MSE link.

Addendum. Note that the formula from PIE may be written as

$$n \sum_{p=0}^{n-1} {n-1\choose p} (-1)^p (n-p-1)! - \sum_{p=0}^{n-1} {n-1\choose p} (-1)^p p (n-p-1)!$$

or $$n (n-1)! \sum_{p=0}^{n-1} \frac{(-1)^p}{p!} - (n-1)! \sum_{p=1}^{n-1} \frac{(-1)^p}{(p-1)!}$$

or

$$- (-1)^{n} + n! \sum_{p=0}^{n} \frac{(-1)^p}{p!} + (n-1)! \sum_{p=1}^{n-1} \frac{(-1)^{p-1}}{(p-1)!}.$$

Introducing derangement numbers

$$D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$$

this becomes

$$- (-1)^n + D_n + (n-1)! \sum_{p=0}^{n-2} \frac{(-1)^{p}}{p!}$$ or $$ - (-1)^n + D_n - (-1)^{n-1} + (n-1)! \sum_{p=0}^{n-1} \frac{(-1)^{p}}{p!}.$$

or alternatively

$$\bbox[5px,border:2px solid #00A000]{ D_n + D_{n-1}.}$$