# Optimally reversing a list by swapping

Let $$\sigma_1, \sigma_2, \dots, \sigma_{n-1} \in S_n$$ be the "adjacent transpositions", so $$\sigma_i = (i, i+1)$$ is the permutation which swaps $$i$$ and $$i+1$$. Recall that an inversion in a permutation $$\pi$$ is a pair $$(i, j)$$ with $$i < j$$ and $$\pi(i) > \pi(j)$$. It isn't hard to show that the number $$I(\pi)$$ of inversions of $$\pi$$ is also the minimum length of a representation of $$\pi$$ as a product of adjacent transpositions, i.e. a representation of the form $$\pi = \sigma_{i_1} \sigma_{i_2} \cdots \sigma_{i_k}$$. Now let $$\tau$$ be the permutation which places the elements of $$\{1, \dots, n\}$$ in reverse order, and note this is the unique permutation with $$I(\tau) = \binom{n}{2}$$. My question is:

In how many distinct ways can we represent $$\tau$$ as a product of $$\binom{n}{2}$$ adjacent transpositions?

I am also interested in asymptotics if an exact answer seems out of reach.

• This paper by Stanley gives an exact answer in the first displayed equation: sciencedirect.com/science/article/pii/S0195669884800396 Commented Jun 22, 2020 at 21:25
• Thank you -- what a wonderful result! If you add your comment as an answer, I'll accept it. Commented Jun 22, 2020 at 21:40

Let $$w_0$$ denote the permutation with $$\binom{n}2$$ inversions. According to (1), available on Science Direct, the number of ways to write $$w_0$$ as a product of $$\binom{n}2$$ adjacent transpositions is $$r(w_0)=\frac{\binom{n}2!}{1^{n-1}3^{n-2}5^{n-3}\cdots (2n-3)^1}.$$