Let $\mathbb{S}_m$ the symmetric group on $m$ letters. Let $v\in\mathbb{S}_m$, and consider paths in the Bruhat order like this: $1\lessdot v_1\lessdot\cdots\lessdot v$, where $\lessdot$ means the covering relation in the (strong) Bruhat order. Let $N_v$ be the number of such paths.

It is intuitively clear that $N_v\leq\ell(v)!$ (for a proof, I found just now the reference), and further that the difference $\ell(v)!-N_v$ is even. Can you prove the latter fact?

Remark. What I said should be true for every finite Coxeter group but I am mostly interested in the symmetric group for now.

  • 1
    $\begingroup$ For the benefit of people finding this question later: Depending on what definition you have seen of the Bruhat order, it might not be "intuitively clear that $N_v\le\ell(v)!$". But this becomes clear when you know the subword characterization of Bruhat order. See, for example, Björner and Brenti's book "Combinatorics of Coxeter Groups", Theorem 2.2.2. $\endgroup$ Jul 31, 2020 at 11:24

1 Answer 1


$\ell(v)!$ is of course even if $\ell(v)>1$, so the statement is really that $N_v$ is even for $\ell(v)>1$. We find a fixed-point free involution on the set of such Bruhat paths. Suppose that $v_2,v_3,\ldots$ are fixed. By the diamond property of Bruhat order there are exactly two possibilities for $v_1$. This gives the involution we want (in fact many of them).

  • 2
    $\begingroup$ In fact, this argument gives that for any Coxeter group (or even any Eulerian poset) $N_v$ is divisible by $2^{\lfloor \ell(v)/2\rfloor}$. $\endgroup$ Jul 31, 2020 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.