1
$\begingroup$

Assume I want all permutations of a set of numbers with certain numbers must go before others.

Similar to this question but I'm looking for a more general formula.

For example the set [5,2,1,8,9,7] produces 6! but if the 5 has to come first and the 8 must come before the 9 and 7 and the 2 must come before the 1, that's a little harder to do by hand (it should be 20 or 6! / 6 * 3 * 2 according to my calculations)

Is there a way formula for this?

Edit (a couple of more examples)

[5, 3, 9, 1, 2, 8] where the 5 must come first and

  1. 3 before 1
  2. 1 before 2
  3. 9 before 8

There should be 10


5, 3, 9, 1, 2, 8, 11] where the 5 must come first and

  1. 3 before 1
  2. 1 before 2
  3. 9 before 8
  4. 9 before 11

There should be 40


[5, 3, 9, 1, 4, 8, 11] where the 5 must come first and

  1. 3 before 1
  2. 3 before 4
  3. 9 before 8
  4. 9 before 11

There should be 80


[5, 3, 9, 1, 2, 4, 8, 11] where the 5 must come first and

  1. 3 before 1
  2. 3 before 4
  3. 1 before 2
  4. 9 before 8
  5. 9 before 11

There should be 210

$\endgroup$
  • 1
    $\begingroup$ You counted correctly. Hard to know what a more general formula might mean, since the general problem has not been defined. But there are techniques, one of which you used. $\endgroup$ – André Nicolas Dec 28 '14 at 3:39
  • 1
    $\begingroup$ I agree - you're counting seems accurate -- however, its difficult to quantify a general problem for then a general formula. Maybe quantify the problem as permutation of n elements ($\mathbb{N}_n$) with a set of rules $\mathcal{A}$ where each $A \in \mathcal{A}$ is a 2-tuple ($A_{before}$, $A_{after}$) where $A_{before}$ is a set of elements that must occur before $A_{after}$. $\endgroup$ – Chinmay Nirkhe Dec 28 '14 at 3:43
  • $\begingroup$ @ChinmayNirkhe I'm not sure how to go about putting the problem in those terms, I've updated the problem with more examples to better illustrate the requirements. $\endgroup$ – qwertymk Dec 28 '14 at 3:48
  • $\begingroup$ @AndréNicolas I added more test cases, I'm just not seeing a pattern that I can generalize $\endgroup$ – qwertymk Dec 28 '14 at 4:02
3
$\begingroup$

In general, most counting problems (especially those taught in an introductory course) usually boil down to some combination of Multiplication Principle, Addition Principle, and Inclusion-Exclusion. In particular, when counting something like this, it is best to break it into steps. I also like to have a running picture of what it is that I've chosen and what it is I have yet to choose when doing a multiplication principle question.

Lets examine the first question more closely:

How many permutations of $[5,2,1,8,9,7]$ exist that follow the rules: $\bullet~~5$ must come first, $\bullet~~8$ must come before both $9$ and $7$, $\bullet~~$and $2$ must come before $1$

Breaking it into steps in terms of which is most difficult to place,

Step 1: Pick which place the $5$ goes into. The first slot is the only option, so there is only one choice. We currently know it looks something like $\underline{5}\underline{\bullet}\underline{\bullet}\underline{\bullet}\underline{\bullet}\underline{\bullet}$

Step 2: Pick which slots the $8$,$9$, and $7$ collectively occupy (order ignored). As there are five slots remaining, there are $\binom{5}{3}$ possible. Suppose for illustration that we chose the second through fourth slots. We now know that it looks something like $\underline{5}\underline{?}\underline{?}\underline{?}\underline{\bullet}\underline{\bullet}$ where the ?'s are occupied by the 8,9, and 7 in a currently unknown order.

Step 3: Pick the order in which the 8,9, and 7 appear within their slots that we picked for them in step 2. Since the $8$ must come before the 9 and 7, there are two choices. Either 897 or 879. Suppose for illustration that it was the second $\underline{5}\underline{8}\underline{7}\underline{9}\underline{\bullet}\underline{\bullet}$

Step 4: Pick which spots the 2 and 1 collectively occupy (order ignored). There are only two spots left, so in fact there is only one choice. They must be in the slots that remain that aren't occupied by the 5,8,9, or 7. $\underline{5}\underline{8}\underline{7}\underline{9}\underline{?}\underline{?}$ where the ?'s are occupied by the 2 and 1 in a currently unknown order.

Step 5: Pick which order the 2 and 1 appear in. Since the 2 must come before the 1 according to our rules, there is only one choice. $\underline{5}\underline{8}\underline{7}\underline{9}\underline{2}\underline{1}$

As a result, we have picked all of the needed information to completely classify a given sequence following these rules, and the number of total possibilities is the product of the number of available choices at each step for a total of $1\cdot \binom{5}{3}\cdot 2\cdot 1\cdot 1 = \frac{5!}{3!2!}\cdot 2 = \frac{5\cdot 4}{2}\cdot 2 = 20$


Examining the final posted example in more detail as requested, as well as beginning to hint at thoughts on the general procedure, we have the following rules:

$\bullet~~$3 before 1, $\bullet~~$3 before 4, $\bullet~~$1 before 2, $\bullet~~$9 before 8, $\bullet~~$9 before 11.

Note that any collection of rules should be consistent and can be viewed as a Poset. I.e., when drawing the Hasse Diagram there should be no directed cycles. If there were, then the rules are inconsistent.

Our Hasse diagram for this set of rules look like this:

hasse diagram for our set of rules

