# How many 0,1 bit strings of length 10 are there which do not contain a string of 1001001?

I've never been asked a question involving how many do not contain a specific string and I'm not quite sure how to go about answering this question.

-
How many do contain the string $1001001$? What the amount is, subtract it from the total number of bitstrings of length $10$. – JavaMan Dec 5 '12 at 3:49
How do I get started on that path I'm very new to discrete math. Would I do 11 c 7 for that? – Anthony Dec 5 '12 at 3:53
My answer had a minor problem, and since I posted it, there are many other answers now that should provide details on how to go about this process. – JavaMan Dec 5 '12 at 4:01

Hint, following on JavaMan's comment: You probably know there are $2^{10}$ total 10-bit strings. Now to contain $1001001$ you can have a string of the form $xxx1001001$ (where the $x$'s are either $1$ or $0$) or a few similar choices, so subtract them. The challenge comes in whether you have subtracted a string twice-so think about the various patterns and see if the same string can satisfy more than one.

-
All the possible patterns are: 1001001xxx x1001001xx xx1001001x xxx1001001 Is this correct? – Anthony Dec 5 '12 at 3:55
@Anthony: that is correct. – Ross Millikan Dec 5 '12 at 3:57

This problem is actually just a little tricky. JavaMan’s suggestion in the comments is the way to go, but there’s a little sting in the tail.

In a ten-bit string the seven-bit string $1001001$ can start at the first, second, third, or fourth bit. Each of those starting positions leaves $3$ bits that can be anything. Thus, there are $2^3=8$ ten-bit words of the form $1001001xxx$, $8$ more of the form $x1001001xx$, and so on, for a total of $4\cdot8=32$ ten-bit strings containing $1001001$.

BUT there might be some ten-bit strings that have $1001001$ starting in more than one of the four possible starting positions, and if so, we’ve counted those strings twice. A little thought reveals that there is exactly one such string, $1001001001$; we counted it once for $\color{red}{1001001}001$ and once for $100\color{red}{1001001}$. Thus, the number of strings containing the substring $1001001$ is really only $32-1=31$.

Finally, there are $2^{10}=1024$ ten-bit strings, so there are $1024-31=993$ that do not contain the substring $1001001$.

-
Thank you very much for your help, I believe I understand the question and the answer now. – Anthony Dec 5 '12 at 4:02
@Anthony: You’re most welcome. – Brian M. Scott Dec 5 '12 at 4:05