# How many permutations of letters ABCDEFG contain the strings ABC and CDE

For this problem, I understand how to find something like how many strings contain the string BA and GF. I just look at the set of letters like this:

{BA, GF, C, D, E}

and since I have 5 distinct elements I can calculate the number of permutations with 5!.

However, I am not sure what to do when the two strings overlap such as the number of permutations which contain the string ABC and CDE or CBA BED.

• Break it into steps. How many strings with $ABC$ are there (ignoring whether or not CDE is present). How many with $CDE$? Finally, how many with $ABCDE$? Use inclusion-exclusion to finish. $|X\cup Y| = |X|+|Y|-|X\cap Y|$ – JMoravitz Feb 18 '15 at 1:18
• Shouldn't ABCDE be one element? – Waffle Feb 18 '15 at 1:20
• @Waffle Looks like you are right. Treating it as {abcde, f, g} and thus using 3! gave me the correct answer. Thanks! – James Hogle Feb 18 '15 at 1:25
• @Waffle I guess this is because the only possible way to have ABC and CDE would be the string ABCDE right? – James Hogle Feb 18 '15 at 1:31
• yeah, add details whether ABC & CDE appears simultaneously or not – Bhaskara-III Dec 11 '16 at 12:37

## 3 Answers

Add the two situations individually and subtract the overlap.

For (ABC) & (CDE) both the pattern has to be combined to get both of them simultaneously i.e. (ABCDE) then number of possible permutations is 3! and for the second question, it is not possible to get (CBA) and (BED) simultaneously so answer is 0.

• how the answer is zero? it can't be zero. so think deeply before you answer – Bhaskara-III Dec 11 '16 at 12:34

Notice that since D and E come after C and A and B before, we must actually have the string ABCDE.

It's unclear whether you mean for the string to be contiguous. If contiguous, you can see that there are four possibilities, two with the string at the beginning and two with it starting at the second place.

If not contiguous, there are $\binom75=21$ ways to pick the spots of ABCDE, then two ways to arrange the F and G for each of these. Thus the answer is 42 in that case.