Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve 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.

share|cite|improve this answer
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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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