Practical illustration of the inclusion-exclusion principle

Question

I am currently doing a combinations problem that has two parts.

Part A: There are $26$ uppercase letters in the alphabet (A, B, C ... Z). How many $20$-letter words contain the subword 'DOWNTIME' twice?

The two instances of 'DOWNTIME' are treated as two blocks, and the remaining 4 letters are slotted in between or around these blocks. So using stars-and-bars, we get $6\choose2$ ways of arranging the blocks. The $4$ individual letters can be any letter from A...Z so we get $26^4$ arrangements there.

Therefore the total number of words containing 'DOWNTIME' twice is equal to $6\choose2$ * $26^4$.

However, I am stuck on Part B.

Part B: How many $20$ letter words do NOT contain 'DOWNTIME' AT ALL?

My approach here was:

total $20$-letter words $-$ (words containing exactly $1$ 'DOWNTIME') $-$ (words containing exactly $2$ 'DOWNTIME').

So using the method in Part A I found that the number of words containing at least $1$ 'DOWNTIME' = $13 \choose 1$ * $26^{12}$

However, this also contains all the instances in which 'DOWNTIME' appears $2$ times (since those remaining $12$ letters include arrangements in which the letters sequentially form 'DOWNTIME').

Now, if $13 \choose 1$ * $26^{12}$ accounts for BOTH $1$ occurence of 'DOWNTIME' AND $2$ occurences of 'DOWNTIME', why do we need to apply the inclusion/exclusion principle?. Why is the answer NOT just $20^{26} - {13 \choose 1} * 26^{12}$ ?

I understand how the inclusion/exclusion principle works for 3 sets, but I just cannot understand how it applies in this particular scenario.

The given answer is: $26^{20} - {13 \choose 1} * 26^{12} + {6\choose2} * 26^4$.

I know that there is double counting going on, but I don't know where nor why. If anyone can illustrate the application of inclusion/exclusion principle here I would be grateful!

Answer 1

The strings with two downtimes are counted twice in ${13 \choose 1}\cdot 26^{12}$. Either the first downtime is the fixed block and the second downtime is built from individual letters, or the other way around.

If $n_k$ is the number of strings with exactly $k$ copies of DOWNTIME, then we have:

$26^{20} = |\text{All length 20 strings}| = n_0+n_1+n_2$
${13 \choose 1}\cdot 26^{12} = n_1+2n_2$
${6 \choose 2}\cdot 26^4 = n_2$

$n_0 = (n_0+n_1+n_2)-(n_1+2n_2)+n_2 = 26^{20}-{13 \choose 1}\cdot 26^{12}+{6 \choose 2}\cdot 26^4$

Answer 2

The instance ${13}\choose{1}$ $26^{12}$ Indeed does count 20-letters words with At Least One occurence of "DOWNTIME". However, it counts those having two "DOWNTIME" twice, as the remaining letters in $26^{12}$ can also contain one occurence of it, in which case, the resulting word will be counted once more when permuting the original "DOWNTIME" you're excluding.

For example, the two following words are the same, but will be counted as two separate entities in your "at least once" formula, hence the need of using PIE to remove double-"DOWNTIME" strings (think of it as the blue letters being a fixed "DOWNTIME" block, and the red letters being randomly selected from the upper-case alphabet): $$\color{blue}{DOWNTIME}\color{red}{PIENDOWNTIME} $$ $$\color{red}{DOWNTIMEPIEN}\color{blue}{DOWNTIME}$$

Hope that sheds light on the issue for you.