# Formula for number of permutations less than a given permutation in weak order

Let $$w\in S_n$$ be a permutation. Is there a reasonable "formula" for the number of elements of the initial interval $$[e,w]$$ of weak (Bruhat) order from the identity to $$w$$?

In terms of what such a "formula" might look like: if $$w$$ is a Grassmannian permutation of shape $$\lambda$$ then we have $$[e,w]\simeq[\varnothing,\lambda]$$, an initial interval of Young's lattice, and we can use the determinantal formula of MacMahon mentioned here: Formula for number of edges in Hasse diagram of Young's lattice interval. More generally, if $$w$$ is a fully commutative permutation (i.e., is 321-avoiding), then $$[e,w]\simeq [\mu,\lambda]$$ for some skew shape $$\lambda/\mu$$, and we can use the linked formula of Kreweras.

Of course what a formula could look like depends on how we encode $$w$$, but I would be happy with anything reasonable (e.g., Lehmer code, co-code, etc.).

By Dittmer and Pak - Counting linear extensions of restricted posets (Theorem 1.4), computing the size of $$[e,w]$$ is $$\#$$P-complete. Thus, a nice formula like the suggested $$n \times n$$ determinant filled with entries of easy-to-calculate permutation data would imply P$$=$$NP.
Though not a formula, Bj$$\ddot{\text{o}}$$rner and Wachs - Permutation statistics and linear extensions of posets (Section 6) provides a bijection between $$[e,w]$$ and linear extensions of a canonically determined two-dimensional poset.
• For anyone who sees this question later: it is worth contrasting the Dittmer-Pak paper with a paper of Cooper and Kirkpatrick (which extends the result of Wei mentioned by Richard Stanley above) which says that for "most" permutations $w$, the size of $[e,w]$ can be computed in sub-exponential time: arxiv.org/abs/1507.00388 – Sam Hopkins Mar 20 '19 at 18:42