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](https://mathoverflow.net/questions/314489/how-many-maximal-length-bruhat-paths-from-u-to-w-can-there-be)), 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.



Number of paths in the Bruhat order in the symmetric group
$\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).


