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!}$?



Fraction of $S_n$ reachable by using every transposition once as $n\to\infty$?
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](https://en.wikipedia.org/wiki/Parity_of_a_permutation) 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.


