# 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. – Nathan Reading Jul 31 '20 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}$. – Richard Stanley Jul 31 '20 at 14:52