2

Find the number of permutations of ABCDEFGHI such that the patterns ABC, DEF, GHI do not occur. I am getting $181434$. $$(9!-9!/3!\cdot3)-3!$$

Michael Hardy
  • 1
Subhasis Biswas
  • 2,600
  • Such that none of them occur, or such that not all of them occur? In other words, is ABCDEFIHG acceptable because not all of ABC, DEF, and GHI occur, or is it unacceptable because at least one of ABC, DEF, and GHI occurs? – Brian Tung Sep 02 '17 at 19:25
  • @BrianTung none of them. – Subhasis Biswas Sep 02 '17 at 19:26
  • 1
    The raw result is not very enlightning. You should explain your way of reasoning. – Jean Marie Sep 02 '17 at 19:29
  • 1
    When you say "pattern," do you mean a not necessarily contiguous subsequence? – Matt Samuel Sep 02 '17 at 19:34
  • Your answer does not make sense. The second term counts permutations in which $A$ comes before $B$ and $B$ comes before $C$ or $D$ comes before $E$ and $E$ becomes before $F$ or $G$ comes before $H$ and $H$ comes before $I$ while your last term counts permutations of the blocks $ABC$, $DEF$, and $GHI$. Brian Tung has shown you how to count permutations in which none of those blocks occurs. – N. F. Taussig Sep 02 '17 at 21:22
  • @N.F.Taussig The most appropriate approach is to assume the patterns as an entire unit and proceed. I did it that way, but the answer isn't at all close. But all I could do is to come up with the nonsense calculation in order to match one of the four given choices. – Subhasis Biswas Sep 02 '17 at 21:29
  • If you use the subsequence interpretation, you should get $210,000$, which is still much larger than the answer in the answer key. – N. F. Taussig Sep 02 '17 at 21:40

1 Answers1

2

Sketch of approach. First find the number $N_{ABC}$ of combinations that contain ABC. You can do this by treating ABC as a single "letter", along with the other actual letters D through I. Note that $N_{DEF} = N_{GHI} = N_{ABC}$.

Now, if you add up $N_{ABC}+N_{DEF}+N_{GHI}$, you get an expression that is somewhat of an overcount of the number of disqualified permutations. The reason is that a permutation such as GABCHIDEF is counted under both $N_{ABC}$ and $N_{DEF}$. You must therefore use inclusion-exclusion to count them properly. You need to determine $N_{ABC,DEF}$ (by treating ABC and DEF both as single letters), and also $N_{ABC,DEF,GHI}$ (by treating ABC, DEF, and GHI all as single letters). Then the number of disqualified permutations is

$$ N_{ABC}+N_{DEF}+N_{GHI} - N_{ABC,DEF} - N_{ABC,GHI} - N_{DEF,GHI} +N_{ABC,DEF,GHI} $$

Finally, subtract from $9!$, the total number of permutations, to get the number of qualified permutations.

Brian Tung
  • 34,160