3

How do you show that number of permutations of {1,2,3,,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.

\endgroup
4
  • 4
    \begingroup math.stackexchange.com/questions/1822068/… \endgroup
    – Alapan Das
    Commented Mar 7, 2021 at 7:51
  • 2
    \begingroup I think both the questions are bit different, Thanks \endgroup
    – BookWick
    Commented Mar 7, 2021 at 9:07
  • 1
    \begingroup Oh sorry, thank you. \endgroup
    – Alapan Das
    Commented Mar 7, 2021 at 10:07
  • 3
    \begingroup Please don't edit out your whole question. That's bad form. \endgroup Commented Mar 7, 2021 at 15:19

1 Answer 1

8
\begingroup

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.

\endgroup
9
  • 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
    Commented Mar 7, 2021 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 Commented Mar 7, 2021 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
    Commented Mar 7, 2021 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
    Commented Mar 7, 2021 at 12:39
  • 2
    \begingroup You have the option, BookWick, of "accepting" this answer by clicking in the check mark next to it. \endgroup Commented Mar 7, 2021 at 23:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .