1

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.

Anthony
  • 177
  • 1
    How many do contain the string $1001001$? What the amount is, subtract it from the total number of bitstrings of length $10$. – JavaMan Dec 05 '12 at 03: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 05 '12 at 03: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 05 '12 at 04:01

2 Answers2

2

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.

Ross Millikan
  • 374,822
1

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$.

Brian M. Scott
  • 616,228