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

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.

• math.stackexchange.com/questions/1822068/… Mar 7 at 7:51
• I think both the questions are bit different, Thanks Mar 7 at 9:07
• Oh sorry, thank you. Mar 7 at 10:07

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.
• Also what did you get $U_{n,k}$? I mean I know what it denotes but what did you get $U_{n,k}$ in terms of the sum? Also what should be the correct formula? Thanks Mar 7 at 9:16
• @BooleanCoder I clarified what the argument gives for $U_{n,k}$, and I will try to write the rest in more detail, though it would be good if you can ask a more specific question, not just "I don't get...". Mar 7 at 9:27
• In the OEIS formula it's $$\dbinom{n - k}{i}$$ However you are claiming that it should be $$\dbinom{n - k + 1}{i}$$ I don't get this part. Thanks! Mar 7 at 10:29