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

There exist work on permutation with restricted positions (say, a permutation $\sigma$ satisfies $\sigma(i) = k$), and I am wondering if there exists a theory on permutation with restricted pairwise orderings, such as the number of permutations that satisfy a set of conditions $\{\sigma(i_m) < \sigma(j_m), m = 1, 2, ..., M\}$.

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

Define $i_m<j_m$ if one of the conditions is $\sigma(i_m)<\sigma(j_m)$. If the conditions are consistent, then this relation defines a partially ordered set $P$, and you are asking for the number of linear extensions of $P$. There is a huge literature on linear extensions, one reference being Chapter 3 of

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.