For lack of better terms, you may consider each "loose braid" separately where I define a loose braid to be a maximal collection of not vertex-disjoint directed paths where all other directed paths are vertex disjoint (excluding a root and tail vertex). In the example above, the vertices $3,1,2,4$ form a loose braid and $9,8,11$ form a loose braid with start as the root vertex and finish as the tail vertex. It is unfortunately possible that braids become tangled, more on that later. Back to solving this particular example by breaking it into steps.

Step 1: Pick which spots the $9,8,11$ braid collectively occupies (order currently ignored). There are $\binom{7}{3} = \frac{7!}{3!4!}$ number of choices. Suppose for illustrative purposes they occupy the first three slots. Our currently known information then looks then like $\underline{?}\underline{?}\underline{?}\underline{\bullet}\underline{\bullet}\underline{\bullet}\underline{\bullet}$ where the ?'s are occupied by $8,9,11$ in some currently unknown order.

Step 2: Pick in what order the elements in the $9,8,11$ braid appear. As the 9 must come before both the 8 and the 11, it must be the 9 first. The second substep here is to pick which comes after the 9. There are two choices, either the 8 or the 11. After having picked that, the third substep is to pick the remaining one, for one choices, for a combined total of $2$ ways to complete step two. For illustrative purposes let it be the 11 before the 8. Our currently known information then looks like $\underline{9}\underline{11}\underline{8}\underline{\bullet}\underline{\bullet}\underline{\bullet}\underline{\bullet}$

Step 3: Pick the locations occupied by the 3,1,2,4 braid with order ignored. As there are only 4 locations left it must be those for a total of $\binom{4}{4} = \frac{4!}{4!0!}=1$ available choices. Denote the locations by ?'s. Our current known information looks like $\underline{9}\underline{11}\underline{8}\underline{?}\underline{?}\underline{?}\underline{?}$

Step 4a: Pick the order in which the pieces are placed. We could treat this as a new problem and split this into sub-braids with 3 as the new root vertex and finish as the tail vertex. As 3 is the root vertex, it must be placed in the front. Our current known information is $\underline{9}\underline{11}\underline{8}\underline{3}\underline{\bullet}\underline{\bullet}\underline{\bullet}$

Step 4b: Pick the locations occupied by the subbraid 1,2. There are 3 locations remaining, so there are $\binom{3}{2} = \frac{3!}{2!1!} = 3$ choices. Identify those by ?'s and assume for illustrative purposes that they were the next two spots on our list. We are now at: $\underline{9}\underline{11}\underline{8}\underline{3}\underline{?}\underline{?}\underline{\bullet}$

Step 4c: Pick the order in which the elements in the 1,2 subbraid go. As it is a chain, the order is predetermined, so there is only one choice. $\underline{9}\underline{11}\underline{8}\underline{3}\underline{1}\underline{2}\underline{\bullet}$

Step 4d: Pick the location for and then the order for the 4 subbraid to go. As there is one location left, and you can only order a single element one way, there is $1$ way to complete this task. $\underline{9}\underline{11}\underline{8}\underline{3}\underline{1}\underline{2}\underline{4}$ As our running tally of information is now completely filled, we know that we have successfully completely characterized the sequence.

For a final total of: $\binom{7}{3}\cdot 2\cdot 1\cdot \binom{3}{2}\cdot 1\cdot 1 = \frac{7!}{3!4!}\cdot 2\cdot 3 = \frac{7!}{4!} = 7\cdot 6\cdot 5 = 210$


As to how to generalize this to an arbitrary collection of rules, note that some collections of rules are not possible to fulfill which can be seen from looking at the directed graph formed by the rules (the Hasse diagram, though I suppose if the rules are inconsistent, the graph wouldn't be called a Hasse diagram anymore). You may look at each "braid" individually as I suggested above, but again be warned that the case of tangled braids can be quite messy. If I were to try to define a tangled braid, it would be a maximal set of paths such that it is not a part of any loose braid. For example, if the rules were instead $3<4, 3<1, 2<1$, that would constitute a tangled braid. I apologize if my definitions are poor or confusing, if someone who is more familiar with Posets than I recognize the objects I am referring to, I would gladly hear a more formal term and definition if one exists. To deal with tangled braids, it would likely need to be done using inclusion-exclusion.

$\endgroup$
  • $\begingroup$ JMoravitz, this answer shows the answer to the sample problem given by @Moshe but it doesn't tell us about the general question of a general permutation. $\endgroup$ – Chinmay Nirkhe Dec 28 '14 at 4:09
  • $\begingroup$ I disagree. Combinatorics is much more intuitive rather than formulaic, and so it is a matter of seeing how to count rather than simply applying a formula. I think JMoravitz's answer hits on this point pretty well. $\endgroup$ – ml0105 Dec 28 '14 at 5:48
  • $\begingroup$ Excellent answer, can you explain how I would deal with nested (?) groups like the last example I give where 3 goes before 1 and 1 goes before 2? $\endgroup$ – qwertymk Dec 28 '14 at 13:10
  • $\begingroup$ Also, can you explain what's happening when you do 5!/3!2! I would assume that it's the P(5,3) term which is 5!/2! where is the 3! coming from? $\endgroup$ – qwertymk Dec 28 '14 at 15:18
  • $\begingroup$ @Moshe The term is not infact a $P(5,3)$ but is a $C(5,3)$. The $3!$ essentially is there to divide by symmetry in order cause the term to ignore order (as the order would be taken care of in a later step). $\endgroup$ – JMoravitz Dec 28 '14 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.