Question:
How many arrangments of the word $AABBBCD$ contain the subword $AB$?
My attempt:
We can naively find the number of arrangements by treating $AB$ as a single 'letter' and then proceed to calculate the number of permutations therein. As such, after reducing $AB$ to a single letter, we now have $6$ letters, with a double repeat of $B$, giving us,
$$ \frac{6!}{2!} \tag{$\ast$}. $$
However, a problem arises because the remaining letters still contain an $A$ and a $B$ so, the above expression will incorrectly count the arrangements
$$ \mathbf{AB}ABBCD \text{ and } AB\mathbf{AB}BCD$$
separately. Hence, $(\ast)$ is definitely over-counting. My question is, do I now treat the subword $w = ABAB$ as one word, find all permutations of the original string containing $w$, which would be $4!$ (since we now only have 'four' letters with no repeats), and then subtract this from $(\ast)$? Are there other ways $(\ast)$ is over-counting that I'm missing? Any help would be greatly appreciated, thank you!
Best Answer
No, using a four-letter ABAB token would undercount the degree to which you overcounted, so your final answer would still be an overcounting. You can have two AB tokens in a word, separated by other letters. So you would instead want to use two separate AB tokens. Then you would have 5 tokens to choose from, with a double repeat of AB, 5!/2! That is the conjunctive case; subtract it from your overcounted 6!/2! case, and you have the inclusive disjunction, the answer: (6!-5!)/2 = 300. Compared to your total permutations, 7!/(2!*3!) = 420, that's a high proportion--71.4% containing AB.
Edit: The formula is again incorrect, as this time these two sequences are counted separately:
ABABBCD ABABBCD
To correct, we can this time just divide by two, giving 5!/(2*2!) rather than 5!/2!.
Answer is then 6!/2! - 5!/(2*2!), = 330, total proportion is therefore 78.6%.