8
$\begingroup$

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.).

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is a terrific answer, thanks so much! $\endgroup$
    – Sam Hopkins
    Mar 13, 2019 at 17:07
  • 1
    $\begingroup$ 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 $\endgroup$
    – Sam Hopkins
    Mar 20, 2019 at 18:42

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.