A decomposition of $w_0$ which is similar to the reduced decomposition

Question

Some basic definitions about reduced decomposition:

In the symmetric group $S_n$, let $s_i$ denote the adjacent transposition $(i,i+1),i\in \{1,2,\cdots,n-1\}.$ Since $S_n$ is generated by adjacent transpositions, any permutation $w\in S_n$ can be written as $w=s_{i_1}s_{i_2}\cdots s_{i_l}$ and an expression $w=s_{i_1}s_{i_2}\cdots s_{i_l}$ of minimal possible length $l$ is called a reduced decomposition, $l=\ell(w)$ is the length of $w$. In fact, $\ell(w)=\#\{(i,j):1\leq i<j\leq n\ \text{and}\ w(i)>w(j)\}$. So $w_0$, given by $w(i)=n+1-i$, is the longest element in $S_n$ whose length is $\frac{n(n-1)}{2}$.

For any $1\leq i<j\leq n$, let $t_{ij}$ be the transposition that interchanges $i$ and $j$. My question is how to find all the following decompositions: $$w_0=t_{i_1j_1}t_{i_2j_2}\cdots t_{i_mj_m}$$ such that $\ell(t_{i_1j_1}\cdots t_{i_kj_k})=k,\ k=1,2,\cdots,m$. Is there any method or function to characterize such decompositions?

Answer 1

Consider the (strong) Bruhat order on the symmetric group: This order is defined for $a,b \in \mathcal{S}_n$ as $a \leq b$ if $\ell(a) < \ell(b)$ and $at=b$ for a transposition $t$.

Therefore, your factorizations are exactly the maximal chains in this poset.

You find some further information about such maximal chains in A Weighted Enumeration of Maximal Chains in the Bruhat Order by John Stembridge. You indeed see the $\mathcal{S}_3$ example with 4 factorizations at the end of Section 1.