how many strings of length 21 from letters {D,L,O} with repetition that have DOLL appearing only once

Question

The word DOLL has length $4$. There will be $18$ possible positions where 'DOLL' can appear, each with $3^{17}$ choices. So there will $18 \cdot 3^{17}$ cases where it can appear at least once. But I also know that there will be many duplicates in this approach. How do I go about removing them.

I can count those

1. With DOLL appearing at least / only $5$ times as $\binom{6}{5}$ each with $3^{21-4 \cdot 5} = 3$ choices.
2. With DOLL appearing at least $4$ times as
   • $21$ positions to place DOLL first time
   • $17$ positions to place DOLL second time
   • $13$ positions to place DOLL third time
   • $9$ positions to place DOLL fourth time
   • all with $3^{5}$ choices, so this gives $21 \cdot 17 \cdot 13 \cdot 9 \cdot 3^5$ possibilities
   • if I subtract all the choices that have $5$ occurrences of DOLL ($\binom{6}{5} \cdot 3$)from this, I will get only those that have $4$ occurrences of DOLL

But from here on how do I proceed for calculating $3$, $2$ and only $1$ occurrences. Do I apply the inclusion exclusion principle at each step or only when calculating for at most $1$ occurrence of DOLL.

Answer 1

"DOLL" can't self-overlap, so you can consider each occurrence of it as a separate block. There are $3^{21-4k}$ strings with "DOLL" in $k$ particular places, and $\binom{21-3k}k$ ways to choose the $k$ places, so by inclusion-exclusion there are

$$ \sum_{k=1}^5(-1)^{k-1}\binom k1\binom{21-3k}k3^{21-4k}=2002583502 $$

strings that contain "DOLL" exactly once.

Answer 2

This answer is incorrect since I failed to account for the fact that we wish to count those arrangements in which DOLL appears exactly once. The issue is that when we apply the Inclusion-Exclusion Principle, we usually start with all the arrangements, then exclude the bad arrangements. In this case, we start with arrangements that include DOLL once, then wish to exclude arrangements that include DOLL more than once. See Joriki's answer for a correct solution and this question he posed about a generalized version of the Inclusion-Principle.

If DOLL appears once, we have $18$ objects to permute, the block containing DOLL and the other $17$ letters. As you concluded, we have $18$ choices for the position of the block and three choices for each of the other $17$ letters, so there are $$\binom{18}{1}3^{17}$$ arrangements in which DOLL appears once, as you found.

From these, we must exclude those arrangements in which DOLL appears more than once.

If DOLL appears twice, we have $15$ objects to permute, two identical blocks containing DOLL and the other $13$ letters. There are $\binom{15}{2}$ ways we can place the two blocks and three choices for each of the other $13$ letters, so there are $$\binom{15}{2}3^{13}$$ arrangements in which DOLL appears twice.

If DOLL appears three times, we have $12$ objects to permute, three blocks containing DOLL and the other $9$ letters. There are $\binom{12}{3}$ ways we can place the three blocks and three choices for each of the other $9$ letters, so there are $$\binom{15}{3}3^9$$ arrangements in which DOLL appears three times.

If DOLL appears four times, we have $9$ objects to permute, four blocks containing DOLL and the other $5$ letters. There are $\binom{9}{4}$ ways we can place the four blocks and three choices for each of the other $5$ letters, so there are $$\binom{15}{4}3^5$$ arrangements in which DOLL appears four times.

If DOLL appears five times, we have $6$ objects to permute, five blocks containing DOLL and the other letter. There are $\binom{6}{5}$ ways we can place the five blocks and three choices for the other letter, so there are $$\binom{6}{5}3$$ arrangements in which DOLL appears five times.

As you observed, DOLL cannot appear six times. Thus, by the Inclusion-Exclusion Principle, the number of arrangements of the letters $\{D,L,O\}$ with repetition in which DOLL appears only once is $$\binom{18}{1}3^{17} - \binom{15}{2}3^{13} + \binom{12}{3}3^9 - \binom{9}{4}3^5 + \binom{6}{5}3$$

Answer 3

(This is simply a supplement to the two previous answers.)

As shown in N.F. Taussig's answer, the number of words with DOLL appearing at least once is given by

$\hspace{.5 in}\displaystyle\binom{18}{1}3^{17} - \binom{15}{2}3^{13} + \binom{12}{3}3^9 - \binom{9}{4}3^5 + \binom{6}{5}3=2,161,418,679$

Similarly, the number of words in which DOLL appears at least twice is given by

$\hspace{.5 in}\displaystyle\binom{15}{2}3^{13} -\binom{2}{1} \binom{12}{3}3^9 +\binom{3}{1} \binom{9}{4}3^5 -\binom{4}{1} \binom{6}{5}3=158,835,177$

Subtracting, we get $2,002,583, 502$ words in which DOLL appears exactly once,

as shown in joriki's answer.