Is there a formula that given a set $S$, and a list of rules on the precedence of the objects in the set, calculates the number of valid permutations?
For example, given the set $S = \{A, B, C, D, E, F\}$, and the following two precedence rules:
- $C$ before $D$
- $E$ before $ F$
Is it possible to calculate the total number of permutations that adhere to these rules?
If we did not have any rules, the total number of permutations would be the $6!$, which is $720$. However, now with these rules, the number of permutations that obey the aforementioned constraints are less than $720$ because, for example, the $A, B, D, C, E, F$ permutation is invalid as it violates the first rule.
Now there are 2 ways of arranging C and D in any sequence and that applies to E and F also.
so basically in every permutation, there will be either of the four sequences CD EF, DC EF, CD FE, DC EF. (there can be letters in between also)
since you need only only one of the sequence, you divide the total number by 4 and you get the answer.
answer: 720/4 = 180