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?

  • $\begingroup$ For $\mathcal{S}_3$ you get $(12)(23)(12) = (23)(13)(12) = (23)(12)(23) = (12)(13)(23)$. Is that correct? For $\mathcal{S}_4$ you get $168$. $\endgroup$ – Christian Stump Mar 17 '16 at 8:28
  • $\begingroup$ For $S_3$, yes, but I did not calculate the number of such decompositions for $S_4$. $\endgroup$ – user173856 Mar 17 '16 at 8:42

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.


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.