Question: > 
> Count the number of arrangements of the $10$ letters ABCDEFGHIJ in which none of the patterns ABE, BED, or HID occur.
> 
> 
> 

I thought that the answer would be $\_{10}P\_{10} - (\_{10}P\_{3} + \_{10}P\_{3} + \_{10}P\_{3} - \_{10}P\_{2}$), since we have $\_{10}P\_{10}$ total arrangements, and $\_{10}P\_{3}$ arrangements for ABE, BED, and HID. But we subtracted $BE$ twice, so we need to add it back in: $\_{10}P\_{2}$.

Please tell me what is wrong with my reasoning!

Answer: 
There are $10!$ permutations of the ten distinct letters. From these, we must subtract those arrangements in which the substrings ABE, BED, or HID appear.

*Arrangements with a prohibited substring*: We count arrangements in which ABE appears. We have eight objects to arrange: ABE, C, D, F, G, H, I, J. Since the objects are distinct, they can be arranged in $8!$ ways.

By symmetry, there are $8!$ arrangements in which BED appears and $8!$ arrangements in which HID appears.

Hence, there are $3 \cdot 8!$ arrangements with a prohibited substring.

However, if we subtract this amount from the total, we will have subtracted each arrangement in which two prohibited substrings appear twice, once for each way we could designate one of those substrings as the prohibited one. We only want to subtract such arrangements once, so we must add them back.

*Arrangements with two prohibited substrings*: Since it is not possible for a permutation of the letters A, B, C, D, E, F, G, H, I, J to contain both BED and HID, this can occur in two ways. Either both ABE and BED appear in the arrangement or both ABE and HID appear in the arrangement.

Substrings ABE and BED both appear in the arrangement: This can only occur if the arrangement contains the substring ABED. Then we have seven objects to arrange: ABED, C, F, G, H, I, J. Since the objects are distinct, they can be arranged in $7!$ ways.

Substrings ABE and HID both appear in the arrangement: We have six objects to arrange: ABE, HID, C, F, G, H, I, J. Since the objects are distinct, they can be arranged in $6!$ ways.

*Arrangements with three prohibited substrings*: Since BED and HID cannot both appear in an arrangement of the letters A, B, C, D, E, F, G, H, I, J, there are no arrangements in which ABE, BED, and HID all appear.

Therefore, by the [Inclusion-Exclusion Principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle), the number of arrangements of the letters A, B, C, D, E, F, G, H, I, J in which none of the substrings ABE, BED, and HID appear is 
$$10! - 3 \cdot 8! + 7! + 6!$$
Since $ABE$ and $HID$ are disjoint, all Permutations where both patterns occur are subtracted twice.