# Number of paths in the Bruhat order in the symmetric group

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.

• 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. Jul 31, 2020 at 11:24

$$\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).
• 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}$. Jul 31, 2020 at 14:52