1
$\begingroup$

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.

$\endgroup$
2

1 Answer 1

2
$\begingroup$

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

(1): Stanley, On the Number of Reduced Decompositions of Elements of Coxeter Groups, Europ. J. Combinatorics vol. 5 (1984) pp. 359-372

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .