2
$\begingroup$

Is there any recurrence relation known for the number of reduced words of the longest element in $S_n$ (not commutation classes)?

Edit: Sorry for unaccepting the answer, but I realized that I really would like to have a recurrence relation in $n$, so I would like to express the number of reduced words of the longest element in $S_n$ in terms of the numbers reduced words of the longest elements in $S_k$ for $k < n$.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

Let $(W,S)$ be a Coxeter system. Let $R(w)$ be the number of reduced words for an element, let $D(w)\subseteq S$ be the set of right descents of $w$. Then $$R(w)=\sum_{s\in D(w)}R(ws)$$ with $R(1)=1$.

This recurrence relation is not how you want to compute the number of reduced words for the longest element of $S_n$, though, because there is a closed formula for this, and using the recurrence relation would take forever.

If you want to build $R(w_0(n))$ from $R(w_0(n-1))$, note that the closed formula for these numbers comes from the hook length formula for standard tableaux on the shape $(n,n-1,\ldots,2,1)$. The product of the hook lengths of every box except for those in the first row is $$\frac{\binom{n}2!}{R(w_0(n-1))}$$ The remaining hook lengths are $2n-1$, $2n-3$, $\ldots$, $3$, $1$. So $$\frac{\binom{n+1}2!}{R(w_0(n))}=(2n-1)!!\frac{\binom n2 !}{R(w_0(n-1))}$$

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Thx! I actually forgot to write that I mean recurrence relation in $n$ but now that there is a closed formula, all the better $\endgroup$
    – Bipolar Minds
    Commented Apr 27, 2020 at 18:26
  • $\begingroup$ @BipolarMinds The formula is well known, for example it's in Combinatorics of Coxeter groups by Bjorner and Brenti, though I'm not sure of the original source. $\endgroup$
    – Matt Samuel
    Commented Apr 27, 2020 at 18:29
  • $\begingroup$ I found it in a paper of Richard Stanley $\endgroup$
    – Bipolar Minds
    Commented Apr 27, 2020 at 18:36
  • 1
    $\begingroup$ @BipolarMinds: it sounds like you might be interested in higher Bruhat orders in the sense of Manin--Schechtman/Ziegler (doi.org/10.1016/0040-9383(93)90019-R). In that paper Ziegler says that, beyond the case covered by Stanley's work, little is known in terms of enumeration. But of course that paper is 30 years old so perhaps more is known now. $\endgroup$
    – Sam Hopkins
    Commented Apr 30, 2020 at 14:39
  • 1
    $\begingroup$ @BipolarMinds Not sure if it will be useful, but I combinatorially described a recurrence for $\frac{\binom{n+1}2!}{|R(w_0(n))|}$. $\endgroup$
    – Matt Samuel
    Commented Apr 30, 2020 at 14:44

You must log in to answer this question.

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