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?
Answer
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$.
No comments:
Post a Comment