Number of permutations with constraints. Hi so i was trying to solve this problem:
Given N, M where N is the number of numbers and M is the number of orders.
An order consits of a pair x y which says in the permutation x should be before y.
After all M orders are taken you should try to figure out the number of permutations that satisfy all orders.
For example 
$N$=4 and $M$=2
First order :$2$ $1$
Second order: $4$ $3$
These permutations satisfy the constraints
$2, 1, 4, 3$
$2, 4, 1, 3$
$2, 4, 3, 1$
$4, 2, 1, 3$
$4, 2, 3, 1$
$4, 3, 2, 1$
The answer is 6.
So by trying out i understood that there is a bijection between the number of permutations where x is before y and y is before x. So there are $\binom{n}{2}$*$(n-2)!$ permutations that fulfill the first order. 
But trying to combine more orders is currently giving me a headache.I would appreciate any tip .
 A: If your orders are exhaustive and disjoint - every number is part of an order, and no number is in more than one order - the number of options is given by the multinomial coefficient 
$$\binom N{2,2,...,2} = \frac{N!}{2^{M}}$$
Note that in this case $M=N/2$
This also works if some $k$ numbers are not part of an order, they are freely ordered amongst the ordered items, giving the same formula, but in this case $N=2M+k$ - effectively the multinomial is 
$$\binom N{2,2,...,2,1,...,1}$$
If some numbers are part of more than one order, those orders would need to be resolved into larger groups, altering the multinomial. The outcome here depends on the nature of the interaction between orders.  For example two orders $[(a,b)$ and $(b,c)]$ give a strict order on $(a,b,c)$ but two orders $[(a,b)$ and $(c,b)]$ give two options $(a,c,b)$ and $(c,a,b)$ (amongst the rest of the set). However they would form a working order of three so might apeear in the multinomial as 
$$a_1\binom N{3,2,...,2} $$
where $a_1$ is the number of options within the composite ordering of three items.
