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\}$.
1 Answer
$\begingroup$
$\endgroup$
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.