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
    Commented 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
    Commented Mar 20, 2019 at 18:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .