Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 < \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|improve this question

1 Answer 1

up vote 5 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 http://arxiv.org/pdf/1009.5740.pdf.

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