# $n$-distant permutations more than not

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?

• 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
• 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
• 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

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).$$

Similarly,

$$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.