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

$\endgroup$
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))}$$

| cite | improve this answer | |
$\endgroup$
  • 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 Apr 27 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 Apr 27 at 18:29
  • $\begingroup$ I found it in a paper of Richard Stanley $\endgroup$ – Bipolar Minds Apr 27 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 Apr 30 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 Apr 30 at 14:44

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.