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

$\endgroup$
6
$\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.

$\endgroup$
  • $\begingroup$ This is a terrific answer, thanks so much! $\endgroup$ – Sam Hopkins Mar 13 '19 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 '19 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.