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.


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.

  • 1
    $\begingroup$ 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 $\endgroup$
    – BookWick
    Mar 7 at 9:16
  • $\begingroup$ @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...". $\endgroup$ Mar 7 at 9:27
  • $\begingroup$ 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! $\endgroup$
    – BookWick
    Mar 7 at 10:29
  • 2
    $\begingroup$ You're fabulous! I figured out the mistake in OEIS formula. Thanks man, I really appreciate your time, efforts for dealing with a complete noob like me. Thanks! I really appreciate it! $\endgroup$
    – BookWick
    Mar 7 at 12:39
  • 2
    $\begingroup$ You have the option, BookWick, of "accepting" this answer by clicking in the check mark next to it. $\endgroup$ Mar 7 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.