2
$\begingroup$

If I have a string that is 6-letters long and all lowercase letters, where letters can be repeated, how many strings contain neither the word bob nor tim?

Would I find the number of 6-letter strings that contain bob and the number of 6-letter strings contain tim separately then subtract their sum from the total number of strings possible?

$\endgroup$
1
  • 8
    $\begingroup$ That would be a good start and is how I would approach the problem as well, but you will need to be careful for a number of reasons. Be aware that there are some arrangements like boboba where bob appears multiple times. Be careful that you didn't subtract it from the total more than once. Also be aware that there are some arrangements like bobtim where both bob and tim simultaneously appear which again should also be subtracted from the total only once each and not multiple times. $\endgroup$ – JMoravitz Apr 8 '18 at 23:05
3
$\begingroup$

First count the number of $6$-letter strings containing the substring "bob".

For $1\le k\le 4$, the number of $6$-letter strings that contain the substring "bob" at position $k$ is $26^3$, since the other $3$ positions can be freely chosen.

Thus, we have an initial count of $(4)(26^3) = 70304$.

But this is an overcount since those $6$-letter strings containing two occurrences of "bob" are counted twice.

If a $6$-letter string has two occurrences of "bob", it's either "bobbob" or else it has one of the forms "Xbobob", "bobobX", where "X" can be any character.

Thus, the number of $6$-letter strings containing two occurrences of "bob" is $1 + 26 + 26 = 53$, hence the corrected count for the number of $6$-letter strings containing the substring "bob" is $70304-53=70251$.

Next, count the number of $6$-letter strings containing the substring "tim".

The initial count is $(4)(26^3) = 70304$, the same as for the substring "bob".

But the overcount is just $1$, since the only $6$-letter string containing two occurrences of "tim" is "timtim".

Hence, the corrected count for the number of $6$-letter strings containing the substring "tim" is $70304-1=70303$.

It follows that the number of $6$-letter strings containing at least one of the substrings "bob" or "tim" is $70251+70303-2=140552$, where the subtraction of $2$ is to correct for the strings "bobtim" and "timbob", which were counted twice.

Finally, the number of $6$-letter strings not containing either of the substrings "bob" or "tim" is $26^6-140552=308775224$.

$\endgroup$
1
  • $\begingroup$ This is a fantastic answer @quasi ! Thank you! $\endgroup$ – adamcasey Apr 9 '18 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.