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\}$. 



Permutation with restricted pairwise ordering
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>.


