2
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ Have you done any calculations for small values of $n$, to see whether any patterns show up? $\endgroup$ Apr 24, 2017 at 0:02
  • $\begingroup$ Yes, I did. And, the indication that the first inequality holds. $\endgroup$ Apr 24, 2017 at 0:17
  • 1
    $\begingroup$ 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\,\}$. $\endgroup$ Apr 24, 2017 at 0:22
  • $\begingroup$ @GerryMyerson: That's true and it seems equality occurs only when $n=2$, else $\vert A\vert>\vert B\vert$. $\endgroup$ Apr 24, 2017 at 1:15
  • 5
    $\begingroup$ 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. $\endgroup$ Apr 24, 2017 at 4:45

2 Answers 2

3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ This is cool. Of course, you may add $n>3$. Now, what's the proof for the nice claim? $\endgroup$ Apr 28, 2017 at 3:43
  • $\begingroup$ @T.Amdeberhan: What claim? I believe I proved all my claims. $\endgroup$ Apr 28, 2017 at 4:11
  • $\begingroup$ Yes, Max, $\vert A_n\vert=\vert B_n\vert+2n\vert B_{n-1}\vert$? $\endgroup$ Apr 28, 2017 at 5:20
  • $\begingroup$ @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. $\endgroup$ Apr 28, 2017 at 11:42
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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