Let $\mathfrak{S}_{2n}$ be the permutation group of the letters $[2n]=\{1,2,\dots,2n\}$. Call a permutation $\pi\in\mathfrak{S}_{2n}$ has an $n$-distant pair if there is some $j\in [2n-1]$ such that $\vert\pi_j-\pi_{j+1}\vert=n$.

Define $A=$ set of $\pi\in\mathfrak{S}_{2n}$ with exactly one $n$-distant pair and $B=$ set of permutations without $n$-distant pairs.

Question. Which inequality is true in general: $\vert A\vert>\vert B\vert$ or $\vert A\vert<\vert B\vert$? And your proof?

  • 1
    Have you done any calculations for small values of $n$, to see whether any patterns show up? – Gerry Myerson Apr 24 '17 at 0:02
  • Yes, I did. And, the indication that the first inequality holds. – T. Amdeberhan Apr 24 '17 at 0:17
  • 1
    I get $|A|=|B|=8$ for $n=2$. $B=\{\,1234,1432,2143,2341,3214,3412,4123,4321\,\}$, $A=\{\,1243,1423,2134,2314,3241,3421,4132,4312\,\}$. – Gerry Myerson Apr 24 '17 at 0:22
  • @GerryMyerson: That's true and it seems equality occurs only when $n=2$, else $\vert A\vert>\vert B\vert$. – T. Amdeberhan Apr 24 '17 at 1:15
  • 5
    Instead of dividing the elements of $\lbrace 1,\ldots,2n\rbrace$ into distant pairs, divide them into pairs as you like. It makes no difference. A restatement of the problem: "Let $t_j$ be the number of ways that $n$ couples can sit at a straight table such that exactly $j$ couples are sitting together. Compare $t_0$ and $t_1$." It must be in the literature somewhere. I can see an approach using switchings but it is too fiddly for the time I can spend on it. A circular table would be slightly easier as the straight table has end effects. – Brendan McKay Apr 24 '17 at 4:45
up vote 3 down vote accepted

There is an injective mapping from $B$ to $A$, which can be constructed as follows: for a permutation $\pi=(p_1,p_2,\dots,p_{2n})\in B$, find the element $p_k$ that pairs with $p_1$ (i.e., $|p_k-p_1|=n$); clearly we have $k>2$. Map $\pi$ to the permutation $\pi'=(p_2,\dots,p_{k-1},p_1,p_k,p_{k+1},\dots,p_{2n})$ (i.e., remove $p_1$ from $\pi$ and insert it right before $p_k$).

It can be easily seen that $\pi'\in A$, and $\pi'$ has only one pre-image in $B$. Hence, $|B|\leq |A|$.

Furthermore, for $n>2$, there exist permutations in $A$ that have no pre-images; namely, these are the permutations that start with an $n$-distant pair. It follows that $|B|<|A|$.

In fact, we can infer from the above argument that $|A_n| = |B_n| + 2n\cdot |B_{n-1}|$.

UPDATE. Inclusion-exclusion gives $$|B_n| = \sum_{j=0}^n (-1)^j \binom{n}{j} 2^j (2n-j)! ,$$ which matches sequence A007060 and can be further used to derive an explicit formula for $|A_n|$ (added as A285850).

  • This is cool. Of course, you may add $n>3$. Now, what's the proof for the nice claim? – T. Amdeberhan Apr 28 '17 at 3:43
  • @T.Amdeberhan: What claim? I believe I proved all my claims. – Max Alekseyev Apr 28 '17 at 4:11
  • Yes, Max, $\vert A_n\vert=\vert B_n\vert+2n\vert B_{n-1}\vert$? – T. Amdeberhan Apr 28 '17 at 5:20
  • @T.Amdeberhan: It follows from the given arguments. The first summand is the number of elements of $A_n$ that have prei-mages, while the second summand is the number of elements that don't. – Max Alekseyev Apr 28 '17 at 11:42

Let f(n), g(n) and h(n) be the number of permutations with zero, one or two occurrence of n-distant pair. The corresponding sets are denoted by F(n), G(n) and H(n).

Delete n and 2n from a permutation in F(n) leaves us a permutation in S_{n-1} with at most two n-distant pairs. Conversely, to construct a permutation in F(n), you may

1) insert n and 2n into some w in F(n-1) so that they are not adjacent, or

2) insert n and 2n into some w in G(n-1) so that one of these two number break up the existing n-distant pair, or

3) insert n and 2n into some w in H(n-1) to break up both existing n-distant pairs.

Therefore, one may derive that

$$f(n)=(2n-1)(2n-2)f(n-1) + 2(2n-2)g(n-1)+2 h(n-1).$$


$$g(n)=2n(2n-1)f(n-1)+2n g(n-1).$$

I checked these recurrences for n<=5 and they seem to be correct. It then follows that g(n)>f(n) for n sufficiently large.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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