17
$\begingroup$

For $n\in \mathbb{N}$ let $S_n$ denote the set of permutations (bijections) $\pi: \{0,\ldots,n-1\}\to \{0,\ldots,n-1\}$. A transposition swaps exactly $2$ elements and is often denoted by $(i \; k)$ if $i\neq k\in\{0,\ldots,n-1\}$ are the elements being swapped.

For $n\in\mathbb{N}$ let $E_n$ be the number of elements of $S_n$ that can be obtained by a composition of all the transposition, such that every transposition is used exactly once.

What is the value of $\lim\sup\frac{E_n}{n!}$?

$\endgroup$
4
  • 3
    $\begingroup$ If I may decategorify, and so regard $E_n$ as a set rather than a number, then $E_2$ is obvious; have you computed $E_3$ and $E_4$, or other ‘small’ values? $\endgroup$
    – LSpice
    Feb 12 at 15:58
  • 4
    $\begingroup$ @LSpice Numbers to sets seems more in the direction of categorifying than decategorifying to me. $\endgroup$ Feb 12 at 16:22
  • 3
    $\begingroup$ Apparently, $E_n = |A_n|=n!/2$ for $n\geq 2$. $\endgroup$ Feb 12 at 17:34
  • 1
    $\begingroup$ @JeremyRickard, yes, you are right; I misspoke (miswrote?). $\endgroup$
    – LSpice
    Feb 12 at 17:49

1 Answer 1

25
$\begingroup$

The value is $1/2$.

The problem can be reformulated as follows: How to sort a non-sorted list $(a_1,...,a_n)$ that is a permutation of $\{1 .. .n\}$ with the parity the same as $n \choose 2$ by exactly one transposition between every pair of indices?

In this answer the phrase "unsorted element" means an element $a_p$ that is not equal to $p$.

This is solved by a recursive manner: Suppose $n\geq 4$ and $a_p\neq p$. Then there's a sequence of transpositions of $a_p$ with all the other elements such that $a_p=p$ after the transpositions and there exists an unsorted element in the list. Thus, we can proceed to the subproblem of finding such a sequence on the list with $a_p$ removed. This recursion stops at $n=3$, but by the parity assumption and the unsorted element assumption, there must be exactly two unsorted elements left, and it's easy to sort them by three transpositions.

Now we only need to prove the existence of such transpositions. We may assume that $a_1 \neq 1$, $a_n=1$ and we need to achieve $a_1=1$ after the transpositions.

Let $(1,2), (1,3), ..., (1,n)$ be the sequence of transpositions. Then $a_1$ will be equal to $1$ after applying the transpositions in order. If there are unsorted elements, we are done; otherwise the sequence $(1,2), (1,3), ..., (1,n-1), (1,n-2), (1,n)$ will give an unsorted element.

$\endgroup$
2

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.