Counting number of arrangements for a string, with conditions This question here has a similar situation, but it was with numbers and does not cover the case where substrings overlap: Find the number of rearrangements of the string 12345 in which none of the sequences 12, 23, 34, 45 occur Say we have a string ABCDEFGHIJ, length 10. Find the number of arrangements for this string given that there cannot be the patterns ABE, BED nor HID. To do this, I go by inclusion-exclusion: take the total number of possible arrangements (10!) minus the number of arrangements with ABE, BED, or HID (8! in each case). But the substring ABED and ABEHID and HIDABE are counted twice in that calculation. Hence, add in the number of arrangements with ABED (7!) and number of arrangements with ABEHID (2 * 5!). ie. answer is given by $10! - 3*8! + 7! + 2*5!$ which is wrong. Would anyone like to point out the mistake in this?

The number of arrangements with ABE and HID is $6!$ (including such as CABEGJHIDF, where the two forbidden patterns are not adjacent). Accounting for this, your final count is $$10!-3*8!+7!+6!$$