0

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.

Jessica Tiberio
  • 443
abelop
  • 1
  • In general rules can interact, causing this problem to be impossible without examining a particular set of rules. However it's easy to define a notion of "independence" of rules so that each rule cuts down the number of options by a certain factor. As long as your rules are independent you can analyze each rule individually. – Reinstate Monica May 14 '18 at 15:02
  • Possible duplicate of number of permutations in which k numbers come after each other – lulu May 14 '18 at 15:03
  • Note: the linked question assumes that the order rules define an ordering among the selected elements. If that is not the case, then you have to sum the orders which are compatible with the given rules. The basic principle, however, remains the same. – lulu May 14 '18 at 15:05

1 Answers1

1

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

Avnish Singh
  • 167