How many words are there of length $7$ are on $\{u,v,w,x,y,z\}$ without the string of letters $xxxx$?

Question

How many words are there of length $7$ are on $\{u,v,w,x,y,z\}$ without the string of letters $xxxx$?

My idea here is to use inclusion-exclusion. I was thinking of setting up the problem as follows: denoting $C_i$ to be the condition that words of length $7$ are with a string of $x's$ of length $i$ and let $N$ be a function that counts the size of the set.

So $N(C_5)={3 \choose 1}5^2$, since we can place the string $xxxxx$ in only 3 ways. Then with the remaining $2$ spots, we can choose any element from $\{u,v,w,y,z\}$ to place, which gives $5^2$ possibilities. So By the product rule, $N(C_5)={3 \choose 1}5^2$.

So there are: $$\begin{align} N(C^{\complement}) & =|\{\text{words of length $7$ on the set $\{u,v,w,x,y,z\}$}|-N(C_4)-N(C_5)-N(C_6)-N(C_7) \\ &=6^7-4\cdot5^3-3\cdot5^2-2\cdot5^1-1 \end{align}$$

Am I way off here or do I have the right idea?

Answer 1

The idea of subtracting from $6^7$ the number of ‘bad’ strings is fine, as is the idea of counting the bad strings according to the length of the unique string of $x$s making each one bad. (Notice that this would become significantly harder if we were looking at much longer strings, since such strings can be bad more than once.)

Clearly $N(C_7)=1$, as you say, and $N(C_6)=2\cdot5=10$, since the non-$x$ must be one of $5$ letters and can be at either end. $N(C_5)$ is a little trickier.

• You can have $axxxxxb$, where neither $a$ nor $b$ can be $x$; there are $5^2=25$ strings of this type.
• You can have $xxxxxab$ or $baxxxxx$, where $a\ne x$, and $b$ can be any of the $6$ letters; there are $2\cdot5\cdot6=60$ strings of this type.

Thus, $N(C_5)=25+60=85$.

I’ll leave you to try to fix the calculation of $N(C_4)$ using similar ideas; I’ve left the answer in the spoiler-protected block below so that you can check yourself.

$2\cdot5\cdot6^2+2\cdot5^2\cdot6=660$.