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\}$.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
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 http://math.mit.edu/~rstan/ec/ec1. 

