Special permutations of $\{1,2,3,\ldots,n\}$

Question

How do you show that number of permutations of $\{1,2,3,\ldots,n\}$ such that image of no two consecutive numbers is consecutive is

$$n! + \sum_{k = 1}^{n}(-1)^k\sum_{i = 1}^{k}\dbinom{k - 1}{i - 1}\dbinom{n - k}{i}2^i(n - k)!$$

In short we need to find number of permutations of $\{1,2,3,\ldots,n\}$ such that none of the following occur: $12, 23, \ldots, (n-1)n \quad $ and $ \quad21, 32, \ldots, n(n-1)$ that is no adjacent numbers should be consecutive.

I tried proving the formula but didn't get any satisfactory result, It seems to be inclusion exclusion principle would work, but there are too many cases to count. I tried to find a recurrence relation, but couldn't do it either. Afterwards I tried to get a generating function for the same but didn't succeed. I don't see any other approach to get through this but I think the most useful tool would be PIE however I'm not finding a good way to use PIE since number of cases are too much. Any help or hint would be highly appreciated. Thanks!

Note that:

I have read almost all the references related to the problem from OEIS.

I have read the whole paper https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-38/issue-4/Permutations-without-Rising-or-Falling-omega-Sequences/10.1214/aoms/1177698793.full but in the paper there aren't any rigorous proofs and most of the proofs are just excluded simply by saying that 'use basic PIE to derive this'. I am looking for a more direct poof using enumerative combinatorics or generating functions.

I highly appreciate your time and efforts. Thanks.

Answer 1

The argument goes as follows. Let us consider the events $A_i=\{ i(i+1) \text{ occurs in a permutation} \}$ and $B_i=\{ (i+1)i \text{ occurs in a permutation} \}$. Some pairs of events like that cannot happen at the same time: $A_i$ is incompatible with both $B_i$ and $B_{i+1}$, and $B_i$ is incompatible with $A_{i+1}$. Note that if we choose specific $k$ compatible events among these, the number of permutations in which those events happen is equal to $(n-k)!$: you can collapse each $\{i,i+1\}$ onto $\{i\}$ without losing any information. For example, if you know that events $A_1$ and $B_3$ happened, that is if the permutation contains $12$ and $43$, then you can replace $12$ with $1$ and $43$ with $3$, obtaining a permutation of $1$, $3$, $4$, ...,$n$, and each permutation of these $n-2$ numbers can be reconstructed to a permutation where $A_1$ and $B_3$ happen.

According to inclusion-exclusion, the number of permutations where none of the events occur is thus equal to the sum $$ n!+\sum_{k=1}^n {(-1)^k}(n-k)! U_{n,k}, $$ where $U_{n,k}$ is the number of possible choices of $k$ compatible events.

Compatibility of events means that our $k$ chosen events are split into $i$ groups, where $1\le i\le k$, such that in each group the events are indexed by consecutive numbers and the same letter $A$ or $B$. This means that for a given $i$, the number of permutations is $2^i$ times the number of ways to choose $k$ elements of $n$ in such a way that there are exactly $i$ groups of consecutives in them (then the factor $2^i$ corresponds to the choice of $A$ or $B$ in each case). It remains to count the latter. That is done by the usual stars-and-bars counting. Namely, let us colour the chosen $k$ elements black and the ones not chosen white, so that the numbers $1$,...,$n$ have $r$ clusters of consecutive black numbers and the rest is white. To enumerate those, let us first put $n-k$ placeholders for white numbers. Those placeholders define $n-k+1$ gaps (the one before the first one, the one between the first two, etc.). Choosing $i$ out of those $n-k+1$ gives us the locations of the $i$ black clusters. Now we need to fill those $i$ clusters with $k$ placeholders for white numbers putting at least one placeholder in each. This is the usual stars-and-bars: we have $\binom{k-1}{i-1}$ ways to do it. Thus, we get the formula $$U_{n,k}=\sum_{i=1}^k 2^{i} \binom{k-1}{i-1}\binom{n-k+1}{i},$$ proving the requested result.