MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on permutations $S_n$, we say that $\sigma \leq \tau$ if $\mathrm{Inv}(\sigma)\subseteq \mathrm{Inv}(\tau)$. The length of a permutation $l(\sigma):= |\mathrm{Inv}(\sigma)|$ is the total number of inversions of $\sigma$.

Weak Bruhat Order on Permutations $S_4$

Is there a formula (closed or not) for the size of a principal order ideal (principal downset) in this poset?

Computing all elements in a given order ideal of this poset is easy enough for a fixed $\sigma\in S_n$ using the covering relations given by $\pi\in\{(1,2),(2,3),...,(n-1,n)\}$ and selecting permutations $\pi\sigma$ such that $l(\pi\sigma)<l(\sigma)$ (and repeating until reaching the minimal/identity permutation.)

I was just curious if the size of upper or lower intervals $[\sigma,id^c]$ or $[id,\sigma]$ was easy identifiable in terms of the set of inversions $\mathrm{Inv}(\sigma)$, the inversion table, the Rothe diagram, etc.

share|cite|improve this question
up vote 7 down vote accepted

In general, no "reasonable" formula is known. For separable permutations (or 3142 and 2413-avoiding permutations), see the paper of Fan Wei at

share|cite|improve this answer

Just posted on the arXiv a manuscript giving a polynomial-time algorithm for computing the size of principal order ideals in the weak Bruhat order:

More specifically, we show that the enumeration problem is fixed-parameter tractable in the "intrinsic width" of a a permutation (a generalization of longest decreasing subsequence). This implies a subexponential algorithm for all but an exponentially small fraction of permutations in general.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